说是总结这个东西很有帮助，所以就写一下。
开题
先看了一遍感觉前三题还有希望，第四题直接寄了，期望根本就不会，还是自己太菜。
T2 比较难看，T3 感觉像裸的分组背包，T1 看着好些，直接开题。
开写
T1 很明显的前缀和维护，然后就去想双指针考虑单调性，发现既然是求余数怎么可能有单调性。然后突然想到由于 \(sum_{[l,r]}=sum_{[1,r]}-sum_{[1,l-1]}\) 这种减法式子，所以对于 \(sum_i\) 直接求 \(sum_i\equiv sum_j(\mod k)\) 即可，开个 map 统计个数（然而并不需要离散化）。
样例飞了，但是感觉自己应该是正解，然后发现多测忘记清空，所以直接手动循环清空 map（因为不知道 .clear()，这里注意），预计 100pts。
T2 觉得不是 lca，看到区间操作就又想到线段树，但是应该是无法整体搞的，所以又换想法。搞了半天题目发现是贪心，应该让叶子结点的加数尽量大，但是推到一半不知道怎么样自己给自己证伪了，此时已经经过 2h，打算先去写 T3，但是事实证明，不管有没有证伪，再重新推一遍都是非常有必要的，因为我要是再推一遍应该就是正解了，预计 0pts。
实践告诉我们，先把题目仔细读一遍比先把代码写下来重要许多，T3 其实并不想看起来那样是个板子，裸的分组背包板子应该是每组只能选一个，但是这里只是每组有重量限制而已。好像有个哥们把板子敲完了然后在那里咒骂。
觉得是分组套一个 01，但是因为这个重量限制不知道第二层循环的区间到底怎么开。
for (int i = () -> ()) {
for (int j = () -> ()) { // 就是这里
dp[j] = max (dp[j] ,dp[j - w[i]] + v[i]) ;
}
}
发现有 \(2\) 个点是每组的重量限制要大于总的重量限制，那么这些重量限制就没用了，可以直接写一个暴力 01 打算搞到 10pts 滚蛋。
象征性看看 T4，发现有 40-60pts 是暴力分，挺高兴，然后突然意识到自己期望不会求连暴力都写不了。于是考场手推（乱糊）期望式子，但是好像把正解公式推出来了？？？那也没用，还是不会。
仔细检查一下 T1，应该 long long 没问题，也不会 MLE，应该是 100pts 稳切。
之后就挣扎 T3，没成。
然后就在 T2 和 T3 之间反复横跳，考试结束。
出分
只有总分，75pts 当时整个人都震惊了，现在回忆也感觉可怕。
出题解和小题分
怎么也想不到 T1 T 了，挂 70pts，原因是每次手动清 map 导致多跑了 \(1\times 10^6\) 次，发现只要把 map 定义成局部变量就过了......
好像是 map 内存和常数都比较大，不如 unordered_map，还有就是一直 memset 会寄，另，其实清空只要把上一次用到的和这一次要用的的交集用循环清掉即可。
T3 45pts 高于预期，正解已经差不多想出来了，该死。其实只要按照组别重量限制做 01 背包之后再打一个 dp，设 \(dp_{i,j}\) 表示前 \(i\) 组重量最多是 \(j\) 的数目，这样暴力就可以碾过，发现自己缺少勇气，而且不太会卡。
T2 也差不多想到正解，笑死。就是贪心。显然符合条件的加数越大越好，只要 dfs 递归求解就行了，很好写，查茶大佬说是树剖，吓我一跳，其实和树基本没有关系。
T4 期望是真的不会，但是发现自己已经可以手推公式。这样以后就敢推了，数学题应该比较擅长才对？费马小定理也会。
总结
首先写完第一件事算复杂度和空间，复杂度比较好算，只用手动计算机子要跑多少次就可以了，学到一个好方法就是去测极端数据，既然能卡过极限应该就是正解了。还知道了一个叫做对拍的东西，防止数据过水很好用。
空间是自己以前不太会注意到的东西，也终于知道了以前大佬们的那么在意时间限制是干肾摸的，具体算法：
- 若要换算成 mb，则用数组大小除以 \(1024^2\)。
- 换算成 kb 则是除以 \(1024\)。
还有 map 不是好东西。
之后又注意到题目时间限制这个东西，查了一下，一般 ccf 老爷机每秒可以跑 \(5\) 亿，但是仅限于 \(\mathcal{O}(n)\)。
\(\mathcal{O}(n\log n)\) 可过 \(5\times 10^6\)。
\(\mathcal{O}(n\sqrt n)\) 可过 \(5\times 10^5\)。
\(\mathcal{O}(n^2)\) 只有 \(5000\)。
\(\mathcal{O}(n^3)\) 降到 \(300\)。
\(\mathcal{O}(2^n)\) 只有 \(25\)（我想到了为什么双向搜索可以优化暴搜）。
\(\mathcal{O}(n!)\) 是可怜的 \(11\)。
我发现上述的复杂度的理想极限小于机子每秒极限，因为有个东西叫做常数。
所以一道题目如果时间限制是 i(s)。那么大概就是 \(5\times i \times 10^8\)，而一般题目时限大概率是 1s。
还有就是发现自己已经逐渐可以想到正解，就差实现和完善了，想法不太细，看官方后有恍然大悟的感觉，其实自己应该完全可以想到，多打模拟赛。
本场比赛再次挂分，但是这次不同于其他，这次是因为平时的不好的习惯（如使用 map，其实就连离散化也不需要它）导致爆炸。
容易自我质疑然后证伪，但是就这次来说，能够手推公式对我来说是一个启发，其实我完全可以去砸结论的。
比赛题目链接挂上：https://www.xinyoudui.com/ac/contest/774001BAC0004100250F826/problem/1753
标签：map,模考,sum,T3,times,2024,mathcal,友队,dp From： https://www.cnblogs.com/Tomoyuki-Mizuyama/p/18314647