细节挺多的扫码玩意 1.取模一定要分清何时取模，如果考场上调不出错可以把每个有取模的地方看一遍。 前车之鉴：[烦人的数学作业] 代码： 1234567891011ll dfs(ll x){ if(!x)return 0; ll res=0; int hi=gethi(x); int len=getlen(x); ll nxt=x-qpowwithoutmod(10,len-1)*hi; <===没错就是这里 for(int i=0;i<hi;++i) (res+=f[len-1][i])%=mod; (res+=(nxt+1)*hi%mod+dfs(nxt)%mod)%mod; return res;}

当面对一道题没有头绪时，以下是一些可能的突破点 1.正难则反，例如最优化满足性质P的元素转化为最劣化满足反性质P的元素 2.遇到区间查，可考虑转化为前缀之差。遇到区间修改，可考虑转化为差分修改 3.不强制在线可考虑离线调整操作顺序，反正也不劣 4.有些元素不具备顺序，不妨给这些元素排序一下(让它满足某种性质) 5.dp最优化的目标也可以作为状态维度 6.有时问题没有明确的性质，这种时候就要创造性质，具体的例子： 图论题两两最短路，没有明确的方向，于是将点划分为两个集合A,B，求A->B的最短路

细节多到爆炸 以NOI2009 诗人小G为例 1.队列1234567891011121314151617181920212223242526272829303132333435363738394041424344void update(int i){ int pos=n+1; while(!q.empty()){ node now=q.back();q.pop_back(); int l=now.l,r=now.r,j=now.j; if(f[i]+w(i,l)<=f[j]+w(j,l)){ pos=l; continue; } if(f[i]+w(i,r)>f[j]+w(j,r)){ q.push_back(now); break; } int mid; while(l+1<r){ mid=l+r>>1; if(f[i]+w(i,mid)<=f[j]+w(j,mid))r=mid; else l=mid; } if(f[i ...

题外话：学平衡树别学蓝书，操作很唐而且展开不多 1.删除时别忘记更新a[nxt].size,a[p].cnt; 123456789101112131415161718192021222324252627282930void remove(int val,int &p){ if(p==0) return ; --a[p].size; if(val==a[p].val){//检索到val //有多个 if(a[p].cnt>1){ --a[p].cnt; <----这里 return ; } //无左子树 if(a[p].l==0) p=a[p].r; //无右子树 else if(a[p].r==0) p=a[p].l; //子树均存在 else{ //求后继 int nxt=next(val,p); //删除nxt remove(a[nxt].val,a[p].r); //令nxt替代p a[nxt].l=a ...

1.bool dfs最后不要忘记return 12345678910111213141516bool dfs(int step){ if(step+gf()>m)return 0; if(gf()==0)return 1; int c[20]; memcpy(c,a,sizeof c); for(int len=1;len<n;++len){ for(int l=1;l+len-1<=n;++l){ for(int p=l+len;p<=n;++p){ move(l,l+len-1,p); if(dfs(step+1))return 1; memcpy(a,c,sizeof a); } } } return 0; <-----例如这里}

1.谨防手残 12345678910void build(int p,int l,int r,ll val[N],int rnk[N]){ ... if(l==r){ d[l].v=val[rnk[l]]; return; } ... } 是d[p].v而不是d[l].v

1.慎用INT_MAX和LONG_MAX 2.初始化，尤其注意结构体的初始化 3.dp出错先问自己几个问题： 表示不可能的值正确吗？(会对其他值产生影响吗？) 边界是啥？初值赋了吗？

bug处处有，OI特别多。从Zero开始的记错生活！ 普通莫队1.注意下标和值的区分例如123456void add(int x){ if(cnt[a[x]]++==0)++ans;}void del(int x){ if(--cnt[a[x]]==0)--ans;}注意不要将a[x]写成x，这样会导致错误。 带修莫队1.留意修改操作12345678910void del(int x){ if(--cnt[a[x]]==0)--ans;}void modify(int x,int l,int r){ if(mo[x].p>=l&&mo[x].p<=r){ if(cnt[mo[x].c]++==0)++ans; del(mo[x].p); } swap(a[mo[x].p],mo[x].c);} luogu P1903这一段不能直接用add 回滚莫队1.几处初始化暴力时有一次12345678910ll tmp ...

以前从来没有重点关注过不等式这一块，到最近才发现自己解不等式压轴题的方法太过于单一，于是便去查了资料，总结一下几类解法。其实说到不等式，在高中联系最紧密的就是最值，所以下面例子多以最值问题为主。 平均值不等式作为高中学习的第一个不等式，平均值不等式是最为基础的，也是最为简单的。 不等式如下： \sqrt{\frac{a^2+b^2}{2}} \geq \frac{a+b}{2} \geq \sqrt{ab} \geq \frac{2}{\frac{1}{a}+\frac{1}{b}}其中$a,b$为正实数，当且仅当$a=b$时等号成立。 常数代换法有时题目会给出一个条件，比如 $式子=t$，$t$ 为一常数，然后求另一式子的最值。比如下面这个例子： 例1：已知 $\frac{3}{a}+\frac{1}{b}=2$，求 $2a+b$ 的最小值。 遇到这种情况，通常会让所求乘上一个常数，再除以这个常数，这样就可以用平均值不等式解决。 比如例1，我们可以让 $2a+b$ 乘上 $2$，再除以 $2$，有 \begin{align} \frac{(2a+b)\cdot 2}{2} &= ...

将一棵树剖分成若干条链，使得树上的路径转化为链上的路径，从而将树上的问题转化为链上的问题，这就是树链剖分。而重链剖分是树链剖分的其中一种，其不同点在于剖分的方式。 重链剖分剖分方式重链剖分的剖分方式是：每次选择子树中最大的子树作为重儿子，其余的子树作为轻儿子。而重链是指一条从根节点到当前节点的路径上，出根节点外，链上其他节点都是重儿子的连边构成的链。如下图： 图中的红色边就是重链，而黑色边就是轻链。每个叶子节点也有一条以自己为起点，长度为 $0$ 的重链。 从图中还能看出，每个节点至多只能有一个重儿子。 重链剖分的几个重要数组$de[i]$：编号为 $i$ 节点的深度。 $fa[i]$：编号为 $i$ 节点的父节点。 $hs[i]$：编号为 $i$ 节点的重儿子。 $s[i]$：编号为 $i$ 节点的子树大小。 $dfn[i]$：编号为 $i$ 节点在重链优先遍历序列中的位置。重链优先遍历即先遍历重链，再遍历轻链的遍历方式。这样可以保证在重链上的节点在数组中是连续的，所以可以用线段树等数据结构维护。 $rnk[i]$：重链优先遍历序列中第 $i$ 个节点的编号。$dfn[i]$的下标 ...