- 图灵
CSP/J 集训 Day 2(怎么发讨论区a QwQ
- @ 2026-10-3 20:36:36
今天在图灵打了国庆模拟赛 Day2,赛后总结一下。
T1:最大公约数
这题要在 1 ~ n 里找两个不同的数,让 gcd 最大。我一眼就看出来了:取 n/2 和 n(或者 n/2 和 2*(n/2)),最大公约数就是 n/2。直接输出 n/2 就完事了。
结果:AC,100 分。
反思:这题是签到题,没什么好说的,但能快速看出来也是好事。
T2:子串
这题要找多少个子串,把小写字母转大写后恰好等于 "NHOI"。长度固定为 4,所以枚举所有长度为 4 的子串,逐字符转大写比较即可。
结果:AC,100 分。
反思:这题也不难,但要注意边界 i+3 < n,我写的是 i+3<n,实际上应该是 i+3 <= n-1,也就是 i+3 < n 是对的(因为下标从 0 开始)。没出问题。
T3:数的变换
这题有三种操作:
2 | n:n ← n/2
3 | n:n ← 2n/3
5 | n:n ← 4n/5
我写的是模拟变换过程:每次优先做 n%20,再做 n%30,再做 n%50,直到 n1 或做不了为止。
问题: 这样模拟出来的次数不一定是最少的,而且顺序影响结果。比如 n=27,模拟出来是 6 次,刚好对;但有些情况模拟出来的不是最优。
正解:统计 n 中因子 2、3、5 的个数,设 n = 2^a · 3^b · 5^c,如果还有其他质因子输出 -1,否则答案 = a + 2b + 3c。
结果:AC
反思:这题本质上不是模拟,而是数学推导。下次看到这种变换题,先想想能不能直接算,别急着模拟。
T4:回文
这题要把字符串变成回文,可以交换一次(免费),然后变换字母(代价只和目标字母有关)。
我直接 cout << 0 ; 骗了 10 分。
正解:统计不匹配对,枚举交换两对,计算交换后的代价。具体来说:
对于每对 (i, n-1-i),如果不匹配,代价是 min(v[s[i]], v[s[n-1-i]], 2*min_v)
枚举交换两对不匹配的字母,看能否减少总代价
结果:10 分(傲娇) (骗分) 。
反思:这题要仔细分析。下次遇到这种题,先想清楚再写,别直接骗分。
T5:序列
这题完全不会,没骗上分。
正解:数位 DP + 异或性质。要求序列和 sum 在 [l, r] 之间,异或和为 z。这题比较复杂,需要用到数位 DP 和组合数学。
结果:0 分。
反思:这题难度较高,不会也正常。但至少可以写个暴力枚举,说不定能骗点分。
总结
T1、T2 是签到题,必须拿满,我做到了。
T3 是数学题,不是模拟题,我方向错了。
T4 是贪心 + 枚举,我直接骗分,有点亏。
T5 是难题,不会也正常,但可以尝试暴力。
经验教训:
-
- 看到变换题,先想数学性质,别急着模拟。
-
- 能骗分就骗分,但骗分代码也要符合题意。
-
- 数组大小按数据范围开,别开小也别开太大。
-
- 贪心、模拟要保证逻辑正确,不能想当然。
-
- 别急着堆屎山代码,代码越简洁越不容易出错。
-
- 不放过任何得分机会,哪怕感觉没希望也试试。
洛古的咋和这个不一样?