HZOJ-599:两数之和 1#
样例输入
6 15
1 5 6 7 10 26
样例输出
1 4
- 思路
方法 | 说明 | 时间复杂度 | 空间复杂度 |
---|---|---|---|
暴力 | 两层循环 | O(N^2) | O(1) |
暴力 | 固定一个数, 另一数用二分去查找 | O(NlogN) | O(1) |
哈希表 | 遍历第一遍,存 遍历第二遍,找 | O(N) | O(N) |
⭐双指针 | 两边指针加, 不断更新 | O(N) | O(1) |
-
双指针
-
数组有序
-
同理,三数之和、四数之和...
- 多一层循环
-
代码
-
HZOJ-600:杨氏矩阵#
样例输入
3 4
1 2 3 4
5 6 15 20
7 10 20 25
15
样例输出
2 3
- 思路
- 从左下角出发或从右上角开始
- 逐步移动横坐标或纵坐标一个单位
- 时间复杂度:O (n + m)
- 和上一题的双指针思想很相似~
-
- 二维空间和一维空间的转换!
-
- 从左下角出发或从右上角开始
- 代码
-
- 提交还是有 2 个 test 超时,还有更快的方法吗?
- 没有,是 OJ 平台的波动性导致的
-
HZOJ-477:元音字母#
样例输入
ABCDEFGIKJUMNBZZ
样例输出
44
- 思路
- 找到上一个元音字母的位置
- 遍历接下来的元音字母的位置
- 计算距离,更新答案
- 代码
-
- s [i] 为 \0 时停止
- last 初始为 - 1,可以在找到第一个元音时,不计算距离,只更新 last
-
HZOJ-479:乒乓球#
样例输入
WWWWWWWWWWWWWWWWWWWW
WWLWE
样例输出
11:0
11:0
1:1
21:0
2:1
- 思路
- 给一个计分结果,分别输出 11 分制下和 21 分制下的比赛结果
- 输出每局得分几比几
- 根据输入数据每行最多 25 个字母,最多有 2500 行
- 得到 2500 * 25 分,/11 或者 / 21
- 得到 11 分制下最多6000局,21 分制下最多3000局
- 判断要开的数组大小
- 给一个计分结果,分别输出 11 分制下和 21 分制下的比赛结果
- 代码
-
- cin 读入规则
- 遇到空格、换行符和制表符结束输入,并在缓冲区中留下使输入结束的结束符 (Enter、Space、Tab),作为下次 cin>> 开头的忽略
- 遇到 EOF 会返回 1
-
HZOJ-480:保龄球#
样例输入
/ / / 72 9/ 81 8/ / 9/ / 8/
样例输出
192
- 思路
- 关键就是红框那段话
- 三种计分情况
- 直接清空:本轮 10 分 + 接下俩 2 球得分
- 间接清空:本轮 10 分 + 接下俩 1 球得分
- 没清空:本轮得分
- 一局十轮
- 👌使用结构体
- 字符数组:每轮对应的得分字符串 8/
- 第一次后得分
- 第二次后得分:本轮最终得分,这里很巧妙,根据题意设置
- Flag:属于上述第几种情况
- 代码
-
- 关键在理解规则,以及巧妙利用结构体!
- s 数组开 4,本来最多是 2 个字符 +\0,但是因为字节对齐,开 3 开 4 一样,这里开 4
- 在终端需使用 ctrl + d 结束 cin 所在的 for 循环
-
HZOJ-481:冰壶比赛#
样例输入
8
5 20 18 19 3 15 13 3
20 2 17 12 5 18 10 11
20 3 4 1 2 11 9 2
1 15 19 9 8 14 11 10
15 2 10 1 19 14 3 18
15 17 21 19 24 32 19 26
-1
样例输出
0:1
0:0
3:0
3:1
- 思路
- 谁能得分:所有冰壶离圆心最近的队可以得分
- 得多少分:在半径 r 内,且在对方离圆心最近的冰壶构成的⚪内,得分队有多少个冰壶
-
- 绿队可得 2 分
- 来自田船长之笔~
-
- 最多 10 局,20 行 + 1
- 先输出每轮的比分,再输出总比分
- 代码
-
- 利用 sort 更方便找获胜方和计分,消耗不大
-
HZOJ-484:柱状统计图#
样例输入
ABC ABC.DEF()G GCC XY
354342aaaCaa aaaaaaaabcdbcd
样例输出
*
*
*
* * * *
* * * * * * * * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
- 思路
- 简单:统计大写字母的个数
- 难点:每行不要有多余的空格;按列输出
- 流程
- 需根据最大的字符出现次数统计行数
- 外层循环:从 mmax 到 1,在满足条件的字符位置上输出 *
- 先得到每行最后一个输出 * 的字符,从 Z 到 A 判断是否满足条件
- 里层循环:从 A 到 ind,需统计每一行最后一个字符是哪个
- 注意 * 和空格的输出条件
- 就是判断字符的统计数是否大于在该行输出 * 需满足的数量
- 代码
-
- 逻辑要理清~
- num 数组开 130 位很巧妙,与 ASICII 码范围对应,统计时不需要判断
- 首位判断:避免有多余的空格
-
HZOJ-485:均分纸牌#
样例输入
4
9 8 17 6
样例输出
3
- 思路
- 只能移到相邻牌堆
- 先算平均数,得到每堆牌的预期数量
- 从一个方向凑到平均数即可
- 从左往右
- 不够借,右边变负数也没问题
- 本质和两种方向凑一样!
- 代码
-
- 最后一堆牌不用考虑
- 只需更新右边一个数,公式无论加减都成立
-
HZOJ-503:独木舟(自己做)#
样例输入
100
9
90
20
20
30
50
60
70
80
90
样例输出
6
- 思路
- 排序再遍历判断
- 代码
HZOJ-504:删数⭐#
样例输入
179566
4
样例输出
15
- 思路
- 大整数
- 精髓:越靠前的数越小,整体才会小
- 大数在前、小数在后情况,删掉大数
- 而直接删除大数是不行的
- 单调栈知识?参考什么是单调栈?- 五分钟学算法
- 流程:
- 扫一下大整数,得到字符串
- 使用 string 类,可以比较方便地删数
- string.replace()
- 遍历每两位
- 循环删的次数 s 次
- 输出
- 忽略前导 0,必须要有 flag,只是判断前导 0,不省略其他 0
- 扫一下大整数,得到字符串
- 延伸:删字母使字典序尽可能小
- 代码
-
- ind 默认为最后一位!即最大数,因为是从小到大排列的
- str.replace 操作,参考std::string::replace-cplusplus
- 处理前导 0 操作:定义 flag
-
HZOJ-505:最大整数#
样例输入
3
121 12 96
样例输出
9612121
- 思路
- ⭐保证字符串连接后的字典序最大
- 保证任意 2 个元素的连接,都是前面的字典序大于后面的
- 使用 sort
- 不行的方法
- 按字典序排序 121 12 96 👉 9612112
- 高几位相同判断长度,短的放前 129 12 96 👉 9612129
- ⭐保证字符串连接后的字典序最大
- 代码
-
- string 类可以用 + 自动连接
- 以字符串形式读入
- ❗把 > 改成 >= 在 oj 里第二个 test 会超时
- 两者区别在于 = 的情况返回 true 还是 false,和 sort 排序本身不稳定没有关系~
- ⭐cmp 函数不简单
- 必须满足 Strict Weak Ordering
-
- 简要参考STL sort 的 comp 函数注意事项-CSDN
- 详细参考一次 stl sort 调用导致的进程崩溃- 博客
-
-
HZOJ-508:两人过河#
样例输入
4
1
5
2
10
样例输出
17
- 思路
- 先排序
- 四种情况
- 1 人
- 2 人
- 3 人:最快的人当工具人
- 4 人
- ①传手电的速度保证最快
- ②过桥效率最高(当次快很快、次慢很慢的时候)
- 每次找过两个人的最快情况
-
- 代码
-
- 妙在 2 人 2 人地计算,两种方式取最小
-
HZOJ-509:智力大冲浪#
样例输入
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
样例输出
9950
- 思路
- 排序:扣钱数、时间←结构体
- 先按扣钱数排序(多在前),再按时间排序(少在前)
- 时段标记数组:记录某时段占用情况
- 对于每个任务尽可能靠后去完成
- 排序:扣钱数、时间←结构体
- 代码
HZOJ-518:金币#
样例输入
10
样例输出
30
- 思路
- 两层循环:给多少钱(1 ~ x);天数(1 ~ i)
- 代码
HZOJ-513:楼层编号#
样例输入
14 3
样例输出
12
- 思路
- 枚举虚假楼层(1 ~ m),可以做为真实楼层编号存在则加一
- 有非暴力解法
- 代码
-
- ans 记得初始化~
- if 里只有 ++ 操作时,可以整合
-
HZOJ-514:火柴棒等式#
样例输入
14
样例输出
2
- 思路
- 每个数对应的火柴数是固定的
- 范围估计(最多 24 根火柴)
- 111 + 111 左边最大的数?
- 其实还可以和 0、1 搭配
- 范围会更大:0 ~ 2000
- 加数 1、加数 2 可重复
- 暴力枚举
- 枚举两个加数,看和是否满足要求👈中转函数 + 苦力函数
- 代码
-
- 枚举👉中转👉苦力
-
HZOJ-515:比例简化#
样例输入
1498 902 10
样例输出
5 3
- 思路
- 范围不大,L 上限是 100
- 从小往大枚举
- 两层循环
- 不需要判断互质,如果存在,则前面肯定有满足条件的互质的答案
- 枚举→判断→保留→给出最贴合答案的
- 代码
HZOJ-516:奶牛碑文#
样例输入
6
COOWWW
样例输出
6
- 思路
- 方法一:直接枚举,三层循环?❌过于暴力,O (N ^ 3)
- 方法二:空间换时间
- 对于每个 O,能组成的 COW 数 = 前面 C 的数量 * 后面 W 的数量
- 扫两遍数组,记录 O (N)
- 前缀和:到这个位置为止,有多少个 C
- 后缀和:到这个位置为止,有多少个 W
- 再扫一遍数组,找 O O (N)
- ans + 前 C 数 * 后 W 数
- 时间:O (N) 空间:O (N)
- 引申:统计 PUSH,时间复杂度 O (N ^ 2)
- 扫两遍,统计前缀和 P,后缀和 H
- 找到 U 后,再找 S,计数
- 参考后面代码里的 “同时找” 技巧,应该也能省一个后缀和数组空间,找到 S 后找 U
- 代码
-
- 统计后缀和 “同时找” O,节省了后缀和数组的空间 0
- int 型相乘要注意溢出问题
-
HZOJ-517:三角形个数#
样例输入
10
样例输出
2
- 思路
- 关键在于不能有重复的三角形
- 确定枚举方式,按大小边来枚举
- 短边 i:1 ~ n / 3
- 中边 j:i ~ (n - i) / 2
- 长边:判断 n - i - j < i + j,成立则 ans++
- 定了大小边,可以避免重复
- 关键在于不能有重复的三角形
- 代码
-
- 枚举最短边→次短边,保证不会重复
-
HZOJ-519:优雅数#
样例输入
110 133
样例输出
13
- 思路
- 优雅数:只有一个数字不一样,其余都一样
- 枚举题
- ❌如果直接枚举,再判断是不是优雅数,量太大!10 ^ 16
- 先枚举优雅数YYXYYYYY,再判断是否在区间
- 5 层循环
- 枚举 Y(一堆数)
- 枚举 X(一个数):X 等于 Y 则 continue
- 枚举数长:3 ~ 17
- X 的位置:1 ~ 数长
- X、Y 如果有一个 0,不能有前导 0
- X 为 0,X 不能在第一位;Y 为 0,X 必在第一位
- 构造优雅数,判断是否在区间内
- 代码
-
- 换个角度枚举,很巧妙
- 一个数可由数字组成、数字长度、数字位置决定
-
附加知识点#
- 如果需要定义超大数组或者有其他函数需用到该数组,最好定义为全局变量,开辟堆空间
思考点#
- string str; //cin >> str 等价于 cin >> &str [0]
- ❓涉及到对象的,最好不要使用取址操作
- 这个之后注意
Tips#
课程速记#
- HZOJ-506
-
- 输出时 1.0 提升类型
-