Bo2SS

Bo2SS

3 OJ题目讲解

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
      • 判断要开的数组大小
  • 代码
    • 图片
    • 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
  • 代码

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 层循环
      1. 枚举 Y(一堆数)
      2. 枚举 X(一个数):X 等于 Y 则 continue
      3. 枚举数长:3 ~ 17
      4. X 的位置:1 ~ 数长
        • X、Y 如果有一个 0,不能有前导 0
        • X 为 0,X 不能在第一位;Y 为 0,X 必在第一位
      5. 构造优雅数,判断是否在区间内
  • 代码
    • 图片
    • 换个角度枚举,很巧妙
    • 一个数可由数字组成、数字长度、数字位置决定

附加知识点#

  • 如果需要定义超大数组或者有其他函数需用到该数组,最好定义为全局变量,开辟堆空间

思考点#

  • string str; //cin >> str 等价于 cin >> &str [0]
  • ❓涉及到对象的,最好不要使用取址操作
    • 这个之后注意

Tips#


课程速记#

  • HZOJ-506
    • 图片
    • 输出时 1.0 提升类型
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。