CSP/J 集训 Day 1 模拟赛总结

T1:数数

这题就是统计字符串里每个字母出现次数。我写是写对了,但用了 26 个 if-else 硬枚举,代码又臭又长。其实一行 a[c-'a']++ 就完事了。

T2:数列

这题我完全想歪了,以为是 DP,找半天转移方程没找到,后来用堆模拟样例全过,结果数组开小 MLE 爆零。

正解: 前缀和 + 同余。sum[i] = (a[1]+...+a[i]) % k,如果两个前缀和相等,中间那段就能被 k 整除。用 cnt[sum] 记录余数出现次数,遍历时累加即可。

T3:基因

这题本质是斐波那契。长度为 k 的合法串数 f(k) = f(k-1) + f(k-2),取模 12345。

问题:没看出斐波那契

T4:商店

这题要排序 + DP。价格从小到大排,f[i] 表示买前 i+1 件的最小花费。i<k 时只能单买,i>=k 时可以选单买或用促销买最后 k 件付最贵的 2 倍。

T5:爬山

这题我从每个格子出发暴力走,但每次贪心选最高的邻居,这是错的——贪心不一定得到最长路径。正确暴力应该枚举所有路径或加记忆化。满分需要排序 + DP 或拓扑排序。

问题:贪心选最高邻居逻辑不对,样例过了?。

总结

  1. 数组大小按数据范围开,别开小也别开太大。

  2. 贪心、模拟要保证逻辑正确,不能想当然。

  3. 骗分代码要符合题意。

  4. 别急着堆屎山代码,代码越简洁越不容易出错。

  5. 不放过任何得分机会,哪怕感觉没希望也试试。

0 条评论

目前还没有评论...