防错笔记
枫林晚
2018-03-10 19:08:32
# 本文章记录所错、易错细节要点。
1.printf("%lld",ans);
printf("%d",ans);
**long long -> %lld**
d -> %d （poj1456 Supermarket）
2.注意数组下标开始地址。
**string：0-strlen-1**
（kmp manancher）
3.注意是否数组内减法（加法）会使越界（或小于0）
注意在取queue，q.pop（）的时候，判断是否为空。 （poj 3784 Median）
**4.注意特殊边界情况：**
n=1;m=0;e<0等等
（poj3013 Big Chirstmas Tree）
5.对于多种数据题型：
（1）注意清空之前的数据。
memset(bian,0,sizeof (struct node)*N)
（poj系列）
（2）poj做题，注意是一组数据还是多组
（poj1325 Machine Schedule）
（3）多组数据中，特判加跳过时，注意输入完该组之后的数据，防止这些垃圾数据被后面一组数据吃掉，影响答案。（时间复杂度，判断是否合法）注意要保证t--（就算是特判跳过，也要带上t--）（zoj 1239Hanoi）
**6.注意输出英文大小写以及标点！**
Yes、YES、No、NO、！、。、？、空格.etc
（poj 1135Domino Effect）（时间复杂度）
7.数位DP注意前导零的处理。
在0~99999（len-1个）时产生。
（luogu 2602数字计数）
8.prim算法中，从优先队列中取出来的一条边一定要**判断两端的点是否已被加入树中。**
if(vis[a]&&vis[b]) bian++,continue;
典例：poj2728Desert King
9.st表中，f[i][j]表示：[i,i+2^j-1]最值。
并且，倍增时必须在**外层循环j**，由小块倍增到大块。
倍增：
```cpp
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1)][j-1];
}
```
查询：
```cpp
scanf("%d%d",&l,&r);
int len=log2(r-l+1);
ans=min(st[l][lrn],st[r+1-(1<<len)][len]);
```
10.输入边的循环时，注意是：for(1,m,i++)
不是for(1,n,i++) 要**分清点数n和边数m**。
11.邻接表建无向图：**bian[2倍M]** 双向。
RE无数。（luogu3629 巡逻）
12.有查询更改操作的题中，先读入“q”，分情况操作，**不要一次性读完之后的具体操作**。以免用字符读入两位数爆零。
（寒假%你赛，luogu1383高级打字机）
13.memset时，检查是否全部清空。
（poj3694）
14.LCA时，dep[0]=-1;
if(dep[x]<dep[y]) swap(x,y);(注意是小于）
(poj3694)(poj3417)
15.有时候，一张map可能要从上到下循环一遍，再从左到右循环一遍，
即：先是for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
再是for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
**一定注意的是：如果第二次将i定为列号，j定为行号时，找地图时一定要：a[j][i] **
千万不能i，j写反了！！！！（在n!=m的时候就惨爆了）（AC100变爆零）（luogu2825 游戏）（ezoj 游戏）（3.24图论考试）
16.tarjan、边双联通分量时，
第三步染联通块时：
for(int i=1;i<=n;i++)
if(!c[x])
{
dcc++;
dfs(x);
}
（注意大括号位置扩全）
17.树状数组：
1.注意query、add中x的加减以及上下界不要弄混。
2.推荐x+=x&(-x)，而不使用lowbit，不调用函数可以加速。
（HDOJ 5542）
```cpp
int query(int x)
{
int tot=0;
for(;x;x-=x&(-x))
tot+=tr[x];
return tot;
}
void add(int x,int c)
{
for(;x<=n;x+=x&(-x))
tr[x]+=c;
}
```
18.单调队列优化dp，注意单调队列中可以单调的部分是什么，**比较时一定要比较完整。**
f[q[hd]]+kq[hd]+m>f[i]+kf[i]+m
一定不能丢掉一次项，常数项等。
（luogu 瑰丽华尔兹，股票交易）
19.注意，变量设为long long 的时候，**输入记得也用%lld。**~~（实在忘了long long就#define int long long）~~（poj2482 Stars in your window）
20.有许多棵树的时候，**千万不要忘了根节点编号。其中线段树一般根节点都是1**，不要和其他树混淆。
(树链剖分6h鏖战)
21.取模减法的时候，出现了负数，取模后还会是负数，所以要**(x+p)%p;保证正数**
（P3197越狱）
22.线段树常规操作，**不要忘了mod**，不要忘了add时候，**sum+=add×(r-l+1)**