官方题解 | 欢乐赛#75题解
赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 皓仔卖蜂蜜 入门 T2 皓仔加油 入门 T3 皓仔找不同 入门 T4 皓仔的十六进制矩阵 入门 T5 皓仔的回响数 普及- T6 皓仔的字符串修剪 普及-
T1 皓仔卖蜂蜜
题目大意
已知每个礼盒需要放入 aaa 瓶蜂蜜。现在皓仔一共有 nnn 瓶蜂蜜，他会尽可能多地把蜂蜜装成完整的礼盒。
请你帮皓仔计算：装完所有能装成礼盒的蜂蜜后，还会剩下几瓶蜂蜜。
题解思路
nnn 瓶蜂蜜， 每个礼盒需要装 aaa 瓶， 问最后剩下几瓶， 这个问题也就是问数字 nnn 除以 aaa 之后的余数是多少， 因此答案直接输出 n%an \% an%a 即可。
参考代码
T2 皓仔加油
题目大意
已知皓仔身上一共有 xxx 元钱，当前油价为每升 ppp 元，汽车油箱最多可以装 vvv 升油。
皓仔想尽可能多地加油，但是加油量不能超过油箱容积。
请你计算皓仔最多可以加多少升油。
题解思路
假如将身上所有的钱都拿去买汽油， 则可以买到 x/px / px/p 升汽油， 但是需要注意油箱最多只能装 vvv 升油，因此最多可以加的油量需要在二者中取一个较小值。
也就是当 x/p≤vx / p \le vx/p≤v 时候， 输出 x/px / px/p，否则输出 vvv。
参考代码
T3 皓仔找不同
题目大意
给定一个长度为 nnn 的数组。
这个数组中，有且只有一个数字和其他所有数字不同，其余 n−1n-1n−1 个数字都是相同的。
现在请你找出这个特殊数字所在的位置，输出它的下标。
数组下标从 111 开始。
题解思路
给定的数字在数组中固定只出现一次， 因此可以从前往后遍历数组， 对于每一个长度为 333 的相邻数字段， 看是否存在一个数字与另外两个数字不同。
变量 iii 循环遍历从 111 开始到 n−2n - 2n−2 结束，每次遍历相邻的 333 个数字 a[i],a[i+1],a[i+2]a[i], a[i + 1], a[i + 2]a[i],a[i+1],a[i+2]， 只要其中某个数字和另外两个数都不相同，就是我们要找的答案， 输出对应下标即可。
参考代码
T4 皓仔的十六进制矩阵
题目大意
给定 nnn 行 nnn 列的表格，每个位置上都是一个十六进制字符。
十六进制字符包括：
* 0 到 9
* A 到 F
其中，字符 0 到 9 分别表示数值 000 到 999，字符 A 到 F 分别表示数值 101010 到 151515。
现在请你计算两个十进制结果：
* 所有行的总和中，最大的那一个行和；
* 所有列的总和中，最大的那一个列和。
题解思路
本题中可以不用专门开二维数组记录完整的表格， 只需要开两个数组 row[]， col[] 用以记录每一行每一列的总和。
例如 row[i] 表示第 iii 行的总和， col[j] 表示第 jjj 列的总和。
两重循环遍历表格的每一个位置 (i,j)(i, j)(i,j) ，输入对应的十六进制字符 xxx 并且转化成对应的数值:
* 当 xxx 为数字字符时， 对应的数值 ccc 为 x - '0';
* 当 xxx 为大写字母时候， 对应的数值位 x - 'A' + 10；
然后将该数值累加到所在行和所在列的数组中，也就是 row[i] += c, col[j] += c；
最后完整遍历所有行和所有列， 求出最大的行总和，以及最大的列总和即可。
参考代码
T5 皓仔的回响数
题目大意
如果一个正整数的十进制表示可以写成 ababab... 的形式，也就是由同一个两位数字片段不断重复组成，且两个数字不同，那么皓仔就称它为“回响数”。
例如：
* 1212 是回响数，因为它可以看成 12 重复了 222 次；
* 343434 是回响数，因为它可以看成 34 重复了 333 次；
* 9090 是回响数，因为它可以看成 90 重复了 222 次；
* 1234 不是回响数。
特别地，回响数的位数必须是偶数，并且至少有 444 位。也就是说，像 12 这样的两位数不算回响数。
现在给定两个整数 l,rl,rl,r，请你统计区间 [l,r][l,r][l,r] 中一共有多少个回响数。
题解思路
注意到数据范围中 r−l≤106r - l \le 10^6r−l≤106， 也就是说虽然值域非常大ai≤1018a_i \le 10^{18}ai ≤1018， 但是所有需要我们判断的数字数量只有 10610^6106 个。
因此可以枚举 lll 到 rrr 范围内的所有数字， 进行数位分解， 判定是否是回响数， 是的话答案加一。 最后输出回响数个数就好。
本题的另一种解法是枚举所有的 ab的可能，并且进行重复拼接得到所有的回响数，可以得到总的回响数个数是较少的。枚举所有的回响数看是否在 [l,r][l, r][l,r] 区间内即可。
参考代码
T6 皓仔的字符串修剪
题目大意
皓仔拿到了两个字符串 sss 和 ttt。
他可以对每个字符串进行若干次删除操作，每次只能删除当前字符串最左端或最右端的一个字符。
也就是说，经过若干次操作后，字符串中剩下的部分一定是原字符串中的一个连续子串。
皓仔希望通过删除操作，使得两个字符串最后剩下的内容完全相同。请你求出最少需要删除多少个字符。
如果两个字符串没有任何公共字符，也可以把两个字符串都删空，此时剩下的内容都为空串，也是剩下内容完全相同的情况。
题解思路
本题问最少删除多少个字符可以使得剩余的子串相等， 因此问题可以转化成两个字符串 s,ts, ts,t 的最长公共子串有多长。
因此可以枚举 sss 的所有子串， 并且在 ttt 中寻找该子串是否出现过， 出现过的话则该子串可以认为是两者的公共子串。
获取 sss 的子串这一操作可以直接使用成员函数 substr 获取， 在 ttt 中查找子串是否出现过可以直接使用成员函数 find来获取。
参考代码
