[关闭]
@ivorysi 2019-07-06T12:10:37.000000Z 字数 23839 阅读 882

一些错误归因

笔记

1.int和int相乘会爆int

这种情况在比较中容易出现
例如

  1. if(a*b<=c) ...

解决方法是把乘法换成除法

  1. if(a<=c/b)

或者开long long

2.没有写函数名

这个略显玄学
就比如说，定义了一个函数

  1. int f(int a,int b,int c,int d);
  2. int main() {
  3.     int x=(a,b,c,d);
  4. }

多出现在参数比较多，而且是赋值操作之间
这个……还是注意点吧……

3.插头dp中状态对应的情况

  1. //不能直接找右侧第一个右括号，因为可能有这样((()))()()
  2. //删掉前两个括号时，我们需要找第5个括号更改方向

一开始直接找的右侧第一个括号

4.关于==打成=

  1. if(a=b) {
  2. }

返回值一定是true
解决方法可以开-Wall来提醒

5.二进制的运算符比比较运算符的优先级要低

  1. if(1&a > 0)

凡是有二进制运算符的地方一定要打括号

6.输出最小值去排序

这可能就是脑子短路了

7.数组越界了吗

这可能就是犯二了

8.数组开大了吗

有些情况下是隐性的
例如长度为100000的string开了100000个
然后就gg

9.数组开小了吗

这就真的见祖宗了……造成的后果就是越界，但是和越界还有区别

10.不开long long

十年OI一场空，不开long long见祖宗
还可以解决int int 相乘的问题

11.int函数没有返回值

写着写着就忘了
开-Wall可以解决这类疑难杂症

12.scanf不打&

开-Wall可以解决这类疑难杂症

13.网络流该往下一个点漏多少的问题

  1. int sap(int u,int aug) {
  2.     if(u==c2*2) return aug;
  3.     int flow=0,dmin=2*n-1;
  5.     for(int i=head[u];i;i=edge[i].next) {
  6.         int v=edge[i].to;
  7.         if(edge[i].val>0) {
  8.             if(dis[u]==dis[v]+1) {
  9.                 int t=sap(v,min(edge[i].val,aug-flow));
  10.                 //应该流走的是aug-flow，为什么每次都是网络流写的出问题qwq
  11.                 edge[i].val-=t;
  12.                 edge[i^1].val+=t;
  13.                 flow+=t;
  14.                 if(flow==aug) break;
  15.                 if(dis[c1*2-1]>=2*n) return flow;
  16.             }
  17.             dmin=min(dmin,dis[v]);
  18.         }
  19.     }
  20.     if(!flow){
  21.         --gap[dis[u]];
  22.         if(gap[dis[u]]==0) dis[c1*2-1]=2*n;
  23.         dis[u]=dmin+1;
  24.         ++gap[dis[u]]; 
  25.     }
  26.     return flow;
  27. }

万一原点的水流不够用呢？

14.关于我自己的宏定义的问题

经常写了xiaosiji后来按照siji的思路来写，然后gg
就是<=变成了<
这个还是要多加注意

15.输出没有排序

这岂不尴尬？
然后当然就爆零啦……

16.忘记多组数据的初始化

一定要多生成几组数据卡自己
万一忘记初始化呢？

17.宽搜会爆空间的题

这个就要手算了，如果空间约束比较大还是深搜吧
例如方格图的大小比较大

18.scanf大概是倒序执行的

  1. scanf("%d%d",&u,&val[u]);

它会先读入val[u]，但是u并不是我们想要的下标

19.Floyd求最小环

  1.  siji(k,1,cnt) {
  2.      xiaosiji(i,1,k) {//因为不能用k点所以是<k
  3.          xiaosiji(j,i+1,k) {
  4.              ans=min(ans,g[i][j]+f[i][k]+f[k][j]);
  5.          }
  6.      }
  7.      siji(i,1,cnt) {
  8.          siji(j,1,cnt) {
  9.              g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
  10.          }
  11.      }
  12. }

必须是小于号

20.有些时候1和l容易弄混

就是在线性处理某个区间，区间的左端点是l，容易习惯性的当1处理

21.没删freopen到某个测试文件

主要表现在我没删注释

22.关于高精度的某个手误(1)

  1. bignum operator *(const bignum &b)const {
  2.     int lena=v.size(),lenb=b.v.size();
  3.     bignum c;c.v.clear();
  4.     siji(i,0,lena+lenb) c.v.push_back(0);
  5.     xiaosiji(i,0,lena) {
  6.         int g=0;
  7.         xiaosiji(j,0,lenb) {
  8.             c.v[i+j]+=(g+v[i]*b.v[j]);//我写成b.v[i]然后越界了……gg……
  9.             g=c.v[i+j]/10;
  10.             c.v[i+j]%=10;
  11.         }
  12.         int t=i+lenb;
  13.         while(g) {
  14.             c.v[t]+=g;
  15.             g=c.v[t]/10;
  16.             c.v[t]%=10;
  17.             ++t;
  18.         }
  19.     }
  20.     gongzi(i,lena+lenb,1) {
  21.         if(c.v[i]==0) c.v.pop_back();
  22.         else break;
  23.     }
  24.     return c;
  25. }

23.关于高精度的某个手误(2)

  1. bignum operator = (long long x){
  2.     v.clear();
  3.     do{
  4.         v.push_back(x%10);
  5.         x/=10;
  6.     }while(x);//我写成x>=0,然后死循环了
  7.     return *this;
  8. }

24.关于默写后缀数组倍增算法

  1. for(p=0,j=1;p<n;j*=2,m=p) {//p是排名有多少个
  2.     for(p=0,i=n-j;i<n;++i) y[p++]=i;
  3.     for(i=0;i<n;++i) if(sa[i]>=j) y[p++]=sa[i]-j;//把>=写成>了
  4.     for(i=0;i<n;++i) sortb[i]=x[y[i]];
  5.     for(i=0;i<m;++i) sorta[i]=0;//把m写成n了
  6.     for(i=0;i<n;++i) ++sorta[sortb[i]];
  7.     for(i=1;i<m;++i) sorta[i]+=sorta[i-1];
  8.     for(i=n-1;i>=0;--i) sa[--sorta[sortb[i]]]=y[i];
  9.     swap(x,y);
  10.     for(p=1,x[sa[0]]=0,i=1;i<n;++i) 
  11.         x[sa[i]]=cmp(y,sa[i],sa[i-1],j) ? p-1:p++;
  12. }

板子题然后gg……
第一个错误导致0不能到y数组里，然而数字从0开始存
把m写成n当n比26小，里面又有较大字符的时候就会gg……

25.忘记及时continue

  1. siji(i,1,n) {
  2.     if(!askpre(a[i])) pushpre(a[i]);
  3.     if(cnt1==cnt2)
  4.         {ans+=s-t+1;continue;}//要加上这一句不然总是从s开始去找t
  5.     while(cnt1!=cnt2) {
  6.         if(p<1) return;
  7.         if(askpre(a[p])) {
  8.             if(!asksuf(a[p])) pushsuf(a[p]);
  9.             --p;
  10.         }
  11.         else {
  12.             while(askpre(a[i+1])) ++i;
  13.             pushpre(a[i+1]);++i;
  14.         } 
  15.     }
  16.     s=p+1;
  17.     t=s;
  18.     while(asksuf(a[t])) --t;
  19.     ++t;
  20.     ans+=s-t+1;
  21. }

然后超时了

26.我又双叒叕把&&打成||了

  1. while(p+1<=n && kuang[p+1].id<=k) {
  2.     while(t>h || q[t-1]<=kuang[p+1].val) --t;
  3.     //上面这句||应该是&&，如果是||那么它会一直--t然后越界到不知道哪里去了
  4.     q[t++]=kuang[p+1].val;
  5.     ++p;
  6. }

27.我忘记第一次肝的某个位置需要初始更新一下

  1. p=1;
  2. while(p<=n && num[p]-1<0) ++p;
  3. siji(i,1,2000000) {
  4.     tot-=cnt[0]/2;
  5.     cnt[0]-=cnt[0]/2;
  6.     if((num[p]-i)==0) {
  7.         cnt[0]+=cnt[num[p]];
  8.         cnt[num[p]]=0;
  9.     }
  11.     while(p<=n && num[p]-i<=0) ++p;
  12.     if(tot==1 && cnt[0]==1) {printf("%d\n",i);break;}
  13. }

这段代码的bug体现在哪里呢，就是如果我们第一个位置是0，然鹅我们有1这样的数，我们下标显然还指着0，就会gg
我们需要一开始就把下标移到第一个非0位就好啦！！！

28.写trie树没打finish标记

我的天我写了这么多年trie树是怎么无伤过每一道题的
难道大家都觉得单纯查字典太傻了……结果我去写单纯查字典就挂了？

29.树状数组不能处理0位！！！！

不能处理0位！！！

30.经典的先序遍历和中序遍历还原二叉树

我们需要需要判断左子树有还是没有，右子树有还是没有

  1. int len=k-l2;
  2. if(len!=0)
  3.     lson[res-'a'+1]=dfs(l1+1,l1+len,l2,k-1);
  4. len=r2-k;
  5. if(len!=0)
  6.     rson[res-'a'+1]=dfs(r1-len+1,r1,k+1,r2);

没有特判就gg

31.因为#define MAXN 多打了一个0爆空间了

如题啊……
然后多了10倍的空间
宏定义的数要打对啊

32.关于某个垃圾的输出函数

  1. void out(int k) {
  2.     if(k>=10) {
  3.         out(k/10);
  4.     }
  5.     putchar('0'+k%10);
  6. }

这个函数是不能输出负数的！！！！！
所以要这么写

  1. void out(int k) {
  2.     if(k<0) {putchar('-');k=-k;}
  3.     if(k>=10) {
  4.         out(k/10);
  5.     }
  6.     putchar('0'+k%10);
  7. }

33.关于浮点数的精度问题

其实浮点数整数部分超过了int就会发生很大的误差……

34.关于字符串的问题（七校模拟）

【题目描述】

定义两个字符串 A,B 相似当且仅当满足以下两个条件中的至少一
个：
(1)A 和 B 相同；
(2)将 A 分为长度相同的两个子串 A0,A1，将 B 分为长度相同的两
个子串 B0,B1，满足 A0 相似于 B0，A1 相似于 B1 或 A0 相似于 B1，
A1 相似于 B0。
给定两个字符串 S,T，问它们是否相似。
有多组数据。

【输入数据】

第一行一个整数 t 表示数据组数。
每组数据第一行一个字符串 S，第二行一个字符串 T，保证它们
长度相同。

【输出数据】

每组数据一行，若相似输出 YES，不相似输出 NO。

【样例输入】

2
abab
baab
aabb
abab

【样例输出】

YES
NO

【数据范围】

对于 30%的数据，|S|<=30。
对于 60%的数据，|S|<=100。
对于 100%的数据，t<=30，∑|S|<=500000。

题解

这道题本来应该AC的……
然而一开始认为长度为奇数的串是不可能往下拆的，直接输出了NO
实际上两个长度为奇数的串可以一开始就相等……哇QAQ

哇QAQ……

35.压缩状态时的位权可以不断变化的（七校模拟第一试Day2T3）

关键那么多年压位压的全都是相同进制的，哇QAQ

36.记一道永远不会写的线段树

火星探险
源程序名 　　　MAR.??? (PAS,C,CPP)
输入文件名　　 MAR.IN
输出文件名 MAR.OUT
时间限制 1S
空间限制 256MB
问题描述：
在2051年，若干火星探险队探索了这颗红色行星的不同的区域并且制作了这些区域的地图。现在, Baltic空间机构有一个雄心勃勃的计划：他们想制作一张整个行星的地图。为了考虑必要的工作，他们需要知道地图上已经存在的全部区域的大小。你的任务是写一个计算这个区域大小的程序。
任务：
l 从输入文件 mar.in 读取地图形状的描述
l 计算地图覆盖的全部的区域
l 输出到输出文件mar.out
输入：
输入文件mar.in的第一行包含一个整数N(1<=N<=10000)，表示可得到的地图数目。
以下N行，每行描述一张地图。
每行包含4个整数x1，y1，x2和y2(0<=x1 输出：
输出文件 mar.out，应该包含一个整数，表示探索区域的总面积(即所有矩形的公共面积)。
样例：
MAR.IN
2
10 10 20 20
15 15 25 30
MAR.OUT
225

这是一道扫描线的题，看上去很像区间加是吧……然后第一反应就是打标记
但是这道题不打标记！！！
为什么呢
因为我们下放了标记之后，一次删除的操作并不会立刻下放，导致我们统计左右子树的时候左子树拥有的线段长度和右子树拥有的线段长度不是真正的线段长度……
然后！这道题利用的是矩形关键的特性！
因为每对一个区间累加我们都会把同样的区间再减去就可以了！！！
我们实际上只需要维护一个线段出现过几次就可以了，直接累加到线段树上就可以了
删除的时候直接减去1
维护cover是覆盖了几次
如果cover>0那么一整条区间都要
如果cover<=0就是左右区间有的线段长度的加和
这道题是不打标记的，因为我们打完标记后的删除操作不能立即下放，导致左右子树 区间统计是错的
这道题是不打标记的！！！！！

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <cstring>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. //#define ivorysi
  9. #define pii pair<int,int> 
  10. #define fi first
  11. #define mod 998244353
  12. using namespace std;
  13. typedef long long ll;
  14. int readint() {
  15.     int res=0;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') c=getchar();
  18.     while(c>='0' && c<='9') {
  19.         res=res*10+c-'0';
  20.         c=getchar();
  21.     }
  22.     return res;
  23. }
  24. void out(ll x) {
  25.     if(x<0) putchar('-'),x=-x;
  26.     if(x>=10) {
  27.         out(x/10);
  28.     }
  29.     putchar('0'+x%10);
  30. }
  31. int n;
  32. struct node {
  33.     int val,st,ed,cmp;
  34.     bool operator < (const node &rhs)const {
  35.         return cmp<rhs.cmp;
  36.     }
  37. }seg[20005];
  38. struct trnode{
  39.     int length,l,r,cover;
  40. }tr[100005];
  41. void build(int u,int l,int r) {
  42.     tr[u].l=l;tr[u].r=r;
  43.     tr[u].length=tr[u].cover=0;
  44.     if(l==r) {
  45.         return;
  46.     }
  47.     int m=(l+r)>>1;
  48.     build(u<<1,l,m);
  49.     build(u<<1|1,m+1,r);
  50. }
  51. void change(int u,int l,int r,int val) {
  52.     if(l==tr[u].l && r==tr[u].r) {
  53.         tr[u].cover+=val;
  54.         if(tr[u].cover>0) tr[u].length=tr[u].r-tr[u].l+1;
  55.         else if(tr[u].l==tr[u].r) tr[u].length=0;
  56.         else tr[u].length=tr[u<<1].length+tr[u<<1|1].length;
  57.         return;
  58.     }
  59.     int mid=(tr[u].l+tr[u].r)>>1;
  60.     if(r<=mid) {
  61.         change(u<<1,l,r,val);
  62.     }
  63.     else if(l>mid) {
  64.         change(u<<1|1,l,r,val);
  65.     }
  66.     else {
  67.         change(u<<1,l,mid,val);
  68.         change(u<<1|1,mid+1,r,val);
  69.     }
  70.     if(tr[u].cover>0) tr[u].length=tr[u].r-tr[u].l+1;
  71.     else if(tr[u].l==tr[u].r) tr[u].length=0;
  72.     else tr[u].length=tr[u<<1].length+tr[u<<1|1].length;
  73. }
  74. ll ans=0;
  75. void solve() {
  76.     int X1,Y1,X2,Y2;
  77.     n=readint();
  78.     siji(i,1,n) {
  79.         X1=readint();
  80.         Y1=readint();
  81.         X2=readint();
  82.         Y2=readint();
  83.         seg[2*i-1]=(node){1,X1,X2,Y1};
  84.         seg[2*i]=(node){-1,X1,X2,Y2};
  85.     }
  86.     sort(seg+1,seg+2*n+1);
  87.     build(1,1,30000);
  88.     change(1,seg[1].st+1,seg[1].ed,seg[1].val);
  89.     siji(i,2,2*n) {
  90.         ll h=seg[i].cmp-seg[i-1].cmp;
  91.         ans+=h*tr[1].length;
  92.         change(1,seg[i].st+1,seg[i].ed,seg[i].val);
  93.     }
  94.     out(ans);putchar('\n');
  95. }
  96. int main() {
  97. #ifdef ivorysi
  98.     freopen("f1.in","r",stdin);
  99. #endif
  100.     solve();
  101.     return 0;
  102. }

37.记一个垃圾的输入函数

  1. int readint() {
  2.     int res=0;
  3.     char c=getchar();
  4.     while(c<'0' || c>'9'){
  5.         c=getchar();
  6.     }
  7.     while(c>='0' && c<='9') {
  8.         res=res*10+c-'0';
  9.         c=getchar();
  10.     }
  11.     return res;
  12. }

这个函数是不能读入负数的！！！

  1. int readint() {
  2.     int res=0;
  3.     int neg=1;
  4.     char c=getchar();
  5.     while(c<'0' || c>'9'){
  6.         if(c=='-') neg=-1; 
  7.         c=getchar();
  8.     }
  9.     while(c>='0' && c<='9') {
  10.         res=res*10+c-'0';
  11.         c=getchar();
  12.     }
  13.     return res*neg;
  14. }

38.记一个线段树的手误

  1. pli qlmax(int u,int l,int r,int x) {
  2.     if(tr[u].l==l && tr[u].r==r) {
  3.         if(x!=tr[u].posl) {
  4.             return make_pair(tr[u].lmax,tr[u].posl);
  5.         }
  6.         return make_pair(tr[u].otherl,tr[u].posthl);
  7.     }
  8.     int m=(tr[u].l+tr[u].r)>>1;
  9.     if(r<=m) {
  10.         return qlmax(u<<1,l,r,x);
  11.     }
  12.     else if(l>m) {
  13.         return qlmax(u<<1|1,m+1,r,x);
  14.         //这里是错的，总是在整个区间下查询的时候一个手滑就写成了m+1……或者上面写成l，m
  15.     }
  16.     else {
  17.         return max(qlmax(u<<1,l,m,x),qlmax(u<<1|1,m+1,r,x));
  18.     }
  19. }

39.缩点后的拓扑排序

  1. siji(k,1,n) {
  2.     poi[col[k]].push_back(k);
  3.     for(int i=head[k];i;i=edge[i].next) {
  4.         int v=edge[i].to;
  5.         ind[col[v]]++;
  6.     }
  7. }

这个是错的，为什么呢……
因为有可能k和v在一个连通块里啊！！！

  1. siji(k,1,n) {
  2.     poi[col[k]].push_back(k);
  3.     for(int i=head[k];i;i=edge[i].next) {
  4.         int v=edge[i].to;
  5.         if(col[v]!=col[k])ind[col[v]]++;
  6.     }
  7. }

40.关于线段树优化dij

我写了这个东西绝对不下十次
绝对每次都错
我整理一下写这个东西的思路
1.预备工作
(1)一个大约点数8-10倍的线段树，一个数组就行，存的是下标
(2)一个dist数组，是临时的，是线段树需要维护的，一个dis数组，是最后的答案
(3)一个vis数组！！！！判断这个点的最短路有没有确定下来！！！！
2.算法部分
(1)将dist数组全部赋成正无穷
(2)将起点的dist改成0
(3)建线段树
(4)算法进行n次……这里总是错，干脆下次写成k=n;while(k--) 好了，不然容易弄混，导致计数器是i，写成head[i]，然而线段树里的点是u
(5)找出一个点u，将dis[u]赋成dist[u],vis[u]=1
(6)更新最短路的时候判断这个点是不是最短路已经确定了,如果更新了最短路，在线段树里更新这个节点
(7)dist[u]改成正无穷，然后在线段树里修改这个点的值

板子！

  1. int tr[MAXN*10],pos[MAXN];
  2. ll dist[MAXN],dis[MAXN],temp;
  3. bool vis[MAXN];
  4. void build(int u,int l,int r) {
  5.     if(l==r) {
  6.         tr[u]=l;
  7.         pos[l]=u;
  8.         return;
  9.     }
  10.     int m=(l+r)>>1;
  11.     build(u<<1,l,m);
  12.     build(u<<1|1,m+1,r);
  13.     if(dist[tr[u<<1]] < dist[tr[u<<1|1]]) {
  14.         tr[u]=tr[u<<1];
  15.     }
  16.     else {
  17.         tr[u]=tr[u<<1|1];
  18.     }
  19. }
  20. void change(int x) {
  21.     int t=pos[x]>>1;
  22.     while(t>=1) {
  23.         if(dist[tr[t<<1]]<dist[tr[t<<1|1]]) {
  24.             tr[t]=tr[t<<1];
  25.         }
  26.         else {
  27.             tr[t]=tr[t<<1|1];
  28.         } 
  29.         t>>=1;
  30.     }
  31. }
  32. void dijkstra() {
  33.     siji(i,1,n) {
  34.         dist[i]=1000000000000000000LL;
  35.     }
  36.     dist[S]=0;
  37.     build(1,1,n);
  38.     siji(i,1,n) {
  39.         int u=tr[1];
  40.         vis[u]=1;
  41.         dis[u]=dist[u];
  42.         if(u==T) break;
  43.         for(int j=head[u];j;j=edge[j].next) {
  44.             int v=edge[j].to;
  45.             ll w=edge[j].val;
  46.             if(vis[v]) continue;
  47.             if(dist[v]-w>dist[u]) {
  48.                 dist[v]=dist[u]+w;
  49.                 change(v);
  50.             }
  51.         }
  52.         dist[u]=1000000000000000000LL;
  53.         change(u);
  54.     }
  55. }

41.处理dfs序容易犯的一个错误

就是会有一个数组id[x]记录x在dfs序中的位置，是位置，而不是id[x]就是dfs序

42.tarjan的一个手误

tarjan写错了我是不是要完蛋了

  1. void tarjan(int u) {
  2.     dfn[u]=low[u]=++inx;
  3.     st.push(u);
  4.     instack[u]=1;
  5.     for(int i=head[u];i;i=edge[i].next) {
  6.     int v=edge[i].to;
  7.     if(!dfn[v]) {
  8.         tarjan(v);
  9.         low[u]=min(low[u],low[v]);
  10.     }
  11.     else if(instack[u]==1) {
  12.         low[u]=min(dfn[v],low[u]);
  13.     }
  14.     }
  15.     if(low[u]==dfn[u]) {
  16.     ++tot;
  17.     int x;
  18.     while(1) {
  19.         x=st.top();st.pop();
  20.         col[x]=tot;
  21.         instack[x]=2;
  22.         if(x==u) break;
  23.     }
  24.     }
  25. }

emmmmmm这个错误显然不好找……看第11行

  1. void tarjan(int u) {
  2.     dfn[u]=low[u]=++inx;
  3.     st.push(u);
  4.     instack[u]=1;
  5.     for(int i=head[u];i;i=edge[i].next) {
  6.     int v=edge[i].to;
  7.     if(!dfn[v]) {
  8.         tarjan(v);
  9.         low[u]=min(low[u],low[v]);
  10.     }
  11.     else if(instack[v]==1) {
  12.         low[u]=min(dfn[v],low[u]);
  13.     }
  14.     }
  15.     if(low[u]==dfn[u]) {
  16.     ++tot;
  17.     int x;
  18.     while(1) {
  19.         x=st.top();st.pop();
  20.         col[x]=tot;
  21.         instack[x]=2;
  22.         if(x==u) break;
  23.     }
  24.     }
  25. }

我这个傻子把v写成u了
算了这两个东西长得太像了，以后换一个变量名吧

43.除很多个数还忘记给这个式子打括号

  1. t=(r[a]*r[a]-r[b]*r[b]+dis*dis)/2*dis*r[a];

这是一个余弦定理
然而显然
我没有打上括号

  1. t=(r[a]*r[a]-r[b]*r[b]+dis*dis)/(2*dis*r[a]);

44.冒泡排序不会写！！！

我的天我为什么把i+1打成l+1
我对于小数据用冒泡排序暴力排序……然而我gg了

  1. siji(i,l,r) {
  2.         siji(j,l+1,r) {
  3.         if(p[j].y < p[i].y) swap(p[j],p[i]);
  4.         }
  5. }

有一个地方不对……就是第二层循环不是l+1啊啊啊啊是i+1啊啊啊啊

  1. siji(i,l,r) {
  2.         siji(j,i+1,r) {
  3.         if(p[j].y < p[i].y) swap(p[j],p[i]);
  4.         }
  5. }

45.把遍历边时的next写成to

  1. for(int i=head[u];i;i=edge[i].to) {
  2.     int v=edge[i].to;
  3.     if(!vis[v] && v!=fa) {
  4.         res=max(res,getdep(v,u));
  5.     }
  6. }

叫我RE小能手

  1. for(int i=head[u];i;i=edge[i].next) {
  2.     int v=edge[i].to;
  3.     if(!vis[v] && v!=fa) {
  4.         res=max(res,getdep(v,u));
  5.     }
  6. }

46.树分治时合并两个树忘记将数组的长度设成0

  1. void solve(int u) {
  2.     int G=calcG(u);
  3.     vis[G]=1;
  4.     int mxdp=0;
  5.     for(int i=head[G];i;i=edge[i].next) {
  6.     int v=edge[i].to;
  7.     if(!vis[v]) {
  8.         int maxdep=getdep(v,G);
  9.         mxdp=max(mxdp,maxdep);
  10.         ver[maxdep].push_back(make_pair(v,edge[i].val));
  11.     }
  12.     }
  13.     siji(i,0,mxdp) L[i]=Z[i]=-inf;
  14.     L[0]=0;
  15.     siji(i,0,mxdp) {
  16.     int siz=ver[i].size(); 
  17.     xiaosiji(j,0,siz) {
  18.         calc(ver[i][j].fi,ver[i][j].se);
  19.         int b=min(k,Ln);
  20.         ql=1;qr=0;
  21.         while(b>=0) {
  22.             while(ql<=qr && L[que[qr]]<=L[b]) {--qr;}
  23.             que[++qr]=b;--b;
  24.         }
  25.         siji(h,0,Zn) {
  26.         if(Z[h]==-inf) continue;
  27.         while(ql<=qr && h+que[ql]+crowd[G]>k) ++ql;
  28.         if(ql<=qr && L[que[ql]]!=-inf) {
  29.             ans=max(ans,L[que[ql]]+Z[h]);
  30.         }
  31.         if(ql>qr || h>k) break;
  32.         }
  33.         if(Ln<Zn) Ln=Zn;
  34.         siji(h,0,Zn) L[h]=max(L[h],Z[h]);
  35.         siji(h,0,Zn) Z[h]=-inf;
  36.     }
  37.     ver[i].clear();
  38.     }
  39.     for(int i=head[G];i;i=edge[i].next) {
  40.     int v=edge[i].to;
  41.     if(!vis[v]) solve(v);
  42.     }
  43. }

Ln和Zn都应该是设成0

  1. void solve(int u) {
  2.     int G=calcG(u);
  3.     vis[G]=1;
  4.     int mxdp=0;
  5.     for(int i=head[G];i;i=edge[i].next) {
  6.     int v=edge[i].to;
  7.     if(!vis[v]) {
  8.         int maxdep=getdep(v,G);
  9.         mxdp=max(mxdp,maxdep);
  10.         ver[maxdep].push_back(make_pair(v,edge[i].val));
  11.     }
  12.     }
  13.     siji(i,0,mxdp) L[i]=Z[i]=-inf;
  14.     L[0]=0;
  15.     Ln=0;
  16.     siji(i,0,mxdp) {
  17.     int siz=ver[i].size(); 
  18.     xiaosiji(j,0,siz) {
  19.         Zn=0;
  20.         calc(ver[i][j].fi,ver[i][j].se);
  21.         int b=min(k,Ln);
  22.         ql=1;qr=0;
  23.         while(b>=0) {
  24.             while(ql<=qr && L[que[qr]]<=L[b]) {--qr;}
  25.             que[++qr]=b;--b;
  26.         }
  27.         siji(h,0,Zn) {
  28.         if(Z[h]==-inf) continue;
  29.         while(ql<=qr && h+que[ql]+crowd[G]>k) ++ql;
  30.         if(ql<=qr && L[que[ql]]!=-inf) {
  31.             ans=max(ans,L[que[ql]]+Z[h]);
  32.         }
  33.         if(ql>qr || h>k) break;
  34.         }
  35.         if(Ln<Zn) Ln=Zn;
  36.         siji(h,0,Zn) L[h]=max(L[h],Z[h]);
  37.         siji(h,0,Zn) Z[h]=-inf;
  38.     }
  39.     ver[i].clear();
  40.     }
  41.     for(int i=head[G];i;i=edge[i].next) {
  42.     int v=edge[i].to;
  43.     if(!vis[v]) solve(v);
  44.     }
  45. }

47.(维修数列）哨兵节点的值没有设成负无穷

我设的是个0啊啊啊啊啊啊啊啊啊
最后的答案该输出负数的时候我输出0啊啊啊啊啊啊

48.我犯了一个忘记对称性的错误

  1. if(id<=mid) {
  2.     Insert(tr[y].lc,tr[x].lc,l,mid,id,on);
  3. }
  4. else {
  5.     Insert(tr[y].lc,tr[x].rc,mid+1,r,id,on);
  6. }

主席树
似乎……有什么地方不对？？？
为啥我一直没看出来……

  1. if(id<=mid) {
  2.     Insert(tr[y].lc,tr[x].lc,l,mid,id,on);
  3. }
  4. else {
  5.     Insert(tr[y].rc,tr[x].rc,mid+1,r,id,on);
  6. }

49.sort unique lower_bound这些东西都是开区间

  1. m=unique(num+1,num+n+cnt)-num-1;

没打+1的我真是瞎了

  1. m=unique(num+1,num+n+cnt+1)-num-1;

附上一个lower_bound正确食用方式

  1. m = lower_bound(num + 1,num + n + cnt + 1) - num;

这回没有-1哦！

50.FFT的一个手误

我要服了我自己了！！！！
f**k！

  1. void FFT(complex *p,int l,int on) {
  2.     brc(p,l);
  3.     complex u,t;
  4.     for(int h=2;h<=l;h<<=1) {
  5.         complex wn(cos(on*2*PI/l),sin(on*2*PI/l));
  6.         for(int k=0;k<l;k+=h) {
  7.             complex w(1.0,0);
  8.             for(int j=k;j<k+h/2;++j) {
  9.                 u=p[j];
  10.                 t=w*p[j+h/2];
  11.                 p[j]=u+t;
  12.                 p[j+h/2]=u-t;
  13.                 w=w*wn;
  14.             }
  15.         }
  16.     }
  17.     if(on==-1) {
  18.         xiaosiji(i,0,l) p[i].r/=l;
  19.     }
  20. }

看起来似乎很正常？？？

  1. void FFT(complex *p,int l,int on) {
  2.     brc(p,l);
  3.     complex u,t;
  4.     for(int h=2;h<=l;h<<=1) {
  5.         complex wn(cos(on*2*PI/h),sin(on*2*PI/h));
  6.         for(int k=0;k<l;k+=h) {
  7.             complex w(1.0,0);
  8.             for(int j=k;j<k+h/2;++j) {
  9.                 u=p[j];
  10.                 t=w*p[j+h/2];
  11.                 p[j]=u+t;
  12.                 p[j+h/2]=u-t;
  13.                 w=w*wn;
  14.             }
  15.         }
  16.     }
  17.     if(on==-1) {
  18.         xiaosiji(i,0,l) p[i].r/=l;
  19.     }
  20. }

是/h啊……每次旋转因子是按递归层数不同旋转角度不一样的……啊……

51.为什么受伤的总是FFT

  1. void FFT(complex *p,int l,int on) {
  2.     brc(p,l);
  3.     complex u,t;
  4.     for(int h=2;h<=l;h<<=1) {
  5.         complex wn(cos(on*2*PI/h),sin(on*2*PI/h));
  6.         for(int k=0;k<l;k+=h) {
  7.             complex w(1.0,0);
  8.             for(int j=0;j<k+h/2;++j) {
  9.                 u=p[j];
  10.                 t=w*p[j+h/2];
  11.                 p[j]=u+t;
  12.                 p[j+h/2]=u-t;
  13.                 w=w*wn;
  14.             }
  15.         }
  16.     }
  17.     if(on==-1) {
  18.         xiaosiji(i,0,l) p[i].r/=l;
  19.     }
  20. }

第三层的循环从k开始啊啊啊啊
因为我们枚举递归层数，把序列分成h长的小段，k是这个小段的起点啊啊啊啊

  1. void FFT(complex *p,int l,int on) {
  2.     brc(p,l);
  3.     complex u,t;
  4.     for(int h=2;h<=l;h<<=1) {
  5.         complex wn(cos(on*2*PI/h),sin(on*2*PI/h));
  6.         for(int k=0;k<l;k+=h) {
  7.             complex w(1.0,0);
  8.             for(int j=k;j<k+h/2;++j) {
  9.                 u=p[j];
  10.                 t=w*p[j+h/2];
  11.                 p[j]=u+t;
  12.                 p[j+h/2]=u-t;
  13.                 w=w*wn;
  14.             }
  15.         }
  16.     }
  17.     if(on==-1) {
  18.         xiaosiji(i,0,l) p[i].r/=l;
  19.     }
  20. }

52.主席树的合并

  1. node *merge(node *x,node *y) {
  2.     if(y==null) {
  3.         ++x->cnt;
  4.         return x;
  5.     }
  6.     if(x==null) {
  7.         ++y->cnt;
  8.         return y;
  9.     }
  10.     node *res=Newnode();
  11.     res->lc = merge(x->lc,y->lc);
  12.     res->rc = merge(x->rc,y->rc);
  13.     res->sum = res->lc->sum + res->rc->sum;
  14.     return res;
  15. }

倒数第二行不能那么写啊……
因为合并一个节点的时候……这个节点显然可以是最后一个节点啊
然后它的两个儿子就什么值也没有，这棵树的值就全错了

  1. node *merge(node *x,node *y) {
  2.     if(y==null) {
  3.         ++x->cnt;
  4.         return x;
  5.     }
  6.     if(x==null) {
  7.         ++y->cnt;
  8.         return y;
  9.     }
  10.     node *res=Newnode();
  11.     res->lc = merge(x->lc,y->lc);
  12.     res->rc = merge(x->rc,y->rc);
  13.     res->sum = x->sum + y->sum;
  14.     return res;
  15. }

53.震惊！树链剖分套主席树为何会TLE

  1. ll PathQuery(int x,int y) {
  2.     ll res = 0;
  3.     while(top[x] != top[y]) {
  4.         if(dep[top[x]] < dep[top[y]]) swap(x,y);
  5.         res += Query(rt[cur_time],1,n,pos[top[x]],pos[x],0,0);
  6.     }
  7.     if(dep[x] > dep[y]) swap(x,y);
  8.     res += Query(rt[cur_time],1,n,pos[x],pos[y],0,0);
  9.     return res;
  10. }

似乎？？？？
这不就死循环了吗？？？！！！

  1. ll PathQuery(int x,int y) {
  2.     ll res = 0;
  3.     while(top[x] != top[y]) {
  4.         if(dep[top[x]] < dep[top[y]]) swap(x,y);
  5.         res += Query(rt[cur_time],1,n,pos[top[x]],pos[x],0,0);
  6.         x = fa[top[x]];//………………
  7.     }
  8.     if(dep[x] > dep[y]) swap(x,y);
  9.     res += Query(rt[cur_time],1,n,pos[x],pos[y],0,0);
  10.     return res;
  11. }

我莫不是个煞笔

54.单调栈又双叒叕跪啦？？？？

  1. void process(int st,int ed,int l,int r) {
  2.     top = 0;sumval = 0;
  3.     for(int i = st + 1 ; i <= ed ; ++i) {
  4.         int cnt = 1;
  5.         if(top >= 1 && height[sa[i]] < height[sa[stk[top]]]) {
  6.             cnt += siz[top];
  7.             sumval -= value[top];
  8.             --top;
  9.         }
  10.         if(sa[i - 1] >= l && sa[i - 1] <= r) {
  11.             --cnt;
  12.         }
  13.         if(cnt != 0) {
  14.             stk[++top] = i;
  15.             value[top] = 1LL * cnt * (height[sa[i]] - k + 1);
  16.             siz[top] = cnt;
  17.             sumval += value[top];
  18.         }
  19.         if(sa[i] >= l && sa[i] <= r) ans += sumval;
  20.     }
  21. }

我还看了好久
后来猛然发现……单调栈的弹出不应该是while吗？？？

  1. void process(int st,int ed,int l,int r) {
  2.     top = 0;sumval = 0;
  3.     for(int i = st + 1 ; i <= ed ; ++i) {
  4.         int cnt = 1;
  5.         while(top >= 1 && height[sa[i]] < height[sa[stk[top]]]) {
  6.             cnt += siz[top];
  7.             sumval -= value[top];
  8.             --top;
  9.         }
  10.         if(sa[i - 1] >= l && sa[i - 1] <= r) {
  11.             --cnt;
  12.         }
  13.         if(cnt != 0) {
  14.             stk[++top] = i;
  15.             value[top] = 1LL * cnt * (height[sa[i]] - k + 1);
  16.             siz[top] = cnt;
  17.             sumval += value[top];
  18.         }
  19.         if(sa[i] >= l && sa[i] <= r) ans += sumval;
  20.     }
  21. }

55 LCT的注意事项

  1. void Rotate(node *u) {
  2.     node *v = u->fa , *w = v->fa;
  3.     node *b = u == v->lc ? u->rc : u->lc;
  4.     if(w) (v == w->lc ? w->lc : w->rc) = u;
  5.     v->fa = u; u->fa = w;
  6.     if(b) b->fa = v;
  7.     if(u == v->lc) {v->lc = b; u->rc = v;}
  8.     else {v->rc = b;u->lc = v;}
  9. }

这是一个普通的rotate,然而在LCT中，w的两个儿子可能都不是v

  1. void Rotate(node *u) {
  2.     node *v = u->fa , *w = v->fa;
  3.     node *b = u == v->lc ? u->rc : u->lc;
  4.     if(w && !isRoot(v)) (v == w->lc ? w->lc : w->rc) = u;
  5.     v->fa = u; u->fa = w;
  6.     if(b) b->fa = v;
  7.     if(u == v->lc) {v->lc = b; u->rc = v;}
  8.     else {v->rc = b;u->lc = v;}
  9. }

56.优化后新的东西可能被之前遗留的一些break影响了

  1. if(c != 1) {
  2.     for(int i = 1 ; i <= tot ; ++i) {
  3.         pow_c[i][1] = c;
  4.         pow_c[i][0] = 1;
  5.         if(c > dep[i]) {
  6.             pow_c[i][0] = 0;
  7.             break;
  8.         }
  9.         for(int j = 2 ; ; ++j) {
  10.             pow_c[i][j] = pow_c[i][j - 1] * c;
  11.             if(pow_c[i][j] < dep[i]) {
  12.                 ++pow_c[i][0];
  13.             }
  14.             else break;
  15.         }
  16.         for(int j = pow_c[i][0] + 1; j <= 10000 ; ++j) {
  17.             pow_c[i][j] = pow_c[i][j - 1] * c  % dep[i];
  18.         }
  19.         pow_t[i][0] = 1;
  20.         pow_t[i][1] = pow_c[i][10000];
  21.         for(int j = 2 ; j <= 10000 ; ++j) {
  22.             pow_t[i][j] = pow_t[i][j - 1] * pow_t[i][1] % dep[i];
  23.         }
  24.     }
  25. }

SHOI2017相逢是问候，决定快速处理快速幂，分块，每设存10000个c相乘和10000个t相乘，然后快速幂的时候可以快速查表
然后……我没发现这个里面我写了

  1. if(c > dep[i]) {
  2.     pow_c[i][0] = 0;
  3.     break;
  4. }

然后我就g了，优化一个东西的时候看看前面是不是有些东西和它冲突了

57.我莫不是个煞笔转世。。。

为什么受伤的总是lct
为什么，它会T？

  1. bool isRoot(int u) {
  2.     if(lct[u].fa) return true;
  3.     return lct[lct[u].fa].lc != u && lct[lct[u].fa].rc != u;
  4. }

这个故事告诉我们，数组版的LCT如果TLE是你指针版的RE（微笑脸）
啥？你跟我说这个isRoot没错啊
呵呵

  1. bool isRoot(int u) {
  2.     if(!lct[u].fa) return true;
  3.     return lct[lct[u].fa].lc != u && lct[lct[u].fa].rc != u;
  4. }

（卒）

58.为什么这个点分治居然能过80

  1. int calcG(int x) {
  2.     que[ql = qr = 1] = x;
  3.     fa[x] = 0;
  4.     while(ql <= qr) {
  5.     int now = que[ql++];
  6.     size[now] = 1,son[now] = 0;
  7.     for(int i = head[now]; i; i = edge[i].next) {
  8.         int v = edge[i].to;
  9.         if(v != fa[now] && !hascalc[v]) {
  10.         que[++qr] = v;
  11.         fa[v] = now;
  12.         }
  13.     }
  14.     }
  15.     int res = qr;
  16.     for(int i = qr ; i >= 1 ; --i) {
  17.     int u = que[i];
  18.     size[fa[u]] += size[u];
  19.     if(size[u] > son[fa[u]]) son[fa[u]] = size[u];
  20.     if(son[u] < qr - size[u]) son[u] = qr - size[u];
  21.     if(son[res] > son[u]) res = u;
  22.     }
  23.     return res;
  24. }

啥，你说你没觉得哪错了……
res = qr啊……明明是res = que[qr]才是这个树里的点，都跑到别的树里岂不尴尬啦qwq

59.又见FFT

  1. void brc(complicated *p) {
  2.     for(int i = 0, j = 0; i < L - 1; ++i) {
  3.     if(i < j) swap(p[i],p[j]);
  4.     int k = L / 2;
  5.     while(j >= k) {
  6.         j -= k;
  7.         k >>= 1;
  8.     }
  9.     j += k;
  10.     }
  11. }

我们把最高位当最低位，而当i = L - 1的时候，虽然不用翻转，但是会使得k减到0，从而死循环，就当为了节省一条语句吧= =

60.写好树分治是我一辈子的事业= =

  1. void dfs(int u) {
  2.     int G = calc_G(u);
  3.     vis[u] = 1;
  4.     for(int i = 1 ; i <= qr ; ++i) aux[que[i]].push_back(G);
  5.     for(int i = head[G] ; i ; i = edge[i].next) {
  6.     int v = edge[i].to;
  7.     if(!vis[v]) dfs(v);
  8.     }
  9. }

啥，你说错的很明显= =
对啊
是很明显vis[u] = 1和vis[G] = 1

  1. void dfs(int u) {
  2.     int G = calc_G(u);
  3.     vis[G] = 1;
  4.     for(int i = 1 ; i <= qr ; ++i) aux[que[i]].push_back(G);
  5.     for(int i = head[G] ; i ; i = edge[i].next) {
  6.     int v = edge[i].to;
  7.     if(!vis[v]) dfs(v);
  8.     }
  9. }

61.为什么我爆搜还错

  1. void calc(int u) {
  2.     que[ql = qr = 1] = u;
  3.     fa[u] = 0;
  4.     memset(dp[u],0,sizeof(dp[u]));
  5.     while(ql <= qr) {
  6.     int now = que[ql++];
  7.     for(int i = head[now] ; i ; i = edge[i].next) {
  8.         int v = edge[i].to;
  9.         if(!vis[v] && fa[u] != v) {
  10.         fa[v] = u;
  11.         memcpy(dp[v],dp[u],sizeof(dp[now]));
  12.         insert(v,val[v]);
  13.         que[++qr] = v;
  14.         }
  15.     }
  16.     }
  17. }

啥……你说很正常，我传参就不该用u……因为我很容易认为当前节点就是u

  1. void calc(int u) {
  2.     que[ql = qr = 1] = u;
  3.     fa[u] = 0;
  4.     memset(dp[u],0,sizeof(dp[u]));
  5.     while(ql <= qr) {
  6.     int now = que[ql++];
  7.     for(int i = head[now] ; i ; i = edge[i].next) {
  8.         int v = edge[i].to;
  9.         if(!vis[v] && fa[now] != v) {
  10.         fa[v] = now;
  11.         memcpy(dp[v],dp[now],sizeof(dp[now]));
  12.         insert(v,val[v]);
  13.         que[++qr] = v;
  14.         }
  15.     }
  16.     }
  17. }

62.关于一个我自编自创的可持久化并查集

这个故事告诉我们不能乱编数据结构？可是我不会啊
这应该是部分可持久化，是个线性的修改

  1. void Merge(int u,int v,bool rb) {
  2.     if(getfa(u,rb) == getfa(v,rb)) return;
  3.     fa[v].push_back(getfa(u,rb));
  4.     if(rb) st.push(v);
  5. }

啥，你说你看不懂
我也看不懂
首先应该是而不是其次是的值需要被存下来，因为我们还要往栈里扔这个东西

  1. void Merge(int u,int v,bool rb) {
  2.     int g = getfa(v,rb),q = getfa(u,rb);
  3.     if(g == q) return;
  4.     fa[g].push_back(q);
  5.     if(rb) st.push(g);
  6. }

63.我不知道为什么我写好了一个函数忘了调用

  1. void add(int u,int v,int c) {
  2.     edge[++sumE].to = v;
  3.     edge[sumE].next = head[u];
  4.     edge[sumE].cap = c;
  5.     head[u] = sumE;
  6. }
  7. void addtwo(int u,int v,int c) {
  8.     if(u == S) Sflow += c;
  9.     add(u,v,c);add(v,u,0);
  10. }
  11. for(int i = 1 ; i <= N ; ++i) {
  12.     if(deg[i] > 0) add(S,i,deg[i]);
  13.     else add(i,T,-deg[i]);
  14. }

好几次了
我都把addtwo写成了add

  1. for(int i = 1 ; i <= N ; ++i) {
  2.     if(deg[i] > 0) addtwo(S,i,deg[i]);
  3.     else addtwo(i,T,-deg[i]);
  4. }

64.却写不对那网络流

我TM是傻x
fuck you fuck me fuck my life

  1. void addtwo(int u,int v,int c) {
  2.     add(u,v,c);add(v,u,c);
  3. }

大家好好看这是我网络流的加边！

  1. void addtwo(int u,int v,int c) {
  2.     add(u,v,c);add(v,u,0);
  3. }

我居然这道题还有40可真是谢谢出题人

65.指数取模取模MOD - 1！！！

  1.     two[i] = fpow(2,C(n - 1,2));

C(n,m)是一个组合数，qumo
我愣是没找出来WA的原因
后来找到了我以前写的代码（多项式求逆，发现指数要取模MOD - 1 = =)

  1.     two[i] = fpow(2,1LL * i * (i - 1) / 2 % (MOD - 1));

66.关于多项式求逆元指数的上界

  1. friend void calc_Inverse(const poly &f,poly &g,int e) {
  2.     if(e == 1) {
  3.         g.a[0] = fpow(f.a[0],MOD - 2);
  4.         g.deg = 0;
  5.         return;
  6.     }
  7.     calc_Inverse(f,g,(e + 1) >> 1);
  8.     int M = 1;while(M <= e - 1 + g.deg) M <<= 1;
  9.     poly t = f;
  10.     for(int i = e ; i < M ; ++i) t.a[i] = 0;
  11.     for(int i = g.deg + 1 ; i < M ; ++i) g.a[i] = 0;
  12.     NTT(g,1,M);NTT(t,1,M);
  13.     for(int i = 0 ; i < M ; ++i) {
  14.         g.a[i] = 1LL * g.a[i] * (2 + MOD - 1LL * g.a[i] * t.a[i] % MOD) % MOD;
  15.     }
  16.     NTT(g,-1,M);
  17.     for(int i = e ; i < M ; ++i) g.a[i] = 0;
  18.     g.deg = e - 1;
  19. }

这个M呢……显然看看我们下面的乘法式，指数最大的是g.deg * 2 + t.deg
我因为把on和L填反和这个指数设置的问题debug了一上午……
md我简直zz

  1. friend void calc_Inverse(const poly &f,poly &g,int e) {
  2.     if(e == 1) {
  3.         g.a[0] = fpow(f.a[0],MOD - 2);
  4.         g.deg = 0;
  5.         return;
  6.     }
  7.     calc_Inverse(f,g,(e + 1) >> 1);
  8.     int M = 1;while(M <= g.deg * 2 + e - 1) M <<= 1;
  9.     poly t = f;t.deg = e - 1;
  10.     for(int i = e ; i < M ; ++i) t.a[i] = 0;
  11.     for(int i = g.deg + 1 ; i < M ; ++i) g.a[i] = 0;
  12.     NTT(g,1,M);NTT(t,1,M);
  13.     for(int i = 0 ; i < M ; ++i) {
  14.         g.a[i] = 1LL * g.a[i] * (2 + MOD - 1LL * g.a[i] * t.a[i] % MOD) % MOD;
  15.     }
  16.     NTT(g,-1,M);
  17.     for(int i = e ; i < M ; ++i) g.a[i] = 0;
  18.     g.deg = e - 1;
  19. }

67.一个变量名给我带来的错觉

  1. int64 dis[MAXN];
  2. ……
  3. ……
  4. ……
  5. void Add_Line(int u,Line g) {
  6.     int l = dis[id[tr[u].L]],r = dis[id[tr[u].R]];
  7.     tr[u].val = min(tr[u].val,min(g.cal(l),g.cal(r)));
  8.     if(!tr[u].cover) {tr[u].f = g;tr[u].cover = 1;return;}
  9.     else {
  10.         int mid = (tr[u].L + tr[u].R) >> 1;
  11.         mid = dis[id[mid]];
  12.         if(tr[u].f.cal(l) >= g.cal(l) && tr[u].f.cal(r) >= g.cal(r)) {
  13.             tr[u].f = g;return;
  14.         }
  15.         else if(tr[u].f.cal(l) <= g.cal(l) && tr[u].f.cal(r) <= g.cal(r)) return;
  16.         else if(tr[u].f.cal(l) <= g.cal(l)) {
  17.             if(cross(tr[u].f,g) <= mid) {Add_Line(u << 1,tr[u].f);tr[u].f = g;}
  18.             else Add_Line(u << 1 | 1,g);
  19.         }
  20.         else {
  21.             if(cross(tr[u].f,g) <= mid) {Add_Line(u << 1,g);}
  22.             else {Add_Line(u << 1 | 1,tr[u].f);tr[u].f = g;}
  23.         }
  24.     }
  25. }

呀，l,r,mid显然就是线段树的区间端点嘛，所以是int

woc我怎么一直WA

……
……
……
去**的l是线段树的区间端点，你不是下面都把l赋成dis了吗，md。。

  1. void Add_Line(int u,Line g) {
  2.     int64 l = dis[id[tr[u].L]],r = dis[id[tr[u].R]];
  3.     tr[u].val = min(tr[u].val,min(g.cal(l),g.cal(r)));
  4.     if(!tr[u].cover) {tr[u].f = g;tr[u].cover = 1;return;}
  5.     else {
  6.         int64 mid = (tr[u].L + tr[u].R) >> 1;
  7.         mid = dis[id[mid]];
  8.         if(tr[u].f.cal(l) >= g.cal(l) && tr[u].f.cal(r) >= g.cal(r)) {
  9.             tr[u].f = g;return;
  10.         }
  11.         else if(tr[u].f.cal(l) <= g.cal(l) && tr[u].f.cal(r) <= g.cal(r)) return;
  12.         else if(tr[u].f.cal(l) <= g.cal(l)) {
  13.             if(cross(tr[u].f,g) <= mid) {Add_Line(u << 1,tr[u].f);tr[u].f = g;}
  14.             else Add_Line(u << 1 | 1,g);
  15.         }
  16.         else {
  17.             if(cross(tr[u].f,g) <= mid) {Add_Line(u << 1,g);}
  18.             else {Add_Line(u << 1 | 1,tr[u].f);tr[u].f = g;}
  19.         }
  20.     }
  21. }

68.误把trie树的建树顺序当成BFS序

你说我也是zz……

69.有些时候RE要开O2才能查出来

这个似乎被zzt指出好几次了啊
“我没WA（RE）”
“你开O2了吗”
“（woc）没”
然后发现自己真的WAorRE……惨兮兮

70.if的速度是while的六倍

然而我用三目运算符

71.一个SAM的手误

  1. void build_sam(int l,int c) {
  2.     node *nowp = tail++,*p;
  3.     nowp->len = l;nowp->cnt = 1;
  4.     for(p = last ; p && !p->nxt[c]; p = p->par) {
  5.         p->nxt[c] = nowp;
  6.     }
  7.     if(!p) nowp->par = root;
  8.     else {
  9.         node *q = p->nxt[c];
  10.         if(q->len == p->len + 1) nowp->par = q;
  11.         else {
  12.             node *copyq = tail++;
  13.             *copyq = *q;
  14.             copyq->len = p->len + 1;copyq->cnt = 0;
  15.             q->par = nowp->par = copyq;
  16.             for(; p && p->nxt[c] == q ; p = p->par) {
  17.                 p->nxt[c] = q;
  18.             }
  19.         }
  20.     }
  21.     last = nowp;
  22. }

然后我们干啥呢
把第17行的q改成copyq啊md

  1. void build_sam(int l,int c) {
  2.     node *nowp = tail++,*p;
  3.     nowp->len = l;nowp->cnt = 1;
  4.     for(p = last ; p && !p->nxt[c]; p = p->par) {
  5.         p->nxt[c] = nowp;
  6.     }
  7.     if(!p) nowp->par = root;
  8.     else {
  9.         node *q = p->nxt[c];
  10.         if(q->len == p->len + 1) nowp->par = q;
  11.         else {
  12.             node *copyq = tail++;
  13.             *copyq = *q;
  14.             copyq->len = p->len + 1;copyq->cnt = 0;
  15.             q->par = nowp->par = copyq;
  16.             for(; p && p->nxt[c] == q ; p = p->par) {
  17.                 p->nxt[c] = copyq;
  18.             }
  19.         }
  20.     }
  21.     last = nowp;
  22. }

72.建后缀树了解一下

  1. void build_suffix_tree() {
  2.     Ncnt = tail - pool;
  3.     for(int i = 0 ; i < Ncnt ; ++i) {
  4.         c[pool[i].len]++;
  5.     }
  6.     for(int i = 1 ; i <= N ; ++i) c[i] += c[i - 1];
  7.     for(int i = 0 ; i < Ncnt ; ++i) {
  8.         que[c[pool[i].len]--] = &pool[i];
  9.     }
  10.     for(int i = 1 ; i <= Ncnt ; ++i) {
  11.         if(que[i]->par) {
  12.             int f = que[i]->par - pool + 1;
  13.             fa[i][0] = f;
  14.             add(f,i,que[i]->len - que[i]->par->len);
  15.             add(i,f,que[i]->len - que[i]->par->len);
  16.         }
  17.         if(que[i]->cnt) {id[N - que[i]->len + 1] = i;pos[i] = N - que[i]->len + 1;}
  18.     }
  19. }

额，父亲用的是在pool里的标号
儿子用的是在que里的标号
我在干什么

  1. void build_suffix_tree() {
  2.     Ncnt = tail - pool;
  3.     for(int i = 0 ; i < Ncnt ; ++i) {
  4.         c[pool[i].len]++;
  5.     }
  6.     for(int i = 1 ; i <= N ; ++i) c[i] += c[i - 1];
  7.     for(int i = 0 ; i < Ncnt ; ++i) {
  8.         que[c[pool[i].len]--] = &pool[i];
  9.     }
  10.     for(int i = 1 ; i <= Ncnt ; ++i) {
  11.         int u = que[i] - pool + 1;
  12.         if(que[i]->par) {
  13.             int f = que[i]->par - pool + 1;
  14.             fa[u][0] = f;
  15.             add(f,u,que[i]->len - que[i]->par->len);
  16.             add(u,f,que[i]->len - que[i]->par->len);
  17.         }
  18.         if(que[i]->cnt) {id[N - que[i]->len + 1] = u;pos[u] = N - que[i]->len + 1;}
  19.     }
  20. }

73.离散化后会新开一个变量，不要用原来的变量

  1. sort(val + 1,val + N + 1);
  2. tot = unique(val + 1,val + N + 1) - val - 1;
  3. lower_bound(val + 1,val + N + 1);

这个时候会出锅（手动微笑
事实上是

  1. lower_bound(val + 1,val + tot + 1);

74.我KM又双叒叕写错了！！！！

  1. void KM() {
  2.     for(int i = 1 ; i <= N ; ++i) {
  3.         ex[i][1] = 0;
  4.         ex[i][0] = 1e16;
  5.         for(int j = 1 ; j <= N ; ++j) {
  6.             ex[i][0] = min(ex[i][0],dist(T[i],S[j]));
  7.         }
  8.     }
  9.     for(int i = 1 ; i <= N ; ++i) {
  11.         for(int j = 1 ; j <= N ; ++j) slack[j] = 1e16;
  12.         memset(vis,0,sizeof(vis));
  13.         while(!Match(i)) {
  15.             db d = 1e16;
  16.             for(int j = 1 ; j <= N ; ++j) d = min(d,slack[j]);
  17.             for(int j = 1 ; j <= N ; ++j) {
  18.                 if(vis[j][0]) ex[j][0] += d;
  19.                 if(vis[j][1]) {ex[j][1] -= d;slack[j] -= d;}
  20.             }
  21.             memset(vis,0,sizeof(vis));
  22.         }
  23.     }
  24.     for(int j = 1 ; j <= N ; ++j) ans += dist(T[matc[j]],S[j]);
  25. }

这个slack的！只对！没有访问过的右边点才需要更新！以及d也是对那个取模

  1. void KM() {
  2.     for(int i = 1 ; i <= N ; ++i) {
  3.         ex[i][1] = 0;
  4.         ex[i][0] = 1e16;
  5.         for(int j = 1 ; j <= N ; ++j) {
  6.             ex[i][0] = min(ex[i][0],dist(T[i],S[j]));
  7.         }
  8.     }
  9.     for(int i = 1 ; i <= N ; ++i) {
  11.         for(int j = 1 ; j <= N ; ++j) slack[j] = 1e16;
  12.         memset(vis,0,sizeof(vis));
  13.         while(!Match(i)) {
  15.             db d = 1e16;
  16.             for(int j = 1 ; j <= N ; ++j) if(!vis[j][1]) d = min(d,slack[j]);//这里
  17.             for(int j = 1 ; j <= N ; ++j) {
  18.                 if(vis[j][0]) ex[j][0] += d;
  19.                 if(vis[j][1]) ex[j][1] -= d;
  20.                 else slack[j] -= d; //还有这里
  21.             }
  22.             memset(vis,0,sizeof(vis));
  23.         }
  24.     }
  25.     for(int j = 1 ; j <= N ; ++j) ans += dist(T[matc[j]],S[j]);
  26. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注