复习计划里的低级错误

复习计划里的低级错误

luoguP2678 跳石头

二分的边界判断应该是

1     for (int mid = (l+r)>>1; l <= r; mid = (l+r)>>1)
2         if (check(mid)) ans = mid, l = mid+1;
3         else r = mid-1;

而不是

1     for (int mid = (l+r)>>1; l < r; mid = (l+r)>>1)
2         if (check(mid)) ans = mid, l = mid+1;
3         else r = mid;

cf230A. Dragons

用sort时候写了cmp结果没调用

luoguP1993 小K的农场

DFSspfa没回溯状态vis[x] = 0

HHHOJ#243. 「NOIP模拟赛 贰」Game

1.没有充分意识到中途爆long long

2.中途的边界条件越界了

loj#10042. 收集雪花

输出的是中间用的变量……

hdu6425Rikka with Badminton

1.调试信息没有删除

2.模数打成98244353……

HHHOJ#256. 「NOIP模拟赛 陆」Fenwick

1.2的幂次没有取模

2.提交框鬼畜了保存的是以前代码

loj#10078. 「一本通 3.2 练习 4」新年好

1.SPFA时候没有pop队首。

2.多个起点的时候把p[i]当成i去做SPFA

bzoj1576: [Usaco2009 Jan]安全路经Travel

堆优化dij，不能标记vis的tag。

bzoj1577: [Usaco2009 Feb]庙会捷运Fair Shuttle

容量没有取min，还以为永久标记线段树打挂了。

bzoj4542: [Hnoi2016]大数

注意莫队要先修改再更新！

主要看情况；有些时候查询和更新会冲突。

例如：

void lAdd(int lbd)
{rSd[sum[lbd]]++, tot+=rSd[sum[lbd-1]], lSd[sum[lbd-1]]++;
}
void rAdd(int rbd)
{lSd[sum[rbd-1]]++, tot+=lSd[sum[rbd]], rSd[sum[rbd]]++;
}
void lErase(int lbd)
{lSd[sum[lbd-1]]--, tot-=rSd[sum[lbd-1]], rSd[sum[lbd]]--;
}
void rErase(int rbd)
{rSd[sum[rbd]]--, tot-=lSd[sum[rbd]], lSd[sum[rbd-1]]--;
}

View Code

luoguP4919 Marisa采蘑菇

1 for (int i=1; i<=m; i++) printf("%dn",ans[q[i].id]);

真是非常要命

bzoj1718: [Usaco2006 Jan] Redundant Paths 分离的路径

1.因为要靠异或找同一条边，所以edgeTot++要放在最后面

2.无向图tarjan之后重建图，再统计连通块的度数：

1 for (int i=1; i<=n; i++)
2     for (int j=head[i]; j!=-1; j=nxt[j])
3         if (i<=edges[j]&&col[i]!=col[edges[j]]) deg[col[i]]++, deg[col[edges[j]]]++;

这里由于无向图，所以要避免重复连边。而且edges[j]很容易打错成edges[i]

loj#10105. 「一本通 3.7 例 1」欧拉回路

第一次打欧拉回路……

 1 void dfs(int x)
 2 {
 3     for (int &i=head[x]; i!=-1; i=nxt[i])
 4     {
 5         int tag = (t==1)?((i+1)>>1):i ,y = i;//这里i会被修改
 6         if (!vis[tag]){
 7             vis[tag] = 1;
 8             dfs(edges[i]);
 9             if (t==1) ans.push_back(y&1?tag:-tag);
10             else ans.push_back(tag);
11         }
12         if (i==-1) return;
13     }
14 }

每一次循环结束之后，都是先执行修改再判断条件。所以如果i==-1，那么先执行的是i=nxt[i]

loj#10106. 「一本通 3.7 例 2」单词游戏

第二道欧拉回路……题挺好，还是细节打挂

有些急的时候容易把 scanf("%s",s+1), m = strlen(s+1); 这个$s+1$容易漏掉。

bzoj1579: [Usaco2009 Feb]Revamping Trails 道路升级

1.dij的时候node重载运算符，>又打成<了

2.如果想要用一个vis[][]加快速度（其实差别不大），那么push进堆的元素要带一个当时的d值，否则会变成假堆，从而整个堆都废了

cf1064D. Labyrinth

BFS最好先判条件再入队，这样省内存并且比较安全（？）

bzoj1093: [ZJOI2007]最大半连通子图

又打了一遍，然而发现：

1. 根据缩点后重建图后的边忘记分开存了
2. 统计方案时候没有判连通块之间的重边
3. 我也不知道为什么tarjan打成了if (dfn[x]!=low[x])……
4. maxm开小了……

bzoj1398: Vijos1382寻找主人 Necklace

 1 #include<bits/stdc++.h>
 2 const int maxn = 1000035;
 3 
 4 bool fl;
 5 int n,sst,tst;
 6 char s[maxn],t[maxn];
 7 
 8 int calc(char *s)
 9 {
10     int i = 0, j = 1, k = 0;
11     while (i < n&&j < n&&k < n)
12     {
13         if (s[(i+k)%n]==s[(j+k)%n]) k++;
14         else{
15             if (s[(i+k)%n] > s[(j+k)%n]) i += k+1;
16             else j += k+1;
17             if (i==j) i++;
18             k = 0;
19         }
20     }
21     return std::min(i, j);
22 }
23 int main()
24 {
25     scanf("%s%s",s,t);
26     fl = 1, n = strlen(s);
27     sst = calc(s), tst = calc(t);
28     for (int i=0; i<n; i++)
29         if (s[(sst+i)%n]!=t[(tst+i)%n]){
30             fl = 0;
31             break;
32         }
33     if (!fl){
34         puts("No");
35         return 0;
36     }else puts("Yes");
37     for (int i=0; i<n; i++)
38         putchar(s[(sst+i)%n]);
39     return 0;
40 }

View Code

calc()里的s打成t了。要注意calc里的操作意义是同一个字符串的最小表示法匹配。

loj#10082. 「一本通 3.3 例 1」Word Rings

1. 已经不知道几次把单向边建成双向边了……
2. 这题是以单词为边，字母为点建图。那么总点数应该是tot而不是n，这种细节经常打挂……

bzoj2442: [Usaco2011 Open]修剪草坪

INF开得不够大……要么以后设成-1算了。这些小细节还是要注意的。

bzoj3626: [LNOI2014]LCA

树剖和线段树都一遍码对。然而因为点从0开始，我重赋成1开始，没有全部改过来浪费了20+mins。

HHHOJ#128. 城市

1. 最早那份树剖、线段树、Kruskal都是一遍码对的……就是查询时候的 ret = std::min(ret, query(1, chain[x]+1, chain[y], 1, n)); +1打错了
2. 然后 printf("infinitely"); 见鬼……
3. 还有区间覆盖操作，因为会覆盖成0，所以标记要设为-1.
4. 因为查询的是区间最大值，那么当L > R的时候应返回一个表示不存在的特殊值，而不是INF

bzoj2238: Mst

边树剖4k，大约30分钟码完。然后RE了一发，发现存边的bool数组开成maxn了……有点能体会LCH当时因为RE没一本的感觉了……

这个，以后还是记得造点大数据运行一下吧。

bzoj2956: 模积和

1. 再一次把逆元抄错……
2. 这里 ll s2 = (n*(m/i)%MO+m*(n/i)%MO)%MO*((i+j)*(j-i+1)/2%MO); 爆了long long……

10.29奇妙的数列

$T=100000,n=10$因为每次 memset sizeof a 所以T掉了……并没有意识到memset这么大的数组是很费时间的

bzoj2006: [NOI2010]超级钢琴

这里ST表的lgs[]开成maxLog了……

HHHOJ#450. 小小 Y 的炮

图方便把lst开成局部变量，于是就每次清空了。

luoguP3386 【模板】二分图匹配

板子这里，

1. 二分图连边的时候，还以为什么单向边双向边的，建了(v,u)的边
2. bitset这里，清零是reset()而不是set(0)

bzoj4950: [Wf2017]Mission Improbable

然而还是板子 if (!vis[mp[x][i]]){ 这里不是 if (!bef[mp[x][i]]){ 

codechef Maximum Tree Path

• T比较大，每次n较小的时候，最好 memset(head, -1, (n+2)<<2); 。
• A*求最值时候， if (1ll*dia*g*mn <= ans) return;
  

这些看似无关紧要的细节实际上影响非常大。

还有这题求带边权直径时候忘记加上边权了

HHHOJ#246. 「NOIP模拟赛 叁」卡车

直径dia忘记开long long了

bzoj1076: [SCOI2008]奖励关

bitset出锅系列

先是 std::bitset<120035> vis[113] 记反了，第一维应该是vis[x]

然后居然不开O2情况下bitset比bool慢得不知道到哪里去

bzoj2243: [SDOI2011]染色

1. maker地方并查集建树， if (get(x)==get(y)) 23333
2. 需要过两端点的线段树特殊操作时候：

1     if (L <= mid&&R > mid){
2         ret = query(rt<<1, L, R, l, mid)+query(rt<<1|1, L, R, mid+1, r);
3         if (f[rt<<1].rc==f[rt<<1|1].lc) ret--;
4         return ret;
5     }    
6     if (L <= mid) ret = query(rt<<1, L, R, l, mid);
7     if (R > mid) ret = query(rt<<1|1, L, R, mid+1, r);

要先判断掉再另两种操作；否则会先将两个操作都执行一次，复杂度原地爆炸。

loj#10209. 「一本通 6.4 例 1」青蛙的约会

中途的 a *= (y-x)/d 需要long long

bzoj2938: [Poi2000]病毒

AC自动机建树时候

 1 void build()
 2 {
 3     for (int i=0; i<=1; i++) f[0][i] = 1;
 4     q.push(1);
 5     while (q.size())
 6     {
 7         int tt = q.front();
 8         q.pop();
 9         for (int i=0; i<=1; i++)
10             if (!f[tt][i]) f[tt][i] = f[fail[tt]][i];
11             else{
12                 fail[f[tt][i]] = f[fail[tt]][i];
13                 if (bad[fail[f[tt][i]]]) bad[f[tt][i]] = 1;
14                 q.push(f[tt][i]);
15             }
16     }
17 }

是 q.push(1); 

bzoj4866: [Ynoi2017]由乃的商场之旅

莫队再一次引入删除与加入操作的顺序出了问题调了很久

1 while (L > q[i].l) --L, Add(L);
2 while (R < q[i].r) ++R, Add(R);
3 while (L < q[i].l) Del(L), ++L;
4 while (R > q[i].r) Del(R), --R;

4568: [Scoi2016]幸运数字

常数意识太差，线性基合并每次query开一个新线性基。

2844: albus就是要第一个出场

求不可重线性基rank时候，忘记把线性基元素拎出来了。

正确姿势应该是：

1 void query(int x)
2 {
3     int i,j;
4     for (i=0, j=0; i<=30; i++)
5         if (p[i]) p[j] = i, ++j;
6     for (i=j-1; i>=0; i--)
7         if ((1<<p[i])&x) ans += (1<<i);　　//这里关键在于+=(1<<i)，为保证是第i个合法元素
8 }

1778: [Usaco2010 Hol]Dotp 驱逐猪猡

输出double类型加了个eps，精度出问题了。

P3834 【模板】可持久化线段树 1（主席树）

模板打挂系列。

1 if (val >= k) return query(a[pre].l, a[rt].l, l, mid, k);
2 return query(a[pre].r, a[rt].r, mid+1, r, k-val);

这里居然给忘了

4756: [Usaco2017 Jan]Promotion Counting

dsu不熟练。删除、染色的时候只有递归层的那个重儿子需要特殊处理的。

1 void color(int x, int c, int del)
2 {
3     update(p[x], c);
4     for (int i=head[x]; i!=-1; i=nxt[i])
5         if (edges[i]!=a[x].fa&&edges[i]!=del)
6             color(edges[i], c, 0);
7 }

luoguP2664 树上游戏

点分治题。边写题边裱。

1 cols = 0;
2 for (int i=1; i<=cols; i++) colEx[col[i]] = 0;

1 getRoot(v, x), size[v] += size[x];

没有及时清空colCnt

3123: [Sdoi2013]森林

• 一直以为数组莫名越界了，结果发现是自己监测的变量的越界了……
• 被题面的testcase鬼畜了

Codeforces Round #536 (Div. 2) 

A题的dx[],dy[]这里，包括了6组（习惯性地以1为下标），但是for t 1..4 ……

C题的maxn想都没想就写了1e5…… 

3396: [Usaco2009 Jan]Total flow 水流

dinic：

这题的超级源点是特殊的点，而不是1。

如果写成了lv[1]=1，那么会导致实际上的lv[S]和其他点平级，因此会出现死循环。

EK：

 f[v] = std::min(f[tmp], edges[i].c-edges[i].f); 这句总会打错

1877: [SDOI2009]晨跑

EK每次增广的初始化漏了flw[S]=INF

因为要拆点，弄混了点与点之间的连边关系。

源汇点和1,n点连边弄错了：为了表示无最大限制，需要连(S,1);(n,T)两条边。而之前我们对每个点都是拆过点的，那么实际上的连边就应是(S,1+n);(n,T).

ICPC 2016 China Final J. Mr.Panda and TubeMaster

EKspfa里面的更新流量 flw[v] = std::min(flw[tmp], edges[i].c-edges[i].f); 打错了。不过居然没WA？

cf1110F. Nearest Leaf

write： void write(ll x){write(x/10);putchar(x%10+'0');} 

线段树：也是没判范围就递归下去了

2406: 矩阵

•  if (lv[x]+=1==lv[v]&&edges[i].f < edges[i].c){ Wall忽略了这个
• 习惯性地把lv[]数组开成maxn，然而这里因为按行列建点，maxNode=2*maxn。突然间又想起LCH在ZJOIRound2上的RE……

2286: [Sdoi2011]消耗战

中间变量要long long，INF开得不够大

P3369 【模板】普通平衡树

为了省代码，delete时候把rt==0的情况也update了一下导致a[0].tot=1

3196: Tyvj 1730 二逼平衡树

getRank求的是<x的个数。值域线段树求前驱后继时候要留点心。

2141: 排队

题目要求维护swap(u,v)；更新答案时一直是假定u < v来处理的……这一种思维惯势很糟糕啊

#180. 今宵是飘逸的利己主义者

因为值域离散化过后是1..1024，所以要输出11位bit而不是10位……

4873: [Shoi2017]寿司餐厅&&1497: [NOI2006]最大获利

网络流老是会把$maxn$和$maxNode$弄混……

#545. 「LibreOJ β Round #7」小埋与游乐场

1. $b_m$:std::sort(b+1, b+n+1);
2. for (q = p; p < m&&b[p]==a[i]; ++p);这里处理两个数列的交；应该是p <= m因为是区间[q,p)
3. 脑子想都没想就写了一个最大费用最大流

4036: [HAOI2015]按位或

再一次把$2^{20}$看成1e5

#185. Monster

FWT时候把转移的多项式和答案多项式弄混了

#188. Polycomp

常数意识的重要性：bitset不要写一些语句很短的（没什么意义的）过程，就可以把暴力从70pts->90pts.

分块遍历所有块：是 n/size+1 而不是 size .

P3804 【模板】后缀自动机

 1     void extend(int c)
 2     {
 3         int p = lst, np = ++tot;
 4         lst = np, len[np] = len[p]+1;
 5         for (; p&&!ch[p][c]; p=fa[p]) ch[p][c] = np;
 6         if (!p) fa[np] = 1;
 7         else{
 8             int q = ch[p][c];
 9             if (len[p]+1==len[q]) fa[np] = q;
10             else{
11                 int nq = ++tot;
12                 len[nq] = len[p]+1;
13                 memcpy(ch[nq], ch[q], sizeof ch[q]);
14 //                for (int i=1; i<=26; i++) ch[nq] = ch[q];
15                 fa[nq] = fa[q], fa[q] = fa[np] = nq;        //fa[q]        Here
16                 for (; ch[p][c]==q; p=fa[p])                //p=fa[p]    Here
17                     ch[p][c] = nq;
18             }
19         }
20         size[np] = 1;
21     }

• ch[]的复制要用memcpy而不是for
• fa[nq]=fa[q]　　nq是对q替代，然后q连边向nq
• 最后的nq替代q过程，是在原先的p上替代

#6401. 字符串

还是SAM： lst = np, len[np] = len[p+1], mx[np] = v; ……

P3387 【模板】缩点

tarjan的更新写成dfn[x] = std::min(dfn[x], low[v]); 

#300. 「湖南省队集训2018 Day5」marshland

偷懒了，总流量限制这么写： for (; lim&&chk; --lim) maxFlow(); 。然而EK里还是原始的写法，也即第一遍进入就是把所有流量跑完了，因此答案就比正解小了。

3676: [Apio2014]回文串

• 对所有的字符标志位置： lst = np, len[np] = len[p]+1, sta[id] = np; //sta[np]=id（Wrong） 
• manacher查询所有回文子串： f.match(id[i-g[i]+2], id[i+g[i]-2]); //id[i-g[i]], id[i+g[i]] 
• extend()完居然没有build()
• 第三次把$2^20$看成$1e5$

cf533A. Berland Miners

n,m打反 for (lst=m; lst>=1; lst--) //lst=n  

#456. 「LJNOIP模拟赛 一 Day1」撸树

存边的数组$u_i,v_i$开成了$maxn$

3.16T2

处理逆元写成inv[i]=(MO-1ll*(MO/i)*inv[MO%i])%MO

P3338 [ZJOI2014]力

1     for (int i=1; i<len; i<<=1)
2     {
3         complex Wn(cos(pi/i), opt*sin(pi/i));
4         for (int j=0, p=i<<1; j<len; j+=p)
5         {
6             complex w(1, 0);
7             for (int k=0; k<i; k++){...}
8         }
9     } 

k应该是从0开始的 

#6045. 「雅礼集训 2017 Day8」价

建边addedge时候，直接向下复制了一行： edges[edgeTot] = Edge(v, u, 0, 0), nxt[edgeTot] = head[u], head[u] = edgeTot, ++edgeTot; 居然还能过40pts

hdu4348 To the moon & 3.19线段树

主要是发现对主席树还存在理解不到位的小漏洞，容易写挂或者混淆标记永久化。标记永久化，主要是可以节省pushdown带来的额外空间开销。这里所指的“空间开销”是由于下传标记而不得不复制的子节点。今天T2 3.19线段树 就是没有标记永久化但是pushdown也没有复制新的节点，那么就有可能在查询一个没有儿子的整段同色区间时候误以为未标记过。再者是关于modify的&rt的，不知道为什么总会写成if (!rt) rt=++tot，实际上每次modify必定会出现一个新节点，所以无论如何都是要新开一个点的。标记永久化的modify中，pushup应该是的 a[rt].val = a[a[rt].l].val+a[a[rt].r].val+1ll*(r-l+1)*(a[rt].tag); 形式，而不能在前面就判断掉。

还有一个回溯回收节点的技巧，即ver = read(), tot = rt[ver+1];，实测效果显著。

P4238 【模板】多项式求逆

查了半天才发现是NTT int valx = a[j+k], valy = 1ll*w*a[i+j+k]%MO; //Wn 写挂了……

对了，$cov[i]$不能提前预处理，因为$cov[]$和处理的长度有关系，必须要每次NTT之前处理才行。

3456: 城市规划

怎么连原根都不会求了：int Wn = qmi(3, MO-2);正确姿势：int Wn = qmi(3, (MO-1)/(i<<1)); 预处理cov[]：cov[i] = (cov[i>>1]>>1)|((i&1)*len>>1);　　(1<<(dt-1))=(len>>1)

codechef  Queries with GCD

枚举所有因数时候，下意识地for i=2 to sqrt(n+0.5)了。实际上$n=1times n$在分解处理gcd的时候也是非常重要的

2836: 魔法树

树剖dfs2，应是轻链链顶作为top

cf896C - Willem, Chtholly and Seniorious

qmi偷懒全用int，然而底数$a$可能是long long范围

iterator要在所处STL元素仍存在的前提下使用

cf1144G. Two Merged Sequences_Maker

1 freopen("cf1144g_zyh.out","r",stdin);
2 scanf("%s",rea1+1);
3 freopen("cf1144g.out","r",stdin);
4 scanf("%s",rea2+1);
5 if (rea1[0]!=rea2[0]) print(false);

字符串下标问题

HHHOJ#176. 栈

线段树再一次开成$maxn<<1$RE成20pts

lydsy十连测 可持久化字符串

kmp没学扎实系列

kmp的 while (a[len]!=a[d+1]&&d) d = fail[d]; 这句话复杂度的证明是关于势能分析的，所以一旦可持久化复杂度就会退化。

这种情况下，对于字符集小的情况，就记$c_{i,c}$表示$i$这个位置为字符$c$时所到达的位置，便能够保证复杂度。

bzoj5361: [Lydsy1805月赛]对称数

主席树update好几次都写成if (!rt) rt=++tot，这句话实际上只是在build的时候用，之后的update都是需要新开节点的。

大转盘

题意是构造长为$2^n$的循环01串，使任意$n$位的二进制数都出现。

有一种巧妙的构造是，把$n$位二进制看成边，连两个$n-1$位二进制，那么问题就变成了欧拉回路的构造。

然后这个欧拉回路是 有向图。不过求解的算法差不多。

#483. NOIP司马懿

暴力点分，然后匹配路径时候错了。

应该用 带点分中心的路径 去匹配 不带点分中心的路径 ，否则会漏掉以点分中心为起点的路径。

uoj#75. 【UR #6】智商锁

1.高斯消元求成主子式了，实际上应该消 余子式。

2.冲突重构的时候，高斯消元的 矩阵没有清空。

3262: 陌上花开

去重之后的 $n$ 和 $m$ 混用了。 

1176: [Balkan2007]Mokia

把询问拆成四个差分时候，居然没有++m，直接覆盖上一个差分了。

转载于:.html