一些思路

  • 有些题直接做并不好做，想想能不能转化一下模型。
  • 莫队在按右端点排序的时候可以通过左端点所属分组奇偶性减少一半计算量
    • return bel[a.l]==bel[b.l]?(bel[a.l]&1?a.r<b.r:a.r>b.r):a.l<b.l;
  • 对一个有向图Tarjan缩点后图的一个拓扑序是强连通分量生成顺序的逆序。
  • 发现DP转移复杂度很高时，可以想一下缩小转移步长（如逐行转移 -> 逐格转移）
  • 就算是博弈论也可以二分答案转成01问题的
  • 在排列上寻找多项式时间算法
    • 枚举最后/最大的那个点在哪里
    • 在不关心顺序的时候可以像背包一样做
    • 画出二维图表方便进行分析？
  • 值域很大（甚至爆double）的时候可尝试取log，可能因此启发思路（BJOI2019奥术神杖：分数规划）
  • 区间最大差问题可以拆开讨论
    • max(a.max,b.max)-min(a.min,b.min)=max(a.max-b.min,b.max-b.min,a.max-a.min,b.max-b.min)

做题流程

  1. 多花点时间读题，手算样例确保（也不一定）正确理解题意
  2. 检查并记录数据范围和模数（1e9+9?1e8+7?）
  3. 评估做法时空复杂度
  4. 静态查错
    1. 检查多组数据
    2. 检查初始化（包括但不限于常量含义与常量是否够大（比如数组长度老忘记+5），网络流cnt，memset，多组数据清空）
    3. 检查数据类型（值，数组正确性）
  5. debug边界数据（对拍小数据，测试极限数据（最小、最大）：数组大小？整数越界？）
    1. gdb到一定时间后停下来冷静思考一下自己的模型，考虑重构或放弃（尤其是大代码/乱搞/细节题）
  6. 检查(模数)算术越界(+,-,*都要)，看看有没有需要用(unsigned) long long
  7. 检查主程序与暴力的公共部分
  8. 检查内存大小
  9. 注释掉提交程序中的调试信息(assert,eprintf)
  10. 检查文件读写，编译提交程序,快到考试结束时重新检查提交程序（版本，编译）

对拍和检验

  • 不要迷信std
  • 不要利用未定义行为，老老实实写特判。
  • 如果调试信息错得离谱，检查调试输出打对了没。
  • gdb±ftrapv 可以快速定位爆int的位置。
  • 如果本机AC提交莫名RE或TLE,检查#ifndef ONLINE_JUDGE和数据初始化
  • 过了undefined检查不代表没有越界，函数传long long 到int等都不是未定义行为。
  • 认清1e9+9,1e9等模数
  • 计算空间时记得找static变量一起算
  • 发现复杂度不对时可以检查一下循环，看看有没有空跑
  • 用fwrite出现OLE其实很可能是RE(比如flush时head没赋回初值)
  • GDB的行为不总是和程序相同
    • 内存越界
    • 调用cmath中的函数
    • 在部分有符号整数和无符号整数运算时可能会转成有符号整数(比如调用STL的size函数)，而gcc程序会转成无符号整数(GCC: 0<0-vector.size(), GDB: 0>0-vector.size() (vector.size>0))
  • 当出现接近满分的WA的时候，可以检查是不是哪里整数越界了
  • 函数return的值和想象中的不一样时，检查是不是从别的地方return了。
  • 开-O2之后的错误检查会比不开-O2严格很多，可以在-O2下编译查错。
  • GDB出现"previous frame identical to this frame (corrupt stack?)"是因为内存越界覆盖了栈信息。
  • GDB的bitset运算是假的，但是读取没问题
  • 数据千万条，清空第一条，多测不清空，爆零两行泪。

STL & 数据结构

  • 左偏树不要无脑并查集。
  • map在查询不存在的值时也会新建一个节点。
  • set中不要存储卫星信息
  • 树剖跳k级祖先时记得算上fa[]的步数
  • 不是所有的长,重链剖分暴力跳top的复杂度都是对的(比如按边权剖分)
  • 李超线段树维护线段时要把线段当参数传入递归(一次更新中，要拿来更新区间的线段并不总是一样)
  • 树上维护信息时不要省去某些要特判的信息，区间操作的时候可能出现问题(XSY3472,区间gcd)
  • LCT的access之后都要splay，否则时间复杂度不对
  • std::nth_element()的顺序是(begin(),nth element,end())而不是(begin(),end(),nth element)
  • 替罪羊树重构常数alpha记得用double存

其它问题

  • 做有膜数的题的时候不要允许负数的存在，否则可能会有tag[x]>1之类的坑，也不好判断是否有整数越界
  • 网络流cnt=1。
  • 网络流一定要加当前弧优化，要不然分分钟被卡出40多倍的常数……
  • memset()时注意开始位置和sizeof()什么。(几次挂在memset(val,0,n*sizeof(val))和memset(val+1,0,sizeof(val)))
  • 写读入函数时检查输入是否有负，小数。
  • 做有膜数的题记得判负和检查有没有int * int（防爆int）
  • 对于double不够精确的地方，可以转成整数之后微调。
  • 对行列式进行高斯消元时注意交换位置时正负会改变。
  • 高精度输出记得加上中间的0。
  • 尽量不要更改常量含义，实在要改的时候在程序醒目处注明提醒自己。
  • 三目运算符表达式周围最好打上括号
  • 调用杜教筛时注意有没有查询连续的大整数，注意n/(n/i)中的n是传入的n还是全局的n
  • NTT时取模比用if判断是否越界快很多，不要使用if取模负优化,也最好不要用inline函数代替过程
  • 预处理逆元时想请楚是不是阶乘逆元
  • 浮点数不要分段求和（带来较大误差）,比如dfs求浮点数的和时要用全局变量来存答案
  • " __int128 "和 “__float128” 不能互相转换(C++会出BUG)
  • 写fft/ntt/fwt时最外层循环总是写成for(int i=1; i<len; ++i)

其他技巧

git:
添加缓存加速下载:git config --global http.postBuffer 16777216
指定历史版本数目"x": --depth= x

gdb：
/t二进制 /o八进制 /x十六进制
可以选择 -tui 选项开启CLI调试（虽然并不会用GUI)

g++ 编译选项加-pg 后运行并gprof <可执行文件名>可以查看程序运行时间情况

Others

cuiuunhp4clfs85vb40gpflgf1

测试内存大小

inline string space(){
	ifstream fin("/proc/self/status");
	return string(istreambuf_iterator<char>(fin),istreambuf_iterator<char>());
}