枫林晚 的博客

枫林晚 的博客

防错笔记

posted on 2018-03-10 19:08:32 | under 技巧 |

本文章记录所错、易错细节要点。

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,由小块倍增到大块。 倍增:

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];
 }

查询:

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)

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)