今天在图灵打了国庆模拟赛 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 是难题,不会也正常,但可以尝试暴力。

经验教训:

    1. 看到变换题,先想数学性质,别急着模拟。
    1. 能骗分就骗分,但骗分代码也要符合题意。
    1. 数组大小按数据范围开,别开小也别开太大。
    1. 贪心、模拟要保证逻辑正确,不能想当然。
    1. 别急着堆屎山代码,代码越简洁越不容易出错。
    1. 不放过任何得分机会,哪怕感觉没希望也试试。

洛古的咋和这个不一样?

2 条评论

  • 1