CSDN

trick

2024-06-10 15:12 由 见合 发表于 #后端开发

trick：

  1. \(x\) 与各位数之和模 \(9\) 同余（CF10D）
  2. st表 和 线段树 可以存 gcd（CF10D）
  3. 注意函数增减性（CF1632D）
  4. dp 时若下标太大，可以调换下标和存储的数值（CF1974E）
  5. 贪心不成立时，可以用反悔贪心（CF1974G）
  6. 乘法总是比加法更优（CF1872G）

注意点：

题目部分：

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

代码部分：

  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); 来加速 cin 和 cout。
  12. 数组越界要特判，比如下标从 \(0\) 开始时 i-1 要特判一下。
  13. 循环边界想清楚再写。
  14. 图论时的输入有时从下标 \(2\) 开始读入。
  15. 二分边界不要判错。
  16. 二分时 \(l+r\) 若超出 long long 范围，可以用 \(mid =l+(r-l)/2\) 来写。
  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 的表格打印出来。

算法选择：

数据范围：

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

题目描述:

  1. 最大值最小（最小值最大）：二分、贪心。
  2. 最大得分和最小得分：贪心、dp。
  3. 修改、求区间最大值：线段树、前缀和。

热门相关：傅少，您女友能1打5   女配她逆袭了   自古红楼出才子   妹妹的婚外情   汉阙