脑弹寄录
5k_sync_closer
·
·
个人记录
部分分看全，认真想每一档（春测 T4 忘了贪 k=2）
强制在线要记 lastans 和异或 lastans（省选模拟赛）
状压下标从 0 开始，大于 30 位开 long long（省选模拟赛）
看清每个变量什么意思（省选模拟赛）
好好读题，模拟样例后再写题（省选 D1T3，D2T2 连读错两题）
统计转贡献不仅可以计数（求满足某条件的数之和），而且可以求最值（求满足某条件的数的最值）（PKUSC D1T1 场寄）
线段树 lazy tag 下传完要清空，整体修改的时候要改，多测所有节点的 lazy tag 都要清空
无返回值函数必须是 void 型的，这个在 O2 下可以 100\to 0（模拟赛）
开数组之前想好要用多大，一定要记得 +50，写完必须检查一遍每个数组的大小（模拟赛）
背包记录方案可以滚动数组。（模拟赛）
数位 DP 尽量避免 memset，如求 popcount=k 的数的个数，令状态为 f_{i,j} 表示填到 i 位，后面还要填 j 个 1 的方案数即可避免在不同 k 之间 memset。（模拟赛）
平衡树维护集合，不能直接把初值 merge 起来，正确做法是先排序再依次 merge。（模拟赛）
最大 / 最小值的初值要根据被统计元素的取值范围设定，不要设大 / 设小。（模拟赛）
时刻记得取模，尤其是 `f[i] = (......) % M` 的形式。（模拟赛）
还有 `... * ... % M * ... % M * ... % M` 的形式。（模拟赛）
只保证互质，不保证质数，不能用费马小定理求逆元。
注意边界，比如是否出现负数下标。（模拟赛）
DFS 记得回溯。（模拟赛）
考虑如下代码：
```cpp
struct node
{
int x, y, lazy;
};
node operator+(node a, node b)
{
node q;
q.x = a.x + b.x;
q.y = a.y + b.y;
return q; //q.lazy 未初始化！
}
```
一定要仔细检查样例输出是否正确，比如是否少输出了操作步数。（模拟赛）
`__lg(0)` 会寄。（模拟赛）
------------
开始打省选模拟赛之后好像就没更过了，现在更一下
不熟（只知道原理，几乎没写过）的东西不要到考场上嗯造，造不出来很亏。（模拟赛）
自信即巅峰，数组往大开，万一跑过了呢（当然还是手造一组数据验证一下更稳）。（模拟赛）
注意细节，对于贪心 / 构造题，时间充裕时尽量手动模拟一下程序的行为与预期是否相符。（模拟赛）
写一行代码之前先想想自己要写什么，避免因为 ** 错误耗费大量调试时间。（AT）
**在不犯 ** 错误的前提下尽量提高码速。不要太相信自己的代码能力，用最快速度写，留足试错时间（模拟赛）**
不要花巨量时间写一个复杂度危险的算法（比如 $n\le 2000$ 写平衡树 $O(n^2\log n)$，或者 $n\le 10^5$ 写 $O(n\log^3 n)$），最后很有可能只得暴力分。
老毛病，部分分看全，认真想每一档（第一条，模拟赛又犯了一遍）
时间充裕的情况下，对于期望能过的部分分，造几组极限数据，看看是不是真的能过。（模拟赛）
倒序遍历 `vector`，不要写：
```cpp
for (int j = P[i].size() - 1; j >= 0; --j)
```
应该写：
```cpp
for (int j = (int)P[i].size() - 1; j >= 0; --j)
```
因为 `P[i]` 可能是空的。
如果觉得自己写的很对但就是不对，也调不出来，就再读一遍题，特别注意模数，特殊性质之类的内容。（模拟赛）
树上背包错误写法：
```cpp
s[u] += s[v];
...
for (int x = 0; x <= s[u]; ++x)
for (int y = 0; y <= min(x, s[v]); ++y)
// 算 f[x]
```
（来条链就似了）
树上背包正确写法：
```cpp
for (int x = 0; x <= s[u] + s[v]; ++x)
for (int y = max(x - s[u], 0ll); y <= min(x, s[v]); ++y)
// 算 f[x]
...
s[u] += s[v];
```
或者刷表法：
```cpp
for (int x = 0; x <= s[u]; ++x)
for (int y = 0; y <= s[v]; ++y)
// 算 f[x + y]
...
s[u] += s[v];
```
~~（大样例不给链是什么心理？~~
自测用时的时候要用**极限数据**，不要用**卡满数据范围但没卡满复杂度的随机数据**
**开数组之前想好要用多大，一定要记得 +50，写完必须检查一遍每个数组的大小（模拟赛），即使很急也必须检查，必须检查，必须检查，特别注意n 1e5 m 2e5 之类的情况 m 个数的数组有没有开够 2e5**
左移超过位数上限是 UB，无符号也一样（不会自然溢出）。
**所有代码都要开 Wall，ubsan,addresssan 跑一遍！！! address 一定要开！！！**
**一定要仔细考虑 corner case。常见 corner case：无解，0，n+1，DP 初始状态，上界，下界**
超过 32 个偶数的乘积模 $2^{32}$ 等于 0。**这个不仅可能是题目的突破口，还可能是挂分的原因。**
h. OJ 上，使用的内存最好不要超过空间限制的一半。
天天挂 freopen，也是没救了。
__int128 不能当数组下标。
读完题标一下重要信息（容易读错的信息，比如最大值/最小值），防止思考过程中记错题面。
不要瞎猜一个东西有决策单调性，过了大样例也要拍，
能同复杂度数据结构优化就没必要考虑决策单调性优化。
**证不出正确性，也感觉不太对的做法，一定记得要拼暴力，即使过了大样例也要拼暴力。**
windows 下 new 一个数组之后里面没有初始化，并不是全 0。
swap 两个长度为 $n$ 的数组复杂度是 $O(n)$ 的。
ST 表小的那一维永远都要开在前面。
**没测极限数据之前，永远不要觉得自己的代码能跑进时限。**
警惕 auto 开出来的变量，auto x = 0 是 int 型的，即使 define int long long 了也是 int 型的
警惕 `memset(f[i], 0, sizeof f)`
**可撤销并查集不能路径压缩！！！这个很容易顺手写错！！！带可撤销并查集的题调不出来第一时间检查这个！！！**
想到一个做法 A（能达到目的，但可能有缺点，比如常数大/比较难写）之后，如果十分钟/二十分钟内想不到更好的能达到相同目的的做法 B，那直接开写做法 A，犹豫就会败北。
树上距离相关问题，记得考虑点分治/点分树。
长为 1 的 FFT 可能因为左移 -1 而爆炸。
**不要死磕 T1。**
IFFT & IFWT 单位根记得求逆，记得除以 n
写标记永久化的时候，一定要想清楚，什么时候考虑标记的贡献，什么时候不考虑
树上 DFS 传父亲的时候，如果点的标号从 0 开始，那么根的父亲应该传 -1 而不应该传 0
**不是计数题的题一定要注意有没有模数，警惕样例答案全部小于模数的情况**
**windows 下有自动补头文件的风险，最好用万能头，并且在 linux 下测一遍**