官方题解 | 欢乐赛#79题解
赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 皓仔的商场折扣 入门 T2 皓仔的周末活动 入门 T3 皓仔的极差筛选 入门 T4 皓仔的数字统计 入门 T5 皓仔的质数公约数 普及- T6 皓仔的回文子串 普及-
T1 皓仔的商场折扣
题意简述
已知三件物品的价格分别为 aaa 元、bbb 元、ccc 元，商场本次活动的折扣为 *** 折。
先计算三件物品的总价，再按照折扣计算最终需要支付的金额，并将结果保留 222 位小数。
解题思路
三件物品的原价总和为：
(a+b+c)(a+b+c)(a+b+c)
*** 折表示按照原价的 d10\dfrac{d}{10}10d 支付，因此最终需要支付的金额为：
(a+b+c)×d10(a+b+c)\times\dfrac{d}{10}(a+b+c)×10d
由于价格和折扣都可能包含小数，因此使用 double 类型存储。
最后使用 printf("%.2f", ans) 将答案保留 222 位小数输出。
时间复杂度为 O(1)O(1)O(1)，空间复杂度为 O(1)O(1)O(1)。
参考代码
T2 皓仔的周末活动
题意简述
皓仔需要在电影、篮球和阅读三个活动中选择一个。
每个活动的总时间等于交通时间加上活动时间。
分别计算三个活动的总时间，并输出其中最小的一个。
解题思路
三个活动的总时间分别为：
a+ba+ba+b
c+dc+dc+d
e+fe+fe+f
只需要分别计算这三个结果，再使用 min 求出最小值即可。
时间复杂度为 O(1)O(1)O(1)，空间复杂度为 O(1)O(1)O(1)。
参考代码
T3 皓仔的极差筛选
题意简述
给定一个长度为 nnn 的整数数组。
数组的极差定义为：
max(a)−min(a)\max(a)-\min(a)max(a)−min(a)
先求出数组的极差，然后按照原输入顺序输出所有严格小于极差的元素。
如果不存在满足条件的元素，则输出 -1。
解题思路
先遍历一遍数组，求出其中的最大值和最小值。
设极差为：
range=maxn−minnrange=maxn-minnrange=maxn−minn
然后再次按照原顺序遍历数组：
* 如果 a[i] < range，就输出该元素；
* 使用一个标记变量判断是否至少输出过一个元素。
如果最终一个满足条件的元素都没有找到，则输出 -1。
时间复杂度为 O(n)O(n)O(n)，空间复杂度为 O(n)O(n)O(n)。
参考代码
T4 皓仔的数字统计
题意简述
给定一个 nnn 行 mmm 列的二维整数数组。
对于每一个出现过的数字 xxx，如果它一共出现了 ccc 次，那么它的统计结果为：
x×cx\times cx×c
求所有出现过的数字中，最大的统计结果。
解题思路
由于数组中的数字范围为 0∼10000\sim10000∼1000，可以直接使用数组 cnt 统计每个数字出现的次数。
读入每个元素 x 时：
* 执行 cnt[x]++，记录它的出现次数。
全部读入完成后，枚举 0∼10000\sim10000∼1000 中的每个数字 xxx，计算：
x×cnt[x]x\times cnt[x]x×cnt[x]
并维护其中的最大值即可。
时间复杂度为 O(nm+1000)O(nm+1000)O(nm+1000)，空间复杂度为 O(1000)O(1000)O(1000)。
参考代码
T5 皓仔的质数公约数
题意简述
给定 nnn 个整数，需要找到一个最大的质数 ppp，使得这 nnn 个整数都能被 ppp 整除。
如果不存在这样的质数，则输出 -1。
解题思路
如果一个质数能够同时整除所有数字，那么它一定也是所有数字最大公约数的质因数。
因此可以先求出所有数字的最大公约数：
g=gcd(a1,a2,…,an)g=\gcd(a_1,a_2,\ldots,a_n)g=gcd(a1 ,a2 ,…,an )
然后对 ggg 进行质因数分解。
从 222 开始枚举因数，如果发现 iii 能整除 ggg，说明 iii 是一个质因数，将答案更新为 iii，并不断除去这个质因数。
最后如果剩下的 g>1g>1g>1，说明剩余的 ggg 本身也是一个质数，需要继续更新答案。
如果最终没有找到任何质因数，说明所有数字的最大公约数为 111，不存在质数公约数，输出 -1。
时间复杂度为 O(n+g)O(n+\sqrt{g})O(n+g )，空间复杂度为 O(1)O(1)O(1)。
参考代码
T6 皓仔的回文子串
题意简述
给定一个长度为 nnn 的字符串 sss。
对于每一个非空连续子串，可以修改其中至多 kkk 个字符，使其变成回文串。
求一共有多少个子串满足条件。
解题思路
对于一个子串 s[l…r]s[l\ldots r]s[l…r]，想要将它变成回文串，只需要比较首尾对应位置的字符。
如果：
s[l]=s[r]s[l]=s[r]s[l]=s[r]
那么这一对字符不需要修改。
如果：
s[l]≠s[r]s[l]\neq s[r]s[l]=s[r]
只需要修改其中一个字符，就可以让这一对字符相同，因此需要增加 111 次修改。
设 dp[l][r] 表示子串 s[l…r]s[l\ldots r]s[l…r] 变成回文串最少需要修改多少个字符。
则有：
dp[l][r]=dp[l+1][r−1]+[s[l]≠s[r]]dp[l][r]=dp[l+1][r-1]+[s[l]\neq s[r]]dp[l][r]=dp[l+1][r−1]+[s[l]=s[r]]
其中，当 l≥rl\geq rl≥r 时，子串长度不超过 111，本身就是回文串，需要修改 000 次。
按照子串长度从小到大计算所有状态。每得到一个 dp[l][r]，如果：
dp[l][r]≤kdp[l][r]\leq kdp[l][r]≤k
说明这个子串可以在至多 kkk 次修改后变成回文串，将答案加 111。
字符串长度最大只有 200200200，因此使用区间 DP 可以轻松通过。
时间复杂度为 O(n2)O(n^2)O(n2)，空间复杂度为 O(n2)O(n^2)O(n2)。
参考代码
