ZR 集训 Day1 - 基础数据结构及其应用 AT_abc380_e [ABC380E] 1D Bucket Tool 使用并查集表示一个连通块，分别用 col_i,st_i,ed_i 表示连通块 i 的颜色、左端点和右端点。 进行修改操作时，要向当前连通块的左右两边看看能否合并。 代码： C++ #include using namespace std; const int N=5e5+5; int n,q; int fa[N],col[N],siz[N],st[N],ed[N]; int find(int x){ if(x==fa[x]) return x; else return fa[x]=find(fa[x]); } int main(){ cin>>n>>q; for(int i=1;i>op>>x; if(op==1){ cin>>c; x=find(x); siz[col[x]]-=ed[x]-st[x]+1; siz[c]+=ed[x]-st[x]+1; col[x]=c; if(st[x]>1){ int l=find(st[x]-1); if(c==col[l]){ fa[l]=x; st[x]=st[l]; } } if(ed[x] `#include using namespace std; #define int long long const int N=1e5+5; int n,m,q; int p[N],inv[N],st[N][70]; int solve(int x){//x表示 int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1)); for(int i=62;i>=0;i--) if(cnt>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli); if(!cnt) return t; t=m,cnt--; for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli); return t; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m>>q; for(int i=1;im;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i]; fill(st[m],st[m]+63,m); for(int k=1;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1]; while(q--){ int t; cin>>t; coutsolve(n-t+1)"\n"; } return 0; }` P1197 [JSOI2008] 星球大战 并查集是不支持删除的，但这道题需要我们对并查集进行删除操作。 不难想到，我们离线并倒着进行处理，这时，删除操作就变成了加边，这题就可做了。 坑点：点从 0 开始计数。 代码： C++ #include using namespace std; const int N=5e5+5; int n,m,k,sum; int fa[N],a[N],b[N],ans[N]; vector g[N]; int find(int x){ if(x==fa[x]) return x; else return fa[x]=find(fa[x]); } int main(){ cin>>n>>m; for(int i=1;i>x>>y; x++,y++; g[x].push_back(y); g[y].push_back(x); } cin>>k; for(int i=1;i>b[i]; b[i]++; a[b[i]]=1; } for(int i=1;i0;i--){ ans[i]=sum; int u=b[i]; a[u]=0; sum++; for(int v:g[u]){ if(a[v]) continue; int x=find(v),y=find(u); if(x==y) continue; fa[x]=y,sum--; } } ans[0]=sum; for(int i=0;i `#include using namespace std; #define int long long const int N=1e5+5; int n,m,q; int p[N],inv[N],st[N][70]; int solve(int x){//x表示 int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1)); for(int i=62;i>=0;i--) if(cnt>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli); if(!cnt) return t; t=m,cnt--; for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli); return t; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m>>q; for(int i=1;im;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i]; fill(st[m],st[m]+63,m); for(int k=1;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1]; while(q--){ int t; cin>>t; coutsolve(n-t+1)"\n"; } return 0; }` P2391 白雪皑皑 不难发现，后面的操作会覆盖前面的颜色，这是一个令人头疼的问题。 根据上面的思路，可以想到倒着进行操作，用连通块并查集维护那些被染了色的块，每次进行操作时找到区间可以染色的来染色。 染色时，我们将当前格子的父亲设为它右边格子，这样下次访问到这个格子时就可以直接跳过。 代码： C++ #include using namespace std; const int N=1e6+5; int n,m,p,q; int fa[N],col[N],st[N],ed[N]; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } int main(){ cin>>n>>m>>p>>q; for(int i=1;i=1;i--){ int l=((i*q+p)%n)+1,r=((i*p+q)%n)+1; if(l>r) swap(l,r); for(int j=l;j `#include using namespace std; #define int long long const int N=1e5+5; int n,m,q; int p[N],inv[N],st[N][70]; int solve(int x){//x表示 int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1)); for(int i=62;i>=0;i--) if(cnt>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli); if(!cnt) return t; t=m,cnt--; for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli); return t; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m>>q; for(int i=1;im;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i]; fill(st[m],st[m]+63,m); for(int k=1;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1]; while(q--){ int t; cin>>t; coutsolve(n-t+1)"\n"; } return 0; }` P16377 [NordicOI 2026] Name Change 改名 能交换的两个位置我们连一条边，易正同一连通块内的位置是可以互相交换的，所以我们用并查集维护，最后判断每个联通块对应的两个字符集是否相等。 代码： C++ #include using namespace std; const int N=2e5+5; int n,m; string s,t; int fa[N]; vector a[N],b,c; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } int main(){ cin>>n>>m>>s>>t; s="#"+s,t="#"+t; for(int i=1;i>x>>y; fa[find(y)]=find(x); } for(int i=1;i `#include using namespace std; #define int long long const int N=1e5+5; int n,m,q; int p[N],inv[N],st[N][70]; int solve(int x){//x表示 int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1)); for(int i=62;i>=0;i--) if(cnt>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli); if(!cnt) return t; t=m,cnt--; for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli); return t; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m>>q; for(int i=1;im;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i]; fill(st[m],st[m]+63,m); for(int k=1;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1]; while(q--){ int t; cin>>t; coutsolve(n-t+1)"\n"; } return 0; }` P1084 [NOIP 2012 提高组] 疫情控制 倍增题，尝试封锁根节点的子节点。 不难发现答案具有单调性，可以二分答案。 这里使用倍增，先贪心地往上跳，如果可以跳到根节点，就先让它呆在根节点儿子处，再找到所有需要驻扎的根节点儿子，进行贪心配对。 代码： C++ #include using namespace std; #define int long long const int N=6e4+5; int n,m,t,at,bt,ct,l,r,mid,ans; int d[N],a[N],st[N][20],dis[N][20],hav[N],ned[N]; bool haveans,sta[N],nd[N]; vector> g[N]; pair h[N]; void dfs1(int x,int fa){ for(auto u:g[x]){ int y=u.first,z=u.second; if(y==fa) continue; d[y]=d[x]+1; st[y][0]=x,dis[y][0]=z; for(int j=1;j=0;j--) if(st[x][j]>1&&cnt+dis[x][j]=ned[i]) i++,j++; else j++; } if(i>bt) return 1; return 0; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; t=log2(n)+1; for(int i=1;i>x>>y>>z; g[x].push_back({y,z}); g[y].push_back({x,z}); r+=z; } d[1]=1; dfs1(1,0); cin>>m; for(int i=1;i>a[i]; while(l>1; if(check(mid)) r=mid-1,ans=mid,haveans=1; else l=mid+1; } if(!haveans) cout `#include using namespace std; #define int long long const int N=1e5+5; int n,m,q; int p[N],inv[N],st[N][70]; int solve(int x){//x表示 int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1)); for(int i=62;i>=0;i--) if(cnt>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli); if(!cnt) return t; t=m,cnt--; for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli); return t; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m>>q; for(int i=1;im;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i]; fill(st[m],st[m]+63,m); for(int k=1;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1]; while(q--){ int t; cin>>t; coutsolve(n-t+1)"\n"; } return 0; }` P3098 [USACO13DEC] The Bessie Shuffle G 考虑对操作进行逆操作，直接模拟会超时，想到使用倍增，详细的看代码实现： C++ #include using namespace std; #define int long long const int N=1e5+5; int n,m,q; int p[N],inv[N],st[N][70]; int solve(int x){//x表示需要当前卡片是第几轮被取出的 int cnt=min(x,n-m+1),//cnt表示需要经历的A类洗牌的次数 t=max(0ll,x-(n-m+1));//t表示A类洗牌后的位置 for(int i=62;i>=0;i--) if(cnt>=(1ll=0;i--) if(cnt>=(1ll>n>>m>>q; for(int i=1;i>p[i],inv[p[i]]=i,st[i-1][0]=inv[i]; fill(st[m],st[m]+63,m); for(int k=1;k>t; cout `#include using namespace std; #define int long long const int N=1e5+5; int n,m,q; int p[N],inv[N],st[N][70]; int solve(int x){//x表示需要当前卡片是第几轮被取出的 int cnt=min(x,n-m+1),//cnt表示需要经历的A类洗牌的次数 t=max(0ll,x-(n-m+1));//t表示A类洗牌后的位置 for(int i=62;i>=0;i--) if(cnt>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli);//倍增进行逆A类洗牌 if(!cnt) return t; t=m,cnt--; for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli);//剩余卡片不够m张，倍增直接取出 return t; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m>>q; for(int i=1;im;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i]; fill(st[m],st[m]+63,m); for(int k=1;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1]; while(q--){ int t; cin>>t; coutsolve(n-t+1)"\n"; } return 0; }`
ZR 集训 Day1 - 基础数据结构及其应用
笔记