HNOI2021游记&省选复习做题记录
Verdandi
2021-03-18 19:09:51
HNOI2021联合省选，A卷。
太长不看：省选打崩，民间数据进队，官方数据直接整退役。。。
## 前言
由于本菜鸡在NOIP2020考出了$90+100+30+45=265$的分数（虽然比很多人成绩低了不知道多少），在HN有一个好看的名次，所以格外看重这次把NOIP作为$40\%$的联合省选，结果省选因为个人原因也没有太好看的分数，还是有一些遗憾的。。。
为什么省选不考字符串、数论和分块啊！！！
## 4月10日 Day 1
$404$机房，和同学都分开了，有一种不祥的预感。
带了一大袋零食去考试，在考前写了个manacher与广义SAM练手，手感挺好。
一遍输对密码，有了一个好的开始！
T1：诶，这道题怎么和我之前做的[一道题](https://www.luogu.com.cn/problem/CF436E)很像呀，要反悔贪心吗？
首先胡了一个找差值的贪心上去，然后样例都没过，原因是最大值可以变成最小值，所以构造了一组比较强的数据：
```
5 5
11 13 15 17 9
1 2 3 4 5
```
想了一下反悔贪心没有想到。
突然发现最终的答案一定会形成一个区间，而且区间长度最小，因此直接想到排序+尺取法，5min rush完了代码，再调了调细节，一遍过大样例。
```
#include<stdio.h>
#include<algorithm>
#define inf 1000000001
using namespace std;
const int maxn=1000005;
int n,m,ans;
int a[maxn],b[maxn],vis[maxn];
pair<int,int>c[maxn<<1];
inline int get(int x){
return x>n? x-n:x;
}
int main(){
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),c[i].first=a[i],c[i].second=i;
for(int i=1;i<=n;i++)
scanf("%d",&b[i]),c[n+i].first=b[i],c[n+i].second=n+i;
sort(c+1,c+1+2*n);
int l=1,r=0,cnta=0,cnt=0;
while(cnt<n||cnta<n-m){
r++;
if(c[r].second<=n)
cnta++;
if(vis[get(c[r].second)]==0)
cnt++;
vis[get(c[r].second)]++;
}
ans=c[r].first-c[l].first;
while(l<2*n&&r<=2*n){
if(c[l].second<=n)
cnta--;
vis[get(c[l].second)]--;
if(vis[get(c[l].second)]==0)
cnt--;
l++;
while(cnt<n||(r<=2*n&&cnta<n-m)){
r++;
if(c[r].second<=n)
cnta++;
if(vis[get(c[r].second)]==0)
cnt++;
vis[get(c[r].second)]++;
}
if(r>2*n)
break;
ans=min(ans,c[r].first-c[l].first);
}
printf("%d\n",ans);
return 0;
}
```
花30min写了个指数级暴力，然后还写了个拍子拍上了，然后去厕所（
拍了几千组数据出了问题，发现是数据生成器写错了，改了一下就继续拍下去了。（最后拍了一两万组$n=20$的数据）
T2：看了好久，感觉和做过的[另一道题](https://www.luogu.com.cn/problem/P3540)很像，然后发现并不可以这样做。
想了想差分之类能不能构造出一些特殊的地方，然后发现并不能。
然后想了一下高斯消元，发现是$O((nm)^3)$，想了想能不能带状高斯消元优化，发现并不会写带状高斯消元，然后就放弃了。
想了想差分约束，发现加法不好做差分约束，想到了直接给某些数带上负号，也就是直接黑白染色黑色为正白色为负，然后坐了坐感觉要把黑色和白色放在一起，又rush了好久发现不能构建一个含有$3$个未知量的不等式约束，然后就没想下去了。
考后补充：实际上可以直接把式子列出来，对一个整体进行差分约束，然后就做完了。
发现第一档部分分不会做，然后果断写第二档部分分。
第二档部分分想了好久，发现很简单：设第一行为$x$，那么之后每一行都可以表示出来，然后可以约束$x$取值范围，随便选一个数就好了。
第三档部分分想到了2-SAT：rush了一个2-SAT然后发现似乎不能约束某些$2\times2$的方格至少有$1$，然后就注释掉了。
考后juju说只需要建虚点就可以了。（我果然是图论废物）
```
#include<stdio.h>
#include<vector>
#define inf 10100000000
using namespace std;
const int maxn=305,maxt=maxn*maxn*2;
int T,n,m,e,ff,fff,ffff;
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
//int scc,all,top;
//int stk[maxt],vis[maxt],bel[maxt],p[4];
//vector<int>v[maxt],rv[maxt];
inline int getpos(int x,int y){
return (x-1)*m+y;
}
/*inline void add(int x,int y){
printf("ADD(%d,%d)\n",x,y);
v[x].push_back(y),rv[y].push_back(x);
}
void dfs(int x){
vis[x]=1;
for(int i=0;i<v[x].size();i++)
if(vis[v[x][i]]==0)
dfs(v[x][i]);
stk[++top]=x;
}
void rdfs(int x,int c){
vis[x]=1,bel[x]=c;
for(int i=0;i<rv[x].size();i++)
if(vis[rv[x][i]]==0)
rdfs(rv[x][i],c);
}*/
void dfs(int x,int y){
if(x==1){
if(y>n)
x++,y=1;
else{
for(int i=0;i<=b[x][y]&&(y==1||i<=b[x][y-1]);i++){
a[x][y]=i;
dfs(x,y+1);
if(ff)
return ;
}
}
}
if(y==1){
if(x>n){
int F=0;
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++){
a[i][j]=b[i-1][j-1]-a[i-1][j-1]-a[i][j-1]-a[i-1][j];
if(a[i][j]<0||a[i][j]>1000000){
F=1;
break;
}
}
if(F==0)
ff=1;
return ;
}
for(int i=0;i<=b[x][y]&&i<=b[x-1][y];i++){
a[x][y]=i;
dfs(x+1,y);
if(ff)
return ;
}
}
}
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d",&T);
while(T--){
int flg01=1,flag=0;
ff=fff=ffff=0;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
for(int j=1;j<m;j++){
scanf("%d",&b[i][j]);
flg01|=(b[i][j]==0||b[i][j]==1);
fff|=(b[i][j]==0);
ffff|=(b[i][j]==4000000);
}
if(fff){
puts("YES");
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("0%c",j==m? '\n':' ');
continue;
}
if(ffff){
puts("YES");
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("1000000%c",j==m? '\n':' ');
continue;
}
if(n==2){
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
c[i][j]=b[j][i];
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
b[i][j]=c[i][j];
swap(n,m),flag=1;
}
if(m==2){
int lst=0,minn=0,maxx=2000000;
for(int i=1;i<n;i++){
if(i&1){
minn=max(minn,b[i][1]-lst-2000000);
maxx=min(maxx,b[i][1]-lst);
lst=b[i][1]-lst;
// 0<=b[i][1]-lst-x<=2e6
}
else{
minn=max(minn,lst-b[i][1]);
maxx=min(maxx,lst-b[i][1]+2000000);
lst=b[i][1]-lst;
// 0<=b[i][1]-lst+x<=2e6
}
}
if(minn>maxx){
puts("NO");
continue;
}
lst=minn;
a[1][1]=lst/2,a[1][2]=lst-lst/2;
for(int i=1;i<n;i++){
lst=b[i][1]-lst;
a[i+1][1]=lst/2,a[i+1][2]=lst-lst/2;
}
}
else{
dfs(1,1);
if(ff==0){
puts("NO");
continue;
}
}
/* if(flg01){
int flg=0;
for(int i=1;i<n;i++)
for(int j=1;j<m;j++){
p[0]=getpos(i,j),p[1]=getpos(i+1,j);
p[2]=getpos(i,j+1),p[3]=getpos(i+1,j+1);
if(b[i][j]==0)
for(int k=0;k<=3;k++)
add(p[k]+n*m,p[k]);
else for(int k=0;k<=3;k++)
for(int c=0;c<=3;c++)
if(k!=c)
add(p[k]+n*m,p[c]);
}
all=2*n*m;
for(int i=1;i<=all;i++)
if(vis[i]==0)
dfs(i);
for(int i=1;i<=all;i++)
vis[i]=0;
for(int i=all;i>=1;i--)
if(vis[stk[i]]==0)
rdfs(stk[i],++scc);
for(int i=1;i<=n*m;i++)
if(bel[i]==bel[n*m+i]){
flg=1;
break;
}
if(flg){
puts("NO");
continue;
}
puts("YES");
for(int i=1;i<=n*m;i++)
printf("%d%c",(bel[i]<bel[n*m+i]),i%m==0? '\n':' ');
for(int i=1;i<=all;i++)
vis[i]=bel[i]=0,v[i].clear();
scc=e=top=0;
continue;
}*/
if(flag){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
c[j][i]=a[i][j];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
a[i][j]=c[i][j];
swap(n,m);
}
puts("YES");
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%d%c",a[i][j],j==m? '\n':' ');
}
return 0;
}
```
T3：考场上画了好久图，找了好久性质，硬生生一个性质都找不出来，发现自己图论能力过于单薄，吐了。
做T3的时候顺带把T1的拍子改成验证极限数据用时，发现几百组极限数据只有一组到了$0.9s$。
```
//I ball ball you.
#include<stdio.h>
const int maxn=1005,maxm=200005;
int n,m,e,stp;
int xx[maxm],yy[maxm],ans[maxm],start[maxn],to[maxm],then[maxm],vis[maxn],ban[maxn];
inline void add(int x,int y){
then[++e]=start[x],start[x]=e,to[e]=y;
}
int dfs(int x,int t,int stp){
if(ban[x]==1)
return 0;
if(x==t)
return 1;
vis[x]=stp;
for(int i=start[x];i;i=then[i]){
int y=to[i];
if(vis[y]!=stp&&dfs(y,t,stp))
return 1;
}
return 0;
}
int f(int x){
int res=0;
for(int i=1;i<=x;i++)
if(dfs(x,i,++stp)&&dfs(i,x,++stp))
res++,ban[i]=1;
for(int i=1;i<=n;i++)
ban[i]=0;
return res;
}
int calc(){
int res=0;
for(int i=1;i<=n;i++){
int now=f(i);
res+=now;
}
return res;
}
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&xx[i],&yy[i]);
ans[m]=n;
for(int i=m;i>=1;i--){
add(xx[i],yy[i]);
ans[i-1]=calc();
}
for(int i=0;i<=m;i++)
printf("%d%c",ans[i],i==m? '\n':' ');
return 0;
}
```
回家后打了一下板子：
[P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376)
[P3381 【模板】最小费用最大流](https://www.luogu.com.cn/problem/P3381)
[P5854 【模板】笛卡尔树](https://www.luogu.com.cn/problem/P5854)
[P4195 【模板】扩展BSGS](https://www.luogu.com.cn/problem/P4195)
[P2495 [SDOI2011]消耗战](https://www.luogu.com.cn/problem/P2495)
## 4月11日 Day 2
又带了一大袋零食去考场，一遍输对密码，针不戳。（这个时候珂怜的xzy没有发现这实际上是一个上午噩梦的开始）
T1：审了一下题，想了想能不能建自动机匹配，发现似乎做不到/dk，然后想了想倍增，没想到什么做法。
然后直接树分块！
在树上撒$\sqrt{n}$个关键点，每个点与其祖先里的关键点距离为$\sqrt{n}$，然后发现可以把询问的路径分成$4$个散块和$2$个整块，散块暴力跳（记得把$lca$到另一端的路径反向，我因为反向调了一个多小时），整块可以预处理第$i$个关键点跳到祖先关键点这一条链，从位置$j$开始匹配能匹配到哪里，不难发现（我想了十几分钟）可以用并查集维护所有位置同时进行匹配，同样还要反过来做一遍。
具体地，可以把整块对应的链上权值序列当成一个普通的序列，与长度为m的串进行匹配，然后对于每个位置可以维护它在匹配的过程中到了哪一个位置，不难发现把相同的位置在匹配的过程中会不断合并，那么直接上并查集就好了。
时间复杂度为：$O(n\sqrt{n}+m\sqrt{n}\alpha(n)+q\sqrt{n})$，常数极大，大样例要跑$4s$。
算了一下，林林总总花了$3$个多小时刚T1吧，结果最后的成绩还是那么丢人/ll。
正解就是我首先排除的倍增/ll。
```
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxc=50005,maxn=200005,maxm=maxn<<1,maxk=25,maxt=1005;
int n,m,c,e,Q,tot,S,qtot;
int p[maxc],w[maxn],start[maxn],to[maxm],then[maxm],dep[maxn],fore[maxn][maxk],ok[maxn],P[maxn],q[maxn],qq[maxn],keyfa[maxn],pos[maxn],res[maxt][maxc],f[maxc],size[maxc],nowans[maxc],flag[maxc],revres[maxt][maxc];
inline int cmp(int a,int b){
return dep[a]>dep[b];
}
inline void add(int x,int y){
then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x,int last){
fore[x][0]=last,dep[x]=dep[last]+1;
for(int i=1;i<=20;i++)
fore[x][i]=fore[fore[x][i-1]][i-1];
for(int i=start[x];i;i=then[i]){
int y=to[i];
if(y==last)
continue;
dfs(y,x);
}
}
int lca(int a,int b){
if(dep[a]<dep[b])
a+=b,b=a-b,a-=b;
for(int i=20;i>=0;i--)
if(dep[fore[a][i]]>=dep[b])
a=fore[a][i];
if(a==b)
return a;
for(int i=20;i>=0;i--)
if(fore[a][i]!=fore[b][i])
a=fore[a][i],b=fore[b][i];
return fore[a][0];
}
void solve(int x,int last,int key){
if(x!=1&&ok[x]){
keyfa[x]=key;
key=x;
}
for(int i=start[x];i;i=then[i]){
int y=to[i];
if(y==last)
continue;
solve(y,x,key);
}
}
int cnt1,cnt2,cnt3;
int tmp1[maxn],tmp2[maxn],tmp3[maxn];
int query(int x,int y,int id){
int z=lca(x,y);
if(1ll*(dep[x]+dep[y]-2*dep[z]+1)*Q<=400000000){
int RES=1;
for(int j=x;j!=z;j=fore[j][0])
if(RES<=c&&p[RES]==w[j]){
RES++;
if(RES>c)
return c;
}
qtot=0;
for(int j=y;j!=z;j=fore[j][0])
qq[++qtot]=j;
qq[++qtot]=z;
for(int j=qtot;j>=1;j--)
if(RES<=c&&p[RES]==w[qq[j]]){
RES++;
if(RES>c)
return c;
}
return RES-1;
}
int RES=1;
while(ok[x]==0&&x!=z){
if(RES<=c&&p[RES]==w[x]){
RES++;
if(RES>c)
return c;
}
if(id==1)
printf("BF_x_up %d res=%d\n",x,RES);
x=fore[x][0];
}
while(x>0&&dep[keyfa[x]]>=dep[z]){
if(id==1)
printf("sqrt_x %d res=%d\n",x,res[ok[x]][RES]);
if(RES<=c){
RES=res[ok[x]][RES];
if(RES>c)
return c;
}
x=keyfa[x];
}
while(x!=z){
if(RES<=c&&p[RES]==w[x]){
RES++;
if(RES>c)
return c;
}
if(id==1)
printf("BF_x_to_z %d res=%d\n",x,RES);
x=fore[x][0];
}
if(RES<=c&&p[RES]==w[z]){
RES++;
if(RES>c)
return c;
}
if(id==1)
printf("BF_z %d\n",z);
cnt1=cnt2=cnt3=0;
while(ok[y]==0&&y!=z)
tmp1[++cnt1]=y,y=fore[y][0];
while(y>0&&dep[keyfa[y]]>=dep[z])
tmp2[++cnt2]=y,y=keyfa[y];
while(y!=z)
tmp3[++cnt3]=y,y=fore[y][0];
for(int i=cnt3;i>=1;i--){
if(id==1)
printf("BF_z_to_y %d res=%d\n",tmp3[i],RES);
if(RES<=c&&p[RES]==w[tmp3[i]]){
RES++;
if(RES>c)
return c;
}
}
for(int i=cnt2;i>=1;i--){
if(id==1)
printf("sqrt_y %d res=%d\n",tmp2[i],revres[ok[tmp2[i]]][RES]);
if(RES<=c){
RES=revres[ok[tmp2[i]]][RES];
if(RES>c)
return c;
}
}
for(int i=cnt1;i>=1;i--){
if(id==1)
printf("BF_y_down %d res=%d\n",tmp1[i],RES);
if(RES<=c&&p[RES]==w[tmp1[i]]){
RES++;
if(RES>c)
return c;
}
}
return RES-1;
}
int find(int x){
return f[x]==x? x:f[x]=find(f[x]);
}
void merge(int a,int b){
a=find(a),b=find(b);
if(size[a]>size[b])
a+=b,b=a-b,a-=b;
f[a]=b,size[b]+=size[a];
}
int main(){
freopen("gem.in","r",stdin);
freopen("gem.out","w",stdout);
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=c;i++)
scanf("%d",&p[i]),pos[p[i]]=i;
for(int i=1;i<=n;i++)
scanf("%d",&w[i]),P[i]=i;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0),sort(P+1,P+1+n,cmp);
S=sqrt(n),ok[1]=++tot,q[tot]=1;
if(n>1000)
S=200;
for(int i=1;i<=n;i++){
int x=P[i],y=x,flg=ok[y];
while(dep[x]-dep[y]<S&&flg==0)
y=fore[y][0],flg|=(ok[y]);
if(flg==0)
ok[y]=++tot,q[tot]=y;
}
solve(1,0,1);
for(int i=1;i<=tot;i++){
int x=q[i];
for(int j=1;j<=c;j++)
f[j]=j,size[j]=1,nowans[j]=j,flag[j]=j;
qtot=0;
//nowans[startpos]=nowpos flag[nowpos]=find(all startpos)
for(int j=x;j!=keyfa[x];j=fore[j][0]){
qq[++qtot]=j;
int now=pos[w[j]],fnow=find(flag[now]);
if(fnow==0)
continue;
flag[nowans[fnow]]=0;
nowans[fnow]++;
if(nowans[fnow]>c)
continue;
int r=flag[nowans[fnow]];
if(r==0)
flag[nowans[fnow]]=fnow;
else merge(fnow,r),flag[nowans[fnow]]=fnow;
}
for(int j=1;j<=c;j++){
res[i][j]=nowans[find(j)];
// printf("res[%d][%d]=%d\n",i,j,res[i][j]);
}
for(int j=1;j<=c;j++)
f[j]=j,size[j]=1,nowans[j]=j,flag[j]=j;
for(int k=qtot;k>=1;k--){
int j=qq[k],now=pos[w[j]],fnow=find(flag[now]);
if(fnow==0)
continue;
flag[nowans[fnow]]=0;
nowans[fnow]++;
if(nowans[fnow]>c)
continue;
int r=flag[nowans[fnow]];
if(r==0)
flag[nowans[fnow]]=fnow;
else merge(fnow,r),flag[nowans[fnow]]=fnow;
}
for(int j=1;j<=c;j++){
revres[i][j]=nowans[find(j)];
// printf("revres[%d][%d]=%d\n",i,j,revres[i][j]);
}
}
scanf("%d",&Q);
for(int i=1;i<=Q;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",query(x,y,0));
}
return 0;
}
```
T2：由于在全力刚T1，因此T2只写了个爆搜，最后竟然还写挂了$15pts$，丢人。
```
#include<stdio.h>
const int maxn=15;
int n,m,fir;
int a[maxn],used[maxn],p[maxn];
long long ans;
inline int max(int a,int b){
return a>b? a:b;
}
void dfs(int x,int rk1,int sum,int val,int add){
if(sum>m)
return ;
if(x>n){
ans++;
return ;
}
for(int i=1;i<=n;i++)
if(used[i]==0){
used[i]=1,p[x]=i;
int v=val+(i>rk1),ad=max(add,v-a[i]);
dfs(x+1,i,sum+ad,v,ad);
used[i]=0;
}
}
int main(){
freopen("ranklist.in","r",stdin);
freopen("ranklist.out","w",stdout);
scanf("%d%d",&n,&m);
a[0]=-1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>a[fir])
fir=i;
}
dfs(1,fir,0,a[fir],0);
printf("%lld\n",ans);
return 0;
}
```
T3：写了个$O(qn^2)$的丢人暴力走人/kk。
实际上可以直接上$\text{bitset}$优化做到更优复杂度的，但是刚T1去了，就没加上去。
```
#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=3005,maxm=maxn<<1,maxk=25;
int n,m,q,e,stp;
int start[maxn],to[maxm],then[maxm],fa[maxn],size[maxn],dep[maxn],g[maxn][maxn],vis[maxn],flg[maxn],fore[maxn][maxk];
inline void add(int x,int y){
then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x){
size[x]=1,fore[x][0]=fa[x];
for(int i=1;i<=20;i++)
fore[x][i]=fore[fore[x][i-1]][i-1];
for(int i=start[x];i;i=then[i]){
int y=to[i];
fa[y]=x,dep[y]=dep[x]+1;
dfs(y),size[x]+=size[y];
}
}
int lca(int a,int b){
if(dep[a]<dep[b])
swap(a,b);
for(int i=20;i>=0;i--)
if(dep[fore[a][i]]>=dep[b])
a=fore[a][i];
if(a==b)
return a;
for(int i=20;i>=0;i--)
if(fore[a][i]!=fore[b][i])
a=fore[a][i],b=fore[b][i];
return fore[a][0];
}
void get(int x,int B){
if(x==B)
return ;
vis[x]=stp;
for(int i=start[x];i;i=then[i]){
int y=to[i];
if(vis[y]==stp)
continue;
get(y,B);
}
}
int main(){
freopen("dominator.in","r",stdin);
freopen("dominator.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
if(m==n-1)
dfs(1);
for(int i=1;i<=n;i++){
stp++,get(1,i);
for(int j=1;j<=n;j++)
g[i][j]|=(vis[j]!=stp);
}
for(int i=1;i<=q;i++){
int x,y;
scanf("%d%d",&x,&y);
if(m==n-1){
if(lca(x,y)!=fa[y])
printf("%d\n",size[x]);
else puts("0");
continue;
}
int res=0;
add(x,y);
for(int j=1;j<=n;j++){
stp++,get(1,j);
for(int k=1;k<=n;k++)
flg[k]|=((vis[k]!=stp)^g[j][k]);
}
for(int j=1;j<=n;j++)
res+=flg[j],flg[j]=0;
start[x]=then[e],e--;
printf("%d\n",res);
}
return 0;
}
```
测了一下民间数据，只有$100+30+20+80+45+30=305$，fst了60分，远低于人均水平/ll
orz民间数据吊打我的juju。
总结一下，还是考试的时候很多思路没有完全成型，或者被hack掉就直接开始写了，因此浪费了大量时间，也导致拿部分分的时间不够。
同样还因为我的思维还不够强，因此很多部分分都没有较成熟的思路，也因此fst。
最后这个难看的分数也或多或少和我最后几天的颓废没有良好的状态有关系吧。
「随风凋零的，是某人从未打算实现的空想，还是落入海面继续下沉的烟花」
不管怎么样，我们都有光明的未来！
upd：退役的一点颜面都没有，艹。
树分块被卡成暴力分，各种各样的错误一并犯了，分数达到了估分下限/ll。
退役的好不甘心啊。。。
---
附赠负数天数的做题记录：
## 3月17日 Day -23
做了一道有意思的交互题[CF1364E X-OR](https://www.luogu.com.cn/problem/CF1364E)。
复习[树剖](https://www.luogu.com.cn/problem/P3384)。人老了，以前15分钟的树剖已经要30分钟了。
把弦图mcs算法板子打了一遍过了两道板题：[P3196 [HNOI2008]神奇的国度](https://www.luogu.com.cn/problem/P3196),[P3852 [TJOI2007]小朋友](https://www.luogu.com.cn/problem/P3852)
在u群问了noi2020翻修道路的中文题解，然后看不懂。
[CF891C Envy](https://www.luogu.com.cn/problem/CF891C)：有意思的$\text{MST}$题
## 3月18日 Day -22
中午划水的时候写了一个树上简单博弈[P5801 [SEERC2019]Game on a Tree](https://www.luogu.com.cn/problem/P5801)
复习树剖写了一道板题[P4312 [COI2009] OTOCI](https://www.luogu.com.cn/problem/P4312)，调了好久，然后就卡到最优解第一名了。
复习fhq-treap。虽然忘光了，打一遍就想起来了：[P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369),[P6136 【模板】普通平衡树（数据加强版）](https://www.luogu.com.cn/problem/P6136)，然后做非模板题一道都做不出来。。。
## 3月19日 Day -21
[UVA1711 Catering](https://www.luogu.com.cn/problem/UVA1711)：上下界网络流水题
下午lk讲了博弈论，竟然自己做出一道题，《震惊！初三废物xzy竟然会做博弈论》[AT3727 [ARC087C] Prefix-free Game](https://www.luogu.com.cn/problem/AT3727)。
[CF142B Help General](https://www.luogu.com.cn/problem/CF142B)：打"General"
[P6560 [SBCOI2020] 时光的流逝](https://www.luogu.com.cn/problem/P6560)：博弈
[P7419 「PMOI-2」参天大树](https://www.luogu.com.cn/problem/P7419)：dp分类讨论题，有点意思
## 3月20日 Day -20
[P4466 [国家集训队]和与积](https://www.luogu.com.cn/problem/P4466)：做一道莫反来保持手感
$$\sum_{i=1}^n\sum_{j=1}^{i-1}[\gcd(i,j)=1]\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor}[i+j\mid d]$$
$$=\sum_{i=1}^{\sqrt{n}}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{i}\rfloor}{i+j}\rfloor\sum_{k\mid\gcd(i,j)}\mu(k)$$
$$=\sum_{k=1}^{\sqrt{n}}\mu(k)\sum_{i=1}^{\lfloor\frac{\sqrt{n}}{k}\rfloor}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{ik}\rfloor}{ik+jk}\rfloor$$
$$=\sum_{k=1}^{\sqrt{n}}\mu(k)\sum_{i=1}^{\lfloor\frac{\sqrt{n}}{k}\rfloor}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{ik^2}\rfloor}{i+j}\rfloor$$
可以$O(\sqrt{n}\log n)$枚举$k,i$，然后整除分块枚举$j$统计答案。
复杂度不会证。
## 3月21日 Day -19
[P5544 [JSOI2016]炸弹攻击1](https://www.luogu.com.cn/problem/P5544)：模拟退火，这么套路的题一点意思都没有
[P4212 外太空旅行](https://www.luogu.com.cn/problem/P4212)：随机化求最大团的无趣题
[P5239 回忆京都](https://www.luogu.com.cn/problem/P5239)：水题
[P4930 [PA2013]Euler](https://www.luogu.com.cn/problem/P4930)，欧拉函数+搜索，[Solution](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-p4930)！
## 3月22日 Day -18
日报挂上去了，但是@上了我的小号，非常尬。
[P4424 [HNOI/AHOI2018]寻宝游戏](https://www.luogu.com.cn/problem/P4424)：myy毒瘤题，蛮好玩的
## 3月23日 Day -17
[P5292 [HNOI2019]校园旅行](https://www.luogu.com.cn/problem/P5292)：myy毒瘤题Ⅱ，也是好玩的题目
[P3344 [ZJOI2015]幻想乡 Wi-Fi 搭建计划](https://www.luogu.com.cn/problem/P3344)：有点套路的结论题
日报改过来了耶！
> 达成成就：2天内大号小号均上洛谷日报
## 3月24日 Day -16
[CF1188D Make Equal](https://www.luogu.com.cn/problem/CF1188D)：有意思的思维题，好毒呀
[AT2374 [AGC014B] Unplanned Queries](https://www.luogu.com.cn/problem/AT2374)：简单结论题
[AT2363 [AGC012C] Tautonym Puzzle](https://www.luogu.com.cn/problem/AT2363)：有意思的构造题
[P7446 [Ynoi2007] rfplca](https://www.luogu.com.cn/problem/P7446)：lxl的毒瘤分块，写了好久，然后发现题解复杂度假了，调题目调到不想写博客了
终于绑定了SPOJ了，感谢NSObject的帮助！然后交了两道题：[SP106 BINSTIRL - Binary Stirling Numbers](https://www.luogu.com.cn/problem/SP106),[SP3734 PERIODNI - Periodni](https://www.luogu.com.cn/problem/SP3734)
## 3月25日&3月26日 Day -15&-14
第一次月考，划了两天水。
## 3月27日 Day -13
[SP20173 DIVCNT2 - Counting Divisors (square)](https://www.luogu.com.cn/problem/SP20173)：老毒瘤题了，硬生生卡了好久空间。。。
写一下推柿子过程吧：
$$
\sum_{i=1}^n d(i^2)=\sum_{i=1}^n\prod_{j=1}^{s_i}(2k_{i,j}+1)\ \ \ \ \ \ \ \ \ \ (i=\prod_{j=1}^{s_i}p_{i,j}^{k_{i,j}})
$$
$$
=\sum_{i=1}^n\sum_{S\in\{i\mid1\leqslant i\leqslant k\}}2^{|S|}\prod_{j\in S}k_{i,j}
$$
$$
=\sum_{i=1}^n\sum_{j\mid i}\mu^2(j)=\sum_{i=1}^n(\sigma\cdot \mu^2)(i)
$$
然后可以用类似杜教筛的方法筛出$\sigma$和$\mu^2$的前$10^8$项，然后写个整除分块，整除分块里求$\sigma$和$\mu^2$就用打出的表和$O(\sqrt{n})$算法结合就好了。
$$
\sum_{i=1}^n\sigma(i)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor
$$
$$
\sum_{i=1}^n\mu^2(i)=\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac{n}{i^2}\rfloor
$$
复杂度是$O(n^{\frac{2}{3}})$
[CF568E Longest Increasing Subsequence](https://www.luogu.com.cn/problem/CF568E)：复杂dp题，有点套路呀
[SP7001 VLATTICE - Visible Lattice Points](https://www.luogu.com.cn/problem/SP7001)：反演裸题
[P6860 象棋与马](https://www.luogu.com.cn/problem/P6860)：有意思的杜教筛
[P6810 「MCOI-02」Convex Hull 凸包](https://www.luogu.com.cn/problem/P6810)：反演裸题
[CF1491F Magnets](https://www.luogu.com.cn/problem/CF1491F)：有一点点意思的交互题
## 3月28日 Day -12
[P5307 [COCI2019] Mobitel](https://www.luogu.com.cn/problem/P5307)：改变枚举状态的经典题+整除分块
[P3579 [POI2014]PAN-Solar Panels](https://www.luogu.com.cn/problem/P3579)：整除分块水题
[CF354C Vasya and Beautiful Arrays](https://www.luogu.com.cn/problem/CF354C)：直接暴力，发现暴力的复杂度为调和级数
[P2135 方块消除](https://www.luogu.com.cn/problem/P2135)=[UVA10559 方块消除 Blocks](https://www.luogu.com.cn/problem/UVA10559)：区间dp套路题（由于状态里有一些改变，所以也可以划分到费用提前里就很离谱）
复习了一下费用提前，然后要写的例题一直咕咕咕。
[UVA11134 传说中的车 Fabled Rooks](https://www.luogu.com.cn/problem/UVA11134)：经典贪心题，直接行列分开
[CF616E Sum of Remainders](https://www.luogu.com.cn/problem/CF616E)：整除分块细节题
[CF963B Destruction of a Tree](https://www.luogu.com.cn/problem/CF963B)：有意思的构造题
[CF276D Little Girl and Maximum XOR](https://www.luogu.com.cn/problem/CF276D)：XOR性质题，直接贪心
[P3496 [POI2010]GIL-Guilds](https://www.luogu.com.cn/problem/P3496)：水题
[CF475D CGCDSSQ](https://www.luogu.com.cn/problem/CF475D)：利用了$\gcd$的性质的普通题
[P4184 [USACO18JAN]Sprinklers P](https://www.luogu.com.cn/problem/P4184)：基础dp优化，[Solution](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-p4184)
## 3月29日 Day -11
再次尝试调试[SP1526 RSORTING - Ranklist Sorting](https://www.luogu.com.cn/problem/SP1526)，没有调出来
[P7451 [THUSCH2017] 杜老师](https://www.luogu.com.cn/problem/P7451)：dls/se，线性基套路题+结论题，[Solution](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-p7451)
划了一天水诶。。。
## 3月30日 Day -10
[AT5697 [AGC041F] Histogram Rooks](https://www.luogu.com.cn/problem/AT5697)：笛卡尔树上背包dp+容斥套容斥的大毒瘤题，[Solution](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-at5697)
## 3月31日 Day -9
[P5556 圣剑护符](https://www.luogu.com.cn/problem/P5556)：一个线性基结论题
[P5438 【XR-2】记忆](https://www.luogu.com.cn/problem/P5438)：神仙推柿子题，不会分析复杂度
[P6162 [Cnoi2020]四角链](https://www.luogu.com.cn/problem/P6162)：熬夜把这道题做完了，是一个基础的第二类斯特林数组合意义题
## 4月1日 Day -8
初三弱鸡终于开始停课了！感动！
[P2495 [SDOI2011]消耗战](https://www.luogu.com.cn/problem/P2495)：复习了虚树板子题
[P5680 [GZOI2017]共享单车](https://www.luogu.com.cn/problem/P5680)：虚树基础题，感觉两个算法硬生生拼凑在一起特别没有美感
[CF1320E Treeland and Viruses](https://www.luogu.com.cn/problem/CF1320E)：虚树上dp
[CF571A Lengthening Sticks](https://www.luogu.com.cn/problem/CF571A)：小学奥数题
[P6298 齿轮](https://www.luogu.com.cn/problem/P6298)：基础容斥
hh讲了ds，然后越讲越偏，越讲越偏。。。
[P6965 [NEERC2016]Binary Code](https://www.luogu.com.cn/problem/P6965)：trie树优化建图细节sb题，调不出来
## 4月2日 Day -7
[CF424C Magic Formulas](https://www.luogu.com.cn/problem/CF424C)：改变顺序，然后直接暴力
[P3293 [SCOI2016]美味](https://www.luogu.com.cn/problem/P3293)：01trie板子题调了亿个小时
[P4592 [TJOI2018]异或](https://www.luogu.com.cn/problem/P4592)：套路题，直接类似主席树一样差分
[P6018 [Ynoi2010] Fusion tree](https://www.luogu.com.cn/problem/P6018)：Ynoi/se，其实就是01trie交换子树的小trick
[P6031 CF1278F Cards 加强版](https://www.luogu.com.cn/problem/P6031)：推柿子sb题，只觉得非常精神污染，[Solution](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-p6031)，顺便水了个弱化版[CF1278F Cards](https://www.luogu.com.cn/problem/CF1278F)
[P2480 [SDOI2010]古代猪文](https://www.luogu.com.cn/problem/P2480)：同余类数学综合题，复习了一下一些数学
## 4月3日 Day -6
[P5298 [PKUWC2018]Minimax](https://www.luogu.com.cn/problem/P5298)：线段树合并优化dp，利用线段树合并的性质
[P5327 [ZJOI2019]语言](https://www.luogu.com.cn/problem/P5327)：ZJOI神仙题/se，利用一个结论然后直接上线段树合并
[P6773 [NOI2020] 命运](https://www.luogu.com.cn/problem/P6773)：打同步赛的时候没写/kk，其实是一道线段树合并优化dp好题，[Solution](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-p6773)
[P5903 【模板】树上 k 级祖先](https://www.luogu.com.cn/problem/P5903)：长剖板子
[CF1009F Dominant Indices](https://www.luogu.com.cn/problem/CF1009F)：dsu on tree板子
[CF715C Digit Tree](https://www.luogu.com.cn/problem/CF715C)：dsu on tree有意思的题，[Solution](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-cf715c)
[P5904 [POI2014]HOT-Hotels 加强版](https://www.luogu.com.cn/problem/P5904)：长剖优化dp
## 4月4日 Day -5
[P5113 Sabbat of the witch](https://www.luogu.com.cn/problem/P5113)：屑分块题，快爬，调不出来
猛的发现博弈论还没复习，赶紧搞一下博弈论。
[AT3939 [ARC091D] Strange Nim](https://www.luogu.com.cn/problem/AT3939)：博弈论+根号分治好题
[CF1147C Thanos Nim](https://www.luogu.com.cn/problem/CF1147C)：有点意思的猜不变量博弈论
[CF15C Industrial Nim](https://www.luogu.com.cn/problem/CF15C)：博弈论+结论题
$$
\oplus_{i=0}^{i-1}=\begin{cases}x&x\equiv 0\pmod 4\\1&x\equiv1\pmod4\\x+1&x\equiv2\pmod4\\0&x\equiv3\pmod 4\end{cases}
$$
[P4643 [国家集训队]阿狸和桃子的游戏](https://www.luogu.com.cn/problem/P4643)：有意思的思维题，把边权转化为点权
[CF36D New Game with a Chess Piece](https://www.luogu.com.cn/problem/CF36D)：分类讨论博弈论（双倍经验[SP7602 CF36D - New Game with a Chess Piece](https://www.luogu.com.cn/problem/SP7602)）
打[愚人节比赛](https://www.luogu.com.cn/contest/42371)！
[T171038 温故而知新](https://www.luogu.com.cn/problem/T171038?contestId=42371)：不会有人不会百度bv转av吧，不会吧？不会吧？
[T173329 A+B Problem](https://www.luogu.com.cn/problem/T173329?contestId=42371)：看到A+B，直接粘[P1601 A+B Problem（高精）](https://www.luogu.com.cn/problem/P1601)的代码，直觉发现不要换行
[T173878 买书送团队](https://www.luogu.com.cn/problem/T173878?contestId=42371)：做了好久的狗屎题，一开始直接上直线解析式，最后问了ykw才发现这是分段函数
[T173049 驹草盛开的万年积雪](https://www.luogu.com.cn/problem/T173049?contestId=42371)：首先让hzr听出几个地方，然后直接调整一下就过了，据hzr说在这之后就单曲循环这首歌停不下来了（
[T173046 风神的神德](https://www.luogu.com.cn/problem/T173046)：首先把图片down下来，然后改成zip，然后再瞎搞一下就发现了[T124363 风神的神德](https://www.luogu.com.cn/problem/T124363)，然后由于私人题目可以看到错误信息，所以可以试出答案，再看回来，发现两题空间限制不同，一个32M一个16M，由于洛谷设置空间会直接四舍五入，所以可以猜测输出31.25%（考场没想到）
[UVA1482 Playing With Stones](https://www.luogu.com.cn/problem/UVA1482)：结论题
[P2575 高手过招](https://www.luogu.com.cn/problem/P2575)：阶梯博弈
[P3480 [POI2009]KAM-Pebbles](https://www.luogu.com.cn/problem/P3480)：阶梯博弈
[P4279 [SHOI2008]小约翰的游戏](https://www.luogu.com.cn/problem/P4279)：Anti-SG，直接上结论（双倍经验：[UVA1566 John](https://www.luogu.com.cn/problem/UVA1566)）
[AT2307 [AGC010F] Tree Game](https://www.luogu.com.cn/problem/AT2307)：就是个树上dp，似乎以前做过？
[CF1221E Game With String](https://www.luogu.com.cn/problem/CF1221E)：分类讨论好题
[CF388C Fox and Card Game](https://www.luogu.com.cn/problem/CF388C)：基础博弈论
## 4月5日 Day -4
[P5305 [GXOI/GZOI2019]旧词](https://www.luogu.com.cn/problem/P5305)：好玩的树剖，其实就是[P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211)的加强版
[P6374 「StOI-1」树上询问](https://www.luogu.com.cn/problem/P6374)：LCA简单题
[CF1498E Two Houses](https://www.luogu.com.cn/problem/CF1498E)：竞赛图水题
[SP9507 MARIO2 - Mario and Mushrooms](https://www.luogu.com.cn/problem/SP9507)：Raney引理板子题，[Solution](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-sp9507)
[CF1498A GCD Sum](https://www.luogu.com.cn/problem/CF1498A)：简单题
[CF1498F Christmas Game](https://www.luogu.com.cn/problem/CF1498F)：有意思的阶梯博弈+换根dp
[P1495 【模板】中国剩余定理(CRT)/曹冲养猪](https://www.luogu.com.cn/problem/P1495)：CRT板子题
[P4720 【模板】扩展卢卡斯](https://www.luogu.com.cn/problem/P4720)：exLucas板子题，调了好久
[P3846 [TJOI2007] 可爱的质数/【模板】BSGS](https://www.luogu.com.cn/problem/P3846)：BSGS板子题
[P4884 多少个1？](https://www.luogu.com.cn/problem/P4884)：BSGS+简单转换
[P2183 [国家集训队]礼物](https://www.luogu.com.cn/problem/P2183)：exLucas板子题
[P4861 按钮](https://www.luogu.com.cn/problem/P4861)：BSGS板子题
打[月赛](https://www.luogu.com.cn/contest/42732)！
[P7478 StickSuger](https://www.luogu.com.cn/problem/P7478?contestId=42732)：不会有人不会做T1吧？不会吧？不会吧？直接贪就对了！
[P7479 至曾是英雄的您](https://www.luogu.com.cn/problem/P7479?contestId=42732)：真的有绿题的必要吗？直接搜每个空位置的连通块就好了。
[P7480 Reboot from Blue](https://www.luogu.com.cn/problem/P7480?contestId=42732)：难度骤增，不会做，爬了。。。
首先想到一个dp思路，但是不难发现还可以倒着走一段距离加油然后再去终点。
然后考虑了这一点之后又发现可以反复横跳，但是不难发现转移是从油价高到油价低的，因此直接$O(n^2)$dp。（这是考场思路）
看到绝对值不会优化了，其实很简单，只需要用$\text{set}$存下dp值直接转移就好了。
[P7481 梦现时刻](https://www.luogu.com.cn/problem/P7481?contestId=42732)：不想做的狗屎题，考场思路：固定$a$，发现给$F(a,b)$每一项配上$x^i$次方的式子可以通过卷积得到：$(\sum_k\frac{x^k}{k!})(\sum_{k}\frac{(n-a)^{\underline i}x^k}{k})$，然后直接上NTT。
没有去改。
[CF906D Power Tower](https://www.luogu.com.cn/problem/CF906D)：欧拉定理水题
[P4454 [CQOI2018]破解D-H协议](https://www.luogu.com.cn/problem/P4454)：BSGS板子题
[P4195 【模板】扩展BSGS](https://www.luogu.com.cn/problem/P4195)：exBSGS板子题（双倍经验[SP3105 MOD - Power Modulo Inverted](https://www.luogu.com.cn/problem/SP3105)）
## 4月6日 Day -3
[P3726 [AH2017/HNOI2017]抛硬币](https://www.luogu.com.cn/problem/P3726)：有意思的组合数学，调不出来
[CF1117E Decypher the String](https://www.luogu.com.cn/problem/CF1117E)：好玩的题！！！我喜欢字符串+分块的神仙题！！！/se/se/se
[CF900D Unusual Sequences](https://www.luogu.com.cn/problem/CF900D)：容斥水题
[P7325 [WC2021] 斐波那契](https://www.luogu.com.cn/problem/P7325)：终于想起来改今年WC的题了（WC2021：伤心掉分场，挂的分数=拿的分数就很离谱）
[CF679E Bear and Bad Powers of 42](https://www.luogu.com.cn/problem/CF679E)：有意思的线段树，调了挺久
[P4198 楼房重建](https://www.luogu.com.cn/problem/P4198)：$\log$的$\text{pushup}$的线段树，有意思
[P5535 【XR-3】小道消息](https://www.luogu.com.cn/problem/P5535)：如果不知道前置知识说不定也能猜到结论，但是证不出来
## 4月7日 Day -2
[P4254 [JSOI2008]Blue Mary开公司](https://www.luogu.com.cn/problem/P4254)：李超线段树裸题，调了亿年（新增遇到$\text{double}$就挂的特性）
[P4097 [HEOI2013]Segment](https://www.luogu.com.cn/problem/P4097)：李超线段树裸题，调了亿年
[CF932F Escape Through Leaf](https://www.luogu.com.cn/problem/CF932F)：李超线段树合并优化dp，好题！！！
[CF589H Tourist Guide](https://www.luogu.com.cn/problem/CF589H)：简单结论题，就是交不上去
[CF875C National Property](https://www.luogu.com.cn/problem/CF875C)：2-SAT套路题
[P3810 【模板】三维偏序（陌上花开）](https://www.luogu.com.cn/problem/P3810)：cdq板子
[P3157 [CQOI2011]动态逆序对](https://www.luogu.com.cn/problem/P3157)：cdq板子
[CF584D Dima and Lisa](https://www.luogu.com.cn/problem/CF584D)：水题
[CF527E Data Center Drama](https://www.luogu.com.cn/problem/CF527E)：卡常欧拉回路，没调出来
[P3375 【模板】KMP字符串匹配](https://www.luogu.com.cn/problem/P3375)：KMP板子
[P4696 [CEOI2011]Matching](https://www.luogu.com.cn/problem/P4696)：KMP好题！！！理解KMP的本质
[P4427 [BJOI2018]求和](https://www.luogu.com.cn/problem/P4427)：大水题，18年BJ出这种水题干什么
slay回来了，所以打了好久slay。
## 4月8日 Day -1
[CF1200E Compress Words](https://www.luogu.com.cn/problem/CF1200E)：KMP简单应用
[P5410 【模板】扩展 KMP（Z 函数）](https://www.luogu.com.cn/problem/P5410)：Z函数板子
[AT2040 [ARC060D] 最良表現 / Best Representation](https://www.luogu.com.cn/problem/AT2040)：结论题+KMP判循环串
[P5357 【模板】AC自动机（二次加强版）](https://www.luogu.com.cn/problem/P5357)：AC机板子
[CF710F String Set Queries](https://www.luogu.com.cn/problem/CF710F)：二进制拆分优化AC机
[CF590E Birthday](https://www.luogu.com.cn/problem/CF590E)：类似[P4298 [CTSC2008]祭祀](https://www.luogu.com.cn/problem/P4298)，就是建出AC机之后搞最长反链。
又打了好久slay。
## 4月9日 Day 0
[P3804 【模板】后缀自动机 (SAM)](https://www.luogu.com.cn/problem/P3804)：SAM板子
[P2178 [NOI2015] 品酒大会](https://www.luogu.com.cn/problem/P2178)：SAM简单应用，调了好久
[P3389 【模板】高斯消元法](https://www.luogu.com.cn/problem/P3389)：高斯消元板子（~~搞死小圆~~）
[P2973 [USACO10HOL]Driving Out the Piggies G](https://www.luogu.com.cn/problem/P2973)：高斯消元裸题
[CF24D Broken robot](https://www.luogu.com.cn/problem/CF24D)：带状高消
[CF585F Digits of Number Pi](https://www.luogu.com.cn/problem/CF585F)：SAM上数位dp的好题
[P6139 【模板】广义后缀自动机（广义 SAM）](https://www.luogu.com.cn/problem/P6139)：广义SAM
[P4081 [USACO17DEC]Standing Out from the Herd P](https://www.luogu.com.cn/problem/P4081)：广义SAM简单应用