7.25训练总结

考场错误：
A题其实并不简单，但是先想了一个方法后，就交了，wa了后一直卡住，策略不当，到最后后期写C的时候也犯了一些低级的错误，这点需要注意。
之后顺利的把BCDHI写完后，又完成了A的改正补充，最后又把G完成了，最终做出了7个题，但罚时最多，应该注意正确率

Gym - 100738E

启发式合并的模板题，其实看到25次的限制，就应该想到应该和log有关，结合最小生成树的Kruskal的算法，把边权排序一个一个做合并就可以了，注意每次选择sz小的往sz大的上面合并就好了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int n,m;
struct edge
{int x,y,z;
}e[maxn<<1];
int fa[maxn],bus[maxn];
vector <int> driver[maxn];
bool cmp(edge x,edge y)
{return x.z<y.z;
}
int find(int x)
{if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
vector <int> G[maxn];
int gs;
ll res;
void print(int u,int ff)
{for(int to:G[u]){if(to==ff) continue;print(to,u);if(driver[bus[to]].size()>driver[bus[u]].size())swap(bus[u],bus[to]);for(int v:driver[bus[to]]){driver[bus[u]].push_back(v);printf("Move %d %d %d\n",v,bus[to],bus[u]);}}if(ff) printf("Drive %d %d %d\n",bus[u],u,ff);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);for(int i=1;i<=n;i++) fa[i]=i,bus[i]=i,driver[i].push_back(i);sort(e+1,e+m+1,cmp);for(int i=1;i<=m;i++){int fx=find(e[i].x),fy=find(e[i].y);if(fx==fy) continue;fa[fx]=fy;res+=e[i].z;G[e[i].x].push_back(e[i].y);G[e[i].y].push_back(e[i].x);gs++; if(gs==n-1) break;}printf("%lld\n",res);for(int i=1;i<=n;i++) fa[i]=i;print(1,0);printf("Done\n");return 0;
}

Gym - 100738F

后缀数组的裸题，可以使用后缀数组后
然后把询问离线，按照长度依次处理，对于同一个长度，二分配合树状数组计算即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n;
char s[maxn];
int sa[maxn],rk[maxn],cnt[maxn],fz[maxn];
int oldrk[maxn],id[maxn];
bool cmp(int x,int y,int w)
{return oldrk[x]==oldrk[y] && oldrk[x+w]==oldrk[y+w];
}
void SA()
{int m=233;for(int i=0;i<=m;i++) cnt[i]=0;for(int i=1;i<=n;i++) cnt[rk[i]=s[i]]++;for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;int i,p;for(int w=1;;w<<=1,m=p){for(p=0,i=n;i>n-w;i--) id[++p]=i;for(i=1;i<=n;i++) if(sa[i]>w) id[++p]=sa[i]-w;for(i=0;i<=m;i++) cnt[i]=0;for(i=1;i<=n;i++) cnt[fz[i]=rk[id[i]]]++;for(i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(i=n;i>=1;i--) sa[cnt[fz[i]]--]=id[i];for(i=1;i<=n;i++) oldrk[i]=rk[i];for(p=0,i=1;i<=n;i++) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;if(p==n){for(i=1;i<=n;i++) sa[rk[i]]=i;break;}}
}
struct Query
{int id,l,k;
}q[maxn];
int Q;
bool ccmp(Query x,Query y)
{return x.l<y.l;
}
int c[maxn];
int lowbit(int x)
{return x&-x;
}
void add(int pos,int x)
{while(pos<=n){c[pos]+=x;pos+=lowbit(pos);}
}
int ask(int pos)
{int res=0;while(pos){res+=c[pos];pos-=lowbit(pos);}return res;
}
int res[maxn];
int main()
{scanf("%s",s+1);n=strlen(s+1);SA();scanf("%d",&Q);for(int i=1;i<=Q;i++){scanf("%d%d",&q[i].l,&q[i].k);q[i].id=i;} sort(q+1,q+Q+1,ccmp);int now=1;for(int i=1;i<=Q;i++){while(now<q[i].l){add(rk[n-now+1],1);now++;}int l=1,r=n,ans=0;while(l<=r){int mid=l+r>>1;if(mid-ask(mid)>=q[i].k) ans=mid,r=mid-1;else l=mid+1;}res[q[i].id]=sa[ans];}for(int i=1;i<=Q;i++) printf("%d\n",res[i]);return 0;
}