Trick

Trick：

1. \(x\) 与各位数之和模 \(9\) 同余（CF10C）
2. st表 和 线段树 可以存 gcd（CF10C）
3. 注意函数增减性（CF1632D）
4. dp 时若下标太大，可以调换下标和存储的数值（CF1974E）
5. 贪心不成立时，可以用反悔贪心（CF1974G）
6. 乘法一般比加法更优（CF1872G）
7. ‘(‘ 看成 \(+1\)，’)’ 看成 \(-1\) （CF1976D）
8. atan2 可以求角度 （CF257C）
9. 正难则反（容斥原理）（CF803F）
10. 抓住数据的特殊性质（如 \(10^18\) 等极端数据）（CF468C）
11. 可以贪心+dp（贪心推性质，用 dp 做），经典单调队列优化 (CF797F)
12. 可以先取一个特殊点来做，通过特殊点的特殊性质来解题 (CF1559D2)
13. 数据很大时，可以考虑能否缩小范围，后面特殊处理 (CF1956E2)
14. 位运算可以在二进制下一位一位考虑。

注意点：

题目部分：

1. 数组范围 注意不要开错（记得修改缺省源）。
2. 并查集 数组要开 两倍。
3. 翻译 看不懂的话要自己翻。
4. 题目中 没用的信息 跳过不看。
5. 子串 和 子序列 看清楚！
6. 排列 有特殊性质。
7. 要看 样例解释 。

代码部分：

1. 多测 不清空，爆零两行泪。
2. dp 初始化 不要忘记（最好设成 LONG_LONG_MAX 或 LONG_LONG_MIN！）。
3. memset 最好 不要用，复杂度高，容易超时。
4. 判断 相等 应是 ==。
5. max 和 min 中前后的数据类型要相同。
6. 不能随意 开 long long，可能爆空间。
7. 看数据范围， 不开 long long 见祖宗！
8. long long 也不够了用 __int128，或手写 高精。
9. vector 最好 不要直接排序，复杂度高，可以用 索引 来排序。
10. 注意算术优先级（加 括号 ）！
11. 交互题记得输出后要 清空（fflush(stdout);），并且不要用 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 来加速。
12. 数组 越界 要特判，比如下标从 \(0\) 开始时 i-1 要特判一下。
13. 循环 边界 想清楚再写。
14. 图论时的输入有时从下标 \(2\) 开始读入。
15. 二分 边界 不要判错。
16. 二分时 \(l+r\) 若超出 long long 范围，可以用 \(mid=l+(r-l)/\) 来写。
17. cf 的题 不要 写 unordered_map，只能用 map，因为有些大佬卡掉了 unordered_map。
18. 提交时记得 删去 调试信息！
19. string 类如果写了 s=" "+s; 之类，n=s.size() 应写在前面。
20. st表要调用 log 的 预处理！！

debug 部分：

1. 样例 输入不了，可能是 Dev-C++ 死机了，可以打开 洛谷在线 IDE 或其他网站来写。
2. 如果用了 while(cin>>n) 之类的输入，程序运行无法终止。如果输入的类型是 整数，常用的办法是换行后输入 \ 或者什么 字母，这样输入就会停止了，并且有输出。或者 在循环中特判 \(n\) 为 \(-1\) 时结束，自己手动输入 \(-1\) 即可。提交时记得 删去。
3. 没有输出，可能是死循环了。把 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 注释掉，之后在递归里 输出 每次的值。
4. dp 值不对，可以将 dp 的表格 打印 出来。
5. 如果是交互题，可能是样例本身不是最优。

算法选择：

数据范围：

1. \(n \le 20\) 时，考虑 暴力搜索 或 状压 dp。
2. \(n \le 40\) 时，考虑 meet in the middle 或 状压 dp 优化。
3. \(n \le 10^2\) 时，考虑 dp。
4. \(n \le 10^3\) 时，考虑 暴力枚举。
5. \(n \le 10^5\) 时，考虑 贪心 优化 dp。
6. \(n \le 10^9\) 时，考虑 二分 和 数学。
7. \(n \le 10^{18}\) 时，考虑 数学。

原文链接：Trick