526互联

错题集

发布时间 2023-07-27 00:51:11作者: pengyule

通读题面，记下坑；写完签到，回看题意和输入顺序/输出格式有没有读错，静心逐条检查多测清空、数组大小、整形溢出等易错点，拍；打满暴力，回看题意和输入顺序/输出格式有没有读错，静心逐条检查多测清空、数组大小、整形溢出等易错点，拍；再冲正解，回看题意和输入顺序/输出格式有没有读错，静心逐条检查多测清空、数组大小、整形溢出等易错点，拍；通读程序，重新编译，看warning，检查freopen

静态查错，手动构造小数据、极限数据，各种数据范围的对拍，是调试、检查时不可省略的步骤！

调试的方法：
①先静态查错，超过5分钟就开始输出调试。
②对拍大数据出错，立刻缩小参数范围直到找到一组极小出错数据，要知道足够小的数据是好调得多的。
检查的方法：手动构造小数据、极限数据；对拍；静态复盘。

  1. 调完一道题后测一下小样例；优化代码过程中每个阶段备份一次
  2. 所有比赛，第一件事是读完所有题目，打完所有暴力！！
    优点有两个：不会吃题目顺序的亏·不会最后急着写突然想到的题暴力没时间打了
    • 不要看到一道T3/T4题面看起来很长很麻烦就束之高阁，可能会错失数目可观的部分分或被包装的签到题(CSPS2022T3，不过也是因为时间不够了)
  3. 不开LL见祖宗，printf,scanf 不写 %lld 见祖宗【补充：p=1ll*p*q%mod不得写成(p*=1ll*q)%=mod】【补充：不要把>=0写~了，俩东西不等价！】【补充：NEVER USE __BUILTIN_POPCOUNT, IT DOESN'T WORK FOR LONG LONG!】
  4. 多测不清空，爆零两行泪||||常见的容易忘记清空的地方
G[0]
结构体
priority_queue
  1. 文件名、模数直接复制
  2. 不要注释 freopen，freopen 不要打成 froepen（结束前5min用cmd编译各cpp），freopen 不要写在 void solve() 里了！
  3. 记得删除调试信息
  4. 变量命名避坑 (下面都不能用)
j0   j1   jn   y0   y1   yn   arg
count   div   left   right   ws   dec   hex
oct   exp   polar   real   signal

  1. int 函数不返回见祖宗（事关重大）（解决方式：\(\Large{编译开\color{red}{-Wall},并认真读每一条警告}\)，所有题目写完的最后10分钟必须认真读IDE里头出来的编译信息！看有没有提示\(\textbf{non-void function return no value}\)类似的提示【因为本地能正常运行】）（模拟赛在namespace sub1{}中写了个int main() 没写return 0.....(-_-||) ）

  2. 审题问题

    1. 数组有没有开够？？（尤其是网络流和一些需要*2的题目！） const int N=1e5+5; const int N=5e5+5;一旦记错N，超级难调，小数据不RE，大数据不知道RE在哪，有些OJ还提示的不是RE【补充：有时不留神没有把200000开到2e5+5，所以全部写N，不要直接写数字，不管多大】Segment Tree / 01trie 如果维护多个信息统一const int V=N*...;不然容易漏写*...导致RE/WA【补充：各个subtask尽量都把数组开成N=Nmax，因为如果各subtask共用a[N]的话，如果a[N]只开到暴力的范围，特殊性质就会 \(\color{violet}{RE}\)】
    2. “大/小”不看反、大模拟操作不看漏
    3. 千万不要复制 pdf 中的样例！

  3. 关于取模

    1. p=1ll*p*q%mod不得写成(p*=1ll*q)%=mod
    2. +mod)%mod必须是(()%mod+mod)%mod，直接+mod)%mod很可能还是负数！！（7.23模拟赛就是因为这个没迅速找出所以T1 100->70！写的时候就注意！）
    3. ans=(ans+1ll*x*(C(n1,m1)-qp(n2,m2))%mod)%mod 也是不行的，负数乘以整数模mod看似正确，答案却是错的。（正确写法：ans=(ans+1ll*x*(C(n1,m1)-qp(n2,m2)+mod)%mod)%mod）
    4. A=1ll*A*(a+b+c)%mod; 是不行的，a+b+c 可能爆 int，三个及以上的 int 相加必须先 (ll)a
    5. 对于取模的题目，编码后和考试结束前15min利用ctrl+F文件查找功能将每一个 * 拉出来检查①其后是否 %mod 了 \(\color{red}{(计数题必备习惯!)}\)，因为在操作多的时候容易漏一个，②如果是 int 有没有1ll*

  4. 留出10分钟检查极限情况特判，如下：

    • 答案为0时有没有考虑？
    • 无解有没有考虑？
    • n和m有没有可能是0？图有没有可能不连通？重边？自环？

  5. 含有double的结构体不得使用node{x,y}创造对象，会\(\color{gold}{CE}\)

  6. 时限 1s，注意常数！（vector,fread）；时刻注意空间开销！（开一个 vector<int>a[N=3e6] 就要65MB了）

  1. （Csp&Noip2020）以为不会爆int结果爆了，记得保险起见开LL；不要好不容易记得开ll输出没有改%lld（P5656也要开LL！提高敏感性！）{p.s.scanf/printf一个long long，不写%lld会\(\color{purple}{RE}\)且本地不报错也不出错！}
  2. （Cf#698）状态不好T2都没写出来；T3知道要开ll，可惜排序比较函数cmp()漏改
  3. （BribingFipa）超级源点的儿子vector忘了清空
  4. manacher: 拼写错误id*2-i not id*2-1
  5. （L语言）优化方法：对于要更新的f，加入更新的操作是f|=x（x不一样）更新若干次，那么一旦发现x!=0就跳出。
  6. AC自动机，第一层只有不为空的子节点才要加入queue;下面层的节点不要忘记加Q
  7. (最长双回文串）在加了#的新串中枚举#断点，不能选第1个、最后一个#因为这样就相当于把断点放在了原串的第一个字符之前和最后一个字符之后
  8. （反回文p3501）又没开LL
  9. 看题目输空格还是换行
  10. 线段树如果把pushdown放在if(L<=l&&r<=R)前要开N*8空间
  11. (wflsacm-1-C)审题问题：1.没看到最短路非负的限制2.没想过加负△
  12. (wflsacm-1-E)莫队：注意两次询问间l,r移动时，先扩张（l--,r++的处理）再缩减（l++,r--）的操作
  13. （7.12B）sum那里左边不能带等，因为这个时候sum还没有加[1,1...1]区间内的任何任何数值（linkif(sum*k<mul&&(sum+r[j]-j+1)*k>=mul&&mul%k==0)ans++;）
  14. （7.13tree）分类讨论不充分，一来可能有新边重合于旧边，二来每一条新边考虑时还可以跟毫无管理的旧边配对删除
  15. （7.23stars）一般完全图的最小生成树一般n^2可过，用暴力prim；多数时候的最小生成树用kruskal；坐标系内特殊距离最小生成树只加有用的边
  16. （7.23achen）递推要注意转移式的限制条件和边界条件。
  17. （7.24gift）注意到0x3f*[>3]会爆MAX_INT/MAX_LL。
  18. y0,y1,yn,j0,j1,jn是库函数不能用作变量名(P5656就不能用x0,y0变量来表示那一组特殊解！)
  19. （7.30median）调试代码不小心会把set的it=begin放到insert前然后RE因为empty，要注意，而且不会在本地出错！
  20. memcpy(to,from,sizeof(from))
  21. (NOIP2015时间复杂度)多测不清空爆零两行泪，结构体也要归零哦
  22. （CF1554Dbackspace）字符串找到第一个不匹配的地方i,j移的时候不能这样写
    while(i<n&&j<m&&s[i]==t[j])i++,j++; if(i==n)return 0;因为可能是刚好匹配完，因此return 0改成return j==m。
  23. exgcd求解时注意`P_HEEE8_53QH1J2_80F_RE.png不能先除再乘（废话）
  24. （9.18C）11的倍数的特征是奇数位之和=偶数位之和(MOD11)
  25. (P5283异或粽子)

“小”技巧：看到最大的 区间 异或和，先求前缀和，将区间转化为最大异或对

  1. 《对于复合函数f(g(x)),其定义域为x的取值范围！》

  2. 当你没有发现100000007是10^8+7 or 当你没有看到 99824353

  3. n=100~600：可以想区间DP
  4. 求平面内的矩形交就不要傻傻地用扫描线了……
    顺便补充一个后来发现很常用的套路：求一个数组中多次查询除了一个数之外的数的异或和、或和、与和、加和……（一切满足交换律&结合律的运算和）都可以使用预处理前缀和和后缀和p[i],s[i]的方式来表示为p[i-1]\(\oplus\)s[i+1]。
  5. 参见笛卡尔树O(n)建树方法，第4排千万不要写>=
  6. 保险起见 #define 还是在 #include 下面写
  7. manacher 的 int p[N<<1] 和 char s[N<<1]——都要开两倍
  8. AC自动机的tot（节点编号）初始必须为0，根节点必须是0，因为可能匹配不上，得自动跳回根
  9. （CF60D）int b=1e6,c=1e5; ll a=b*c-c*c; 还是会出错，因为是先按int算右边再付给一个ll；ll a=(long long)b*c-c*c还是会错，每一次乘都要强行ll，或者简单地，*1ll。
  10. (树剖)注意！求dfn放到dfs2！
  11. （AC自动机）AC自动机fail树下传权值时一定不要搞反弄成统计子树和了！
  12. （P4606 [SDOI2018]战略游戏）树状数组的add不小心把void打成了int，luogu和loj都RE了，注意不返回的int函数会RE!
  13. (无语。。CF#769(1632)D)倍增要先枚举j（2^j）啊!!
  14. (P2515 [HAOI2010]软件安装)背包的转移条件必须注意，因为最大的前提是V[x]（当前节点体积）必须装得下，所以imagec562c6504494bd48.png
  15. （普及组/摆渡车）我斜率优化哪里写错了呢？这不是模板题吗咋会样例都过不了呢？这两份代码核心部分有什么本质区别吗？哦……括号好像有点错位。。。
  16. \(\color{green}{Dij}\) 要 \(\color{green}{vis}\) 掉已经确定下来的x[THIS IS ESSENTIAL!!!] (x=Q.top().se;Q.pop();if(vis[x])continue;vis[x];....)；Dij别把priority_queue写成queue!!
  17. 线段树维护a[i]+b[i]（其中b数组是定的）的区间最大值，区间对a修改。怎么写？t2[N<<2]：在build中求出的b的最大值；tag[N<<2]：tag[k]=max(tag[k],v)；t[N<<2]：t[k]=max(t[k],tag[k]+t2[k])
  18. (ARC091D)if(k*k<=n),k<=1e9方会炸从而错误选择。根号分治一律写k<=n/k
  19. (2022/4.8ZRT3)感觉自己完全没错所以一直无效debug。就是说：n个点的边带权树选若干条长为k(k∈{3,4})的边不重复链，最大的总边权和多少？这个问题中为什么O(nk)的拼接树形dp是错的？原因是一个点上可能挂着如下图所示的多组链，这个算法就分身乏术了。（正解是随机化，看博客去）imaged7c479255fd4f6d6.png
  20. （Number of binomial coefficients）char虽然可以在一定程度上用作int,但几百以上是存不了，因为ASCII码的本质。所以一定不要在进制转换时直接在上面做运算！先a[i]=s[i]-'0'!
  21. (Bear and chemistry)用来强制在线的\(R\)需要开LL
  22. Lagrange：莫把*((n-i&1)?-1:1)写成...1:-1；arr[]开多大想清楚；常数优化：min(维护的点值, arr[x+1]-arr[x])、先枚举x从而省去一维并且能够对x这一轮统一插值；取模(vital)
  23. (Dynamic Rankings)动态开点线段树空间要开2e5×72，因为值域大小为n+q
  24. 以前似乎学了个假的数位 dp，事实上只用记忆化不顶上界的部分呢，这样可以避免求一个数的就memset依次，从而有效削掉时间
  25. 别忘了，AC自动机的统计是不能直接tag[u]的，哪怕只统计bool也不行
  26. (ACSX6.28chain)订正的时候线段树N<<2的<<2掉了，换做不给大样例的考场时候就废了啊！
  27. (ACSX7.6)[本地查不出]\(A*\) 要mp[gha()]=1（防止重复入队）if(!mp[nxt.gha()])sta[++id]=nxt,Q.push(id),mp[nxt.gha()]=1;我掉了mp[nxt.gha()]=1;！！血的教训！
  28. 圆方树不instk
  29. Kruskal重构树dfs(nod) not dfs(1)（节约调试时间）
  30. PAM's tot=1
  31. 主席树在 if(l==r)/if(L<=l&&r<=R) 处的修改需要把结构体中维护的每个值都copy，再修改
  32. «VERY IMPORTANT» 极角排序必须使用 atan2，不能使用 \(\bf a\times \bf b\)
  33. (Atcoder/Snuke the Phantom Thief) EK费用流求最长路要考虑到dis有可能是很小的负数，所以要memset成0xcf
  34. (JSOI2018战争)“constinteps=1e-9;”！
  35. (NOIP2018保卫王国【动态dp】)①矩阵乘法和广义矩阵乘法不具有交换律，因而是从深度大的乘到深度小的；②树剖的修改之后还原到询问前的状态，要使用最原始的方法（储存copy+还原），不要加加减减（容易跟min等其他运算混在一起出错）
  36. (Intrinsic Interval)查st表的gran(l,r)注意assert l<=r，因为l>r可能本地不RE！
  37. 求mex（用vector的）勿忘先sort
  38. SORT不能用return ...<=...;，搞不好RE！要用<！！！
  39. 对于简单但操作多模拟题，检查有没有写漏一个操作！
  40. *lower_bound(..) 之前先判 lower_bound(..)!=..end()
  41. (8.13)当真调了好久啊……for(int i=n,mx=0;i;i--)if(mx<b[i].se)b[++_n]=b[i],mx=b[i].se;哪里错了？为什么必须正着来？太过显然就不解释了。
  42. （省选联考2021A支配）debug的时候不小心把vec.clear()删了，导致很不解自己的严格O(n^2)为什么TLE 当感到很odd自己的常数怎么可能“如此大”时,不妨看下是不是没清空什么
  43. (数据备份)注意到不能反悔b[1]和b[n]，因为这样对应没有增加一对办公楼。所以要把b[0]=b[n+1]=inf
  44. \(\color{red}\bf{\_\_int128}\) 或导致CE!!(at least on CF it does)故尽量使用long double代替!!
  45. (量子通信)一开始a1,a2没开ULL，调了好久才发现
  46. (魔法)结构体(matrix,...)初始化的时候写了for(i->n)for(j->n)f[i][j]=(...)最后发现根本没用，因为在最开始定义的时候，n还没有输入！所以要写for(i->N-1)for(j->N-1)...！（都是伪代码）
  47. (ABC214G)
    • 组合数C[n][m]和阶乘jc[n]因为计算原因要开到2N，但是我在改成C[N*2][N]后没有改jc[2*N]，可能不 \(\color{purple}{RE}\), 不报错!
    • (j&&C[2*cnt-j-1][j-1]) \(\ne\) (!j?0:C[2*cnt-j-1][j-1])
  48. sqrt不准(Dytechlab Cup 2022 B)，用二分（虽然我并没有打这一场）
  49. 树形背包的写法差异导致效率差异巨大
    for(int j=1;j<=siz[y];j++){
	for(int i=1;i<=siz[x]-siz[y];i++){
		add(f[x][0][i+j],1ll*g[i][0]*f[y][1][j]%mod);
		add(f[x][1][i+j],1ll*g[i][1]*f[y][1][j]%mod);
		add(f[x][0][i+j-1],1ll*g[i][0]*f[y][0][j]%mod);
		add(f[x][1][i+j-1],(1ll*g[i][0]*f[y][1][j]+1ll*g[i][1]*f[y][0][j])%mod);
	}
}//✅

    for(int j=1;j<=siz[y];j++){
	for(int i=j;i<=siz[x];i++){
		add(f[x][0][i],1ll*g[i-j][0]*f[y][1][j]%mod);
		add(f[x][1][i],1ll*g[i-j][1]*f[y][1][j]%mod);
		add(f[x][0][i],1ll*g[i-j+1][0]*f[y][0][j]%mod);
		add(f[x][1][i],(1ll*g[i-j+1][0]*f[y][1][j]+1ll*g[i-j+1][1]*f[y][0][j])%mod);
	}
}//❌
  50. (SHOI概率充电器)为避免 x/0=nan，将除数+eps(eps取1e-12等)。还有就是换根 dp 的 dfs2 是先把 g[y] 计算出来再 dfs(y,x)，日久天长别忘了（节约调试时间）
  51. (Binary Table)二维数组a[i][j] i,j打反导致RE?(节约调试时间)
  52. (Half-decay-tree)h<=30,for(int x=1;x<(1<<h+1);x<<=1)会错，因为(1<<32)>Maxint. 解决方案：1ll<<h+1
  53. (1726D)多测，有一个边的book数组，清空时写了 for(int i=1;i<=n;i++)dG[i]=0，实际上应该把n改成m。WA了两次
  54. (1725C)交第一次时断环成链没有把数组大小开两倍
  55. （1712D）二分上下界若没设紧可能会造成一些mistake，而这些mistake是corner case，如果上下界恰设到定义域的左开右闭区间的端点处则能够避免
  56. (Free Market)低级错误：01背包顺序
  57. (很久以前做的：joisc两个人的星座)atcoder评测机的神奇问题，重载运算符在结构体里面定义要加friend还是什么的，拉出来定义就能对
  58. (大型整数的奇怪问题/二分边界/const int 时或许也该注意)
ll L=0,R=80000000000000007,mid;//√
ll L=0,R=8e16+7,mid;//×，输出R会是80000000000000000

  1. （Cactus Wall）要建有向图，不是无向图，边权是指向的点的是否空

  2. 无向欧拉图寻找欧拉回路时要注意每遍历一条边就把它pop_back()，同时del[边编号]=1。

    void euler(int x){
	while(!E[x].empty()){
		if(del[E[x].back().se]){E[x].pop_back();continue;}
		del[E[x].back().se]=1;
		Do sth...
		int t=E[x].back().fi;
		E[x].pop_back();//第二个pop_back也不能省！
		euler(t);
    }
}

  3. int a[N];memset(a,0xcf,sizeof a)：值!=-0x3f3f3f3f，也!=0xcfcfcfcf，而是一个绝对值<1e9的负数！memset(a,-0x3f,sizeof a)：值!=-0x3f3f3f3f，是一个绝对值略大于1e9的负数！为了避免因真实数值不够大等导致的FST，必须要手写memset!!

  4. if(f[0][i][j]<INF)ans=min(ans,f[0][i][j]*i.......，前面的不能掉（一开始f memset 成了INF），不然会溢出成负数！

  5. (CSP-S2022T1holiday)被洛谷的过水数据蒙蔽以为自己AC了，去infoj上一侧发现废了，我本来记了第三大，结果把 for(j=0;j<=2;j++) 打成了 for(j=0;j<2;j++)……

  6. (2022.11.8)T1签到爆零？点开提交记录一看，原来是n*m的矩阵全是0的情况就一次操作都不需要了，要特判。寻思着这种特判在每个subtask都放一个是不是有亿点残忍……反正是模拟赛，但要\(\Large{长记性}\)

  7. (11.9)log2不是绝对的准（尤其是在参与各种运算后取整时），所以对精度有一定要求时记得用x±1校正

  8. (CF1537F)输入结束再输出NO（虽然不等输入结束都可以判断）（节约调试时间）

  9. (starry night camping)long long:求两个[-1e9,1e9]内的坐标点的曼哈顿距离时会爆int

  10. 使用fgets读取整行换行符会被读取并存入s

  11. 对于区间操作、操作若干次一个数就会不变的DS题，当然使用线段树维护，但是即便这个节点已经有恒定标记，区间修改时也要打tag然后pushdown照常，因为还可能进入它

  12. 栈模拟dfs时，注意递归层数是O(m),not O(n)

  13. (NOIP2022)线段树的两个tag从ull改成了int，原因是赛时以为int比ull快，想卡时，但后面有一个(r-l+1)*tag，n是2.5e5，就炸了52->36... 看到*务必警觉，谨慎判断两侧相乘是否确保不会爆int

  14. 《Very Important》循环中的特判有没有把continue写成break

  15. 长链剖分求son[x]一定要先把len设为-1，因为边权为0的时候可能永不更新，然后把叶子的len设为0。重链剖分可能有时也需要。

  16. 平衡树一定不要更新0节点（空节点）

  17. 网络流题 提交前 务必务必 检查边数、点数是否开够数组！！

  18. (SXMN2.13)博弈论题，样例里面没有输出Bob的，我把必败和必胜叫做1和2，必胜应该是if(sg(...)==2)的，结果我误写成if(sg(...))，导致20pts丢了

  19. (aliens)WQS二分注意L,R上下界，通常是L=-1,R=MAX_VAL或L=-MAX_VAL,R=1 (-1写成-2)也会错！

  20. SAM的fail在第一次赋值后还会变化！
    多个独立的串插入SAM时一定要每次把las=1！
    SAM节点数2n

  21. 线段树合并数组大小开到2nlogn

  22. （2.25）复制pdf中样例时掉了最后一个数字，调了1个小时！

  23. (PJudgeNOIPR#5)T1又一次某处乘法忘了1ll*

  24. 低级错误：if(b<r<b+n)

  25. (Roads in Yusland)
    （1）动态开点pushdown注意if(t[x].ls);if(t[x].rs);
    （2）不要把l打成1 （但是我真的没有啊，有没有可能是Dev-C++的bug把l渲染成1了……）

  26. K-D 树的 nth_element 比较函数一定要写成 return a[i].l==a[j].l?i<j:a[i].l<a[j].l，这样后面 ins/del 时才能正确锁定目标位置（尤其是 del，会 RE 的）

  27. \(\bm {for/while}\) 循环不允许写 \(\bm{<}\) 了，哪怕是，也给我改成 \(\LARGE \bm {<=}\)！！！(CSPS2022T1)

  28. （HL3.7）离散化的\(u\)没有多测清零导致TLE！！
    查kth别用线段树二分了，用离散化+树状数组二分，常数小得多！

  29. 维护分段函数的和时，要特判斜率为0的情况，因为没有分界点

  30. (2023.3.9)CF E fst,原因：想假了，考后2min改对；F 最后几分钟没调出来，原因：预处理的floyd最短路数组e[u][v]，后面 dp 从u转移到v时没有if(e[u][v]<INF)，导致求出不合法的答案。

  31. (2023.3.10模拟赛)数据结构签到题和暴力老哥同分。原因：考试时写出了分块正解，却因为在大数据下运行缓慢，而认为是算法本身常数过大，禁锢了进一步发现可以优化的点的想法。考后散心时感觉 len 并不需要从 1 到 47 枚举，只可能是 1 到 47 内离散的不超过 10 个数值，改正后立刻通过。
    56. map<int,bool>调了好久，本来一开始bool就行，后来改变了map的含义，忘了把类型改成<int,int>

  32. 欧拉序求lca预处理st表空间要开N*2（这次没忘）
    58. 想用 unordered_map 存 n=1e5 图的邻接矩阵并TLE时的卡常方法：for(i,1,n)sort(G[i]);.....if(binary_search(G[y].begin(),G[y].end(),x))

  33. cdq 分治如果是 \(\geqq\) 一定要多关键字排序！ sort(a+1,a+m+1,[](node a,node b){return a.a==b.a?a.b==b.b?a.c==b.c?a.type<b.type:a.c<b.c:a.b<b.b:a.a<b.a;});

  34. int 的 exgcd 在 x*=C 一步可能溢出。

  35. 输入树忘了无向边 G[v].emplace_back(u,w)

  36. 值域1e9的双向链表如果只想用几个位置，初始化时不能写 for(i,1,n)pre[a[i]+1]=a[i],nxt[a[i]]=a[i]+1，而要写 for(i,1,n)pre[a[i]+1]=a[i],nxt[a[i]]=a[i]+1,pre[a[i]]=a[i]-1,nxt[a[i]-1]=a[i]

  37. f[200005][205] 比 f[205][200005] 慢好多好多

  38. const int INF=2e9; f[i]=ask(...)-l[i] (ask可能返回-INF)导致溢出，调了1h! 以后设 INF 时谨慎一些，如果定义的时候还不能确定是否溢出就先打个注释警告。

  39. (联合省选2023)D1T3 多测没有把该清空的全清空（priority_queue<int,vector<int>,greater<int> >q[N]），\({\color{orange}{48}}\to\color{orange}{40}\)，现在感到后怕

  40. (联合省选2023)D2T2 可以用并查集解决的写了个dinic，\(40\to 36\)（就像UR#24可以用并查集解决的建了个图dfs，常数大了）

  41. （CF1381D Treesnake)打错一个字符 visl[l] 写成了 visr[l]，静态查错没查出来

  42. （4.26模拟赛）疑似卡常题一定：（1）不用vector（2）加fread

  43. 求行列式时，辗转相除的高斯消元法灰常灰常的慢，应该使用：

for(int i=1;i<=n;i++){
	if(!e[i][i])for(int j=i+1;j<=n;j++)if(e[j][i]){swap(e[j],e[i]);det=-det;break;}
	if(!e[i][i])return puts("0"),0;
	int now=qp(e[i][i],mod-2);
	for(int j=i+1;j<=n;j++){
		int d=(ll)e[j][i]*now%mod;
		for(int k=1;k<=n;k++)e[j][k]=(e[j][k]-(ll)e[i][k]*d%mod+mod)%mod;
	}
}
  1. (PKUWC2020火山哥与打铁传说)线段树 \(\bf{pushdown}\) 了吗？
  2. \(O(n^3)\)矩阵乘法要以 i、k、j 的顺序枚举，常数减小2倍以上！
  3. （4.28模拟赛）AC自动机高斯消元有一个for(j,0,tot)写成了for(j,1,tot)，导致消元不彻底。 ||| 高斯消元求行列式只需要从i+1开始第二轮枚举，而解方程要for(j,0,tot)if(j!=i)！
  4. (分手是祝愿)把*ctrl+F拉出来看有没有取模和(ll)
  5. (5.4模拟赛)线段树合并merge调用时把merge(x,y,l,r)写成了merge(l,r,x,y)还有线段树合并优化DP pushup 未取模
  6. (CF-R872赛后被hack)组合数忘记判 \(n<m\)
  7. 如果 NOI 考场的 VScode 有在线语法提示的话，不要在显示“0错误”后就不编译了，因为并没有提示所有错误，还是很可能 CE！
  8. 对拍的 Gen 不能写 mt19937(clock())，因为可能是按照程序运行起始时刻为 0 计的，从而总是生成同一组数据。
  9. 负数整除运算要三思（转成正数再运算)
  10. 通过使对二维数组 l[i][j],u[i][j],r[i][j] 的调用地址连续化，更改了l,r的i,j两维顺序，更改了循环顺序；减少了不必要的循环条件。最终将《数中分》一题的暴力代码从6s+优化到了4s-
  11. 打部分分容易错的地方：if(n*q<=1e8)bruteforce::solve();[×] if((ll)n*q<=1e8)bruteforce::solve();[√]
  12. （P8456）Tarjan圆方树求每个点双的子图边集时，误把bel[i.first]写成bel[dfn[i.first]]
  13. 计数 DP 卡常：\(f[i]=f[i]*f[j]...\% mod\) 乘之前判断 \(f[j]\) 是否 \(\ne 0\)。
  14. (5.24dingzheng)Did not fa[n+1]=n+1 in DSU for maintaining deletion on sequence. It would be stuck in a loop and result in MLE 85pts. Such mistakes can only be discovered by DuiPai!
  15. My 20pts brute force solution in today's T3 got 0, what happened? When I was deleting the cerr<<... for debugging, I failed to delete a portion of it, and the code became: cerr<<\nscanf("%s",s+1);, but cerr is too slow.
  16. [b] typo: [_b], debugged for half an hour. Always read your code thoroughly when confused.
  17. 最小费用可行流: NO SOLUTION it is possible even when the balancing measures are taken, so it is necessary to recheck after finishing running MCMF.
  18. O(26*1e5*26),always wrap small loops out of big ones, and put small array indices before big ones! 4s+->3s-
  19. Debugged ACAM fail tree High-Light-Decomposition for over an hour: if(siz[son[x]]<siz[y])son[x]=y. Since son[x] is initially 0, this will result in TLE since siz[0] is always the biggest and the tree would not be decomposed at all. ALWAYS WRITE if(!son[x]||siz[son[x]]<siz[y])son[x]=y;! YOU DON'T WANT TO DEBUG BASIC DS FOR AN HOUR AT NOI, DO YOU!
  20. Don't use fread in Interactive Problems!
  21. 确认自己正确性无误后，一定要精益求精，力求降低复杂度或者减小常数。有时并不能一次写出复杂度最低或常数最小的做法。（模拟赛n<=3000，明明可以\(O(n^2)\)预处理dis[u][v]，我却使用了带 log 的倍增，去冒 \(O(n^2\log n)\) 能过的险（而且还写挂了）；UOJ Round 24 明明可以用并查集求连通性，我却建了一张图来判，还是用 vector。其实并不见得是掉以轻心，而是缺乏工匠精神和优化意识，在平时需要反复训练。）另外，优化常数后勿忘和原代码对拍，避免出现“优化”成 WA 的情况（NOIP2022T4）。
  22. 倍增求 LCA 须注意！——如果是带权树，是不能偷懒用带权深度作为 dep 的！原因，显然！
  23. NTT beware: for(i,0,lim-1)c[i]=(ll)a[i]*b[i]%mod;,not for(i,0,n)
  24. (6.22) DuiPaied but Boomed 0: Assumed \(a_i\) to be the position of balls and \(b_i\) to be the position of holes without a second thought. (in fact it should be the reverse.) Didn't even look at the input section carefully. The problem needed checker, so even though my output was completely different with the standard output, I thought it was right, and it could pass my hand-written checker. PAY ATTENTION TO INPUT AND OUTPUT FORMAT!
  25. When maintaining an integer, long double cannot replace __int128. Calculation results are unacceptably inaccurate. Use long long if possible; otherwise use __int128.
  26. NOI Linux 下没出错、CF 上出错的一个诡异 Warning：c[z++]=a[0]+b[0]-(z==0?0:-inf);（“z may be used undefined”），以后尽量少这么写。
  27. 当对拍发现暴力比较难写时，起码得先写 gen 测一下极限数据会不会 RE、TLE、WA，不要摆烂！