有一段时间没写总结了，不能再拖了。。。 26 NOIP 二十连测 day1 | 正睿 OI 题目 #3681 | 正睿 OI 根据每个人最多连两条边可以知道，最后的连通块要么是环、要么是链，那就简单了。 但是挂了十分，原因是当一个连通块没有产生贡献时，就不需要再删边了。 代码： C++#include using namespace std; #define int long long const int N=1e6+5; int n,m,k,ans1,ans2; vector g[N]; int fa[N],siz[N],sum[N],tag[N]; int find(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x; } signed main(){ cinnmk; for(int i=1;iuv; int fu=find(u),fv=find(v); if(fu==fv){ sum[fu]++; continue; } if(siz[fu]#include using namespace std; #define int long long const int N=1e6+5; int n,m,k,ans1,ans2; vectorint g[N]; int fa[N],siz[N],sum[N],tag[N]; int find(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x; } signed main(){ cinnmk; for(int i=1;in;i++) fa[i]=i,siz[i]=1; for(int i=1,u,v;im;i++){ cinuv; int fu=find(u),fv=find(v); if(fu==fv){ sum[fu]++; continue; } if(siz[fu]siz[fv]) swap(fu,fv); fa[fv]=fu,siz[fu]+=siz[fv],sum[fu]+=sum[fv]+1; } for(int i=1;in;i++){ int f=find(i); if(tag[f]) continue; tag[f]=1; if(sum[f]==siz[f]&&siz[f]==k){ ans1+=k; continue; } ans1+=siz[f]/k*k; if(siz[f]/k*k) ans2+=(siz[f]+k-1)/k-1+(sum[f]==siz[f]); } coutans1" "ans2; return 0; } 题目 #3683 | 正睿 OI 对于 $A$ 中的一条边 $(u,v)$（$u$ 是 $v$ 的祖先），总能在 $B$ 中对应一条链 $L$，且 $L_1=u,L_n=v$。 若一个点在图 $A$ 中 $v$ 子树内，那就把它标记为 $1$，反之标记为 $0$，那我们相当于是要在 $L$ 上找到一个为 $1$ 一个为 $0$ 的相邻的两个点。由于 $L$ 的两端是满足一个为 $1$ 一个为 $0$ 的，所以可以直接二分，保证二分区间的两个端点一个为 $1$ 一个为 $0$ 即可。 代码： C++#include using namespace std; #define int long long const int N=2e5+5; int n,idx; int dfn[N],siz[N],depa[N],dep[N],fa[N][20]; pair e[N]; vector a[N],b[N]; map,int mp; void dfsa(int u,int f){ dfn[u]=++idx,siz[u]=1,depa[u]=depa[f]+1; for(auto v:a[u]){ if(v==f) continue; dfsa(v,u); siz[u]+=siz[v]; } } void dfsb(int u,int f){ fa[u][0]=f,dep[u]=dep[f]+1; for(int i=1;i=0;i--) if(dep[fa[u][i]]=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=19;i=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int jump(int u,int v,int lca,int x){ int d=dep[u]-dep[lca],len=dep[u]+dep[v]-dep[lca]*2; if(xi)&1) u=fa[u][i]; return u; } else{ x=len-x; for(int i=0;ii)&1) v=fa[v][i]; return v; } } void solve(int u,int v){ if(depa[u]depa[v]) swap(u,v); int lca=getlca(u,v),len=dep[u]+dep[v]-dep[lca]*2; int l=0,r=len; while(l+11; int p=jump(u,v,lca,mid); if(dfn[p]=dfn[v]&&dfn[p]n; for(int i=1,u,v;iuv; e[i]={u,v}; a[u].push_back(v); a[v].push_back(u); } for(int i=1,u,v;iuv; b[u].push_back(v); b[v].push_back(u); mp[{u,v}]=mp[{v,u}]=i; } dfsa(1,0); dfsb(1,0); for(int i=1;i#include using namespace std; #define int long long const int N=2e5+5; int n,idx; int dfn[N],siz[N],depa[N],dep[N],fa[N][20]; pairint,int e[N]; vectorint a[N],b[N]; mappairint,int,int mp; void dfsa(int u,int f){ dfn[u]=++idx,siz[u]=1,depa[u]=depa[f]+1; for(auto v:a[u]){ if(v==f) continue; dfsa(v,u); siz[u]+=siz[v]; } } void dfsb(int u,int f){ fa[u][0]=f,dep[u]=dep[f]+1; for(int i=1;i20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(auto v:b[u]){ if(v==f) continue; dfsb(v,u); } } int getlca(int u,int v){ if(dep[u]dep[v]) swap(u,v); for(int i=19;i=0;i--) if(dep[fa[u][i]]=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=19;i=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int jump(int u,int v,int lca,int x){ int d=dep[u]-dep[lca],len=dep[u]+dep[v]-dep[lca]*2; if(xd){ for(int i=0;i20;i++) if((xi)&1) u=fa[u][i]; return u; } else{ x=len-x; for(int i=0;i20;i++) if((xi)&1) v=fa[v][i]; return v; } } void solve(int u,int v){ if(depa[u]depa[v]) swap(u,v); int lca=getlca(u,v),len=dep[u]+dep[v]-dep[lca]*2; int l=0,r=len; while(l+1r){ int mid=(l+r)1; int p=jump(u,v,lca,mid); if(dfn[p]=dfn[v]&&dfn[p]dfn[v]+siz[v]) r=mid; else l=mid; } coutmp[{jump(u,v,lca,l),jump(u,v,lca,r)}]"\n"; } signed main(){ freopen("trees.in","r",stdin); freopen("trees.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinn; for(int i=1,u,v;in;i++){ cinuv; e[i]={u,v}; a[u].push_back(v); a[v].push_back(u); } for(int i=1,u,v;in;i++){ cinuv; b[u].push_back(v); b[v].push_back(u); mp[{u,v}]=mp[{v,u}]=i; } dfsa(1,0); dfsb(1,0); for(int i=1;in;i++) solve(e[i].first,e[i].second); return 0; } 题目 #3682 | 正睿 OI 考虑给每个连通块一个随机权值，并记录一个点在所有图中所属连通块的权值的异或和，并同时记录这个点在多少个图中是连了边的。 考虑当一个点新连边时，如果这个点在连边后刚好在 $k$ 张图上都连了边，那就把这个点的异或和权值记录到哈希表中并更新答案，因为哈希表内所有相同异或和权值的点两两都能产生贡献。 连边时启发式合并即可，这里每张图的并查集必须要用动态的内存，否则会爆炸。 代码： C++#include using namespace std; typedef unsigned long long ull; const int N=5e5+5; int n,k,q; long long ans; int cnt[N]; ull vis[N]; unordered_map mp; mt19937_64 rnd(rand()); struct dsu{ unordered_map fa,siz; unordered_map w; unordered_map d; void newd(int x){ if(fa.count(x)) return; fa[x]=x,siz[x]=1,d[x].push_back(x); } int find(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x; } void remove(ull wis){ ans-=1ll*mp[wis]*(mp[wis]-1)/2; mp[wis]--; ans+=1ll*mp[wis]*(mp[wis]-1)/2; } void add(ull wis){ ans-=1ll*mp[wis]*(mp[wis]-1)/2; mp[wis]++; ans+=1ll*mp[wis]*(mp[wis]-1)/2; } void merge(int x,int y){ newd(x),newd(y); int fx=find(x),fy=find(y); if(fx==fy) return; if(siz[fx]siz[fy]) swap(fx,fy),swap(x,y); if(siz[fy]==1){ w[fy]=rnd(),fa[fx]=fy,siz[fy]+=siz[fx]; d[fy].push_back(x); cnt[x]++,cnt[y]++; vis[x]^=w[fy],vis[y]^=w[fy]; if(cnt[x]==k) add(vis[x]); if(cnt[y]==k) add(vis[y]); } else if(siz[fx]==1){ fa[fx]=fy,siz[fy]+=siz[fx]; d[fy].push_back(x); cnt[x]++,vis[x]^=w[fy]; if(cnt[x]==k) add(vis[x]); } else{ fa[fx]=fy,siz[fy]+=siz[fx]; for(int i:d[fx]){ d[fy].push_back(i); vis[i]^=w[fx]^w[fy]; if(cnt[i]==k){ remove(vis[i]^w[fx]^w[fy]); add(vis[i]); } } } } }g[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinnkq; while(q--){ int id,x,y; cinidxy; g[id].merge(x,y); cout#include using namespace std; typedef unsigned long long ull; const int N=5e5+5; int n,k,q; long long ans; int cnt[N]; ull vis[N]; unordered_mapull,int mp; mt19937_64 rnd(rand()); struct dsu{ unordered_mapint,int fa,siz; unordered_mapint,ull w; unordered_mapint,vectorint d; void newd(int x){ if(fa.count(x)) return; fa[x]=x,siz[x]=1,d[x].push_back(x); } int find(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x; } void remove(ull wis){ ans-=1ll*mp[wis]*(mp[wis]-1)/2; mp[wis]--; ans+=1ll*mp[wis]*(mp[wis]-1)/2; } void add(ull wis){ ans-=1ll*mp[wis]*(mp[wis]-1)/2; mp[wis]++; ans+=1ll*mp[wis]*(mp[wis]-1)/2; } void merge(int x,int y){ newd(x),newd(y); int fx=find(x),fy=find(y); if(fx==fy) return; if(siz[fx]siz[fy]) swap(fx,fy),swap(x,y); if(siz[fy]==1){ w[fy]=rnd(),fa[fx]=fy,siz[fy]+=siz[fx]; d[fy].push_back(x); cnt[x]++,cnt[y]++; vis[x]^=w[fy],vis[y]^=w[fy]; if(cnt[x]==k) add(vis[x]); if(cnt[y]==k) add(vis[y]); } else if(siz[fx]==1){ fa[fx]=fy,siz[fy]+=siz[fx]; d[fy].push_back(x); cnt[x]++,vis[x]^=w[fy]; if(cnt[x]==k) add(vis[x]); } else{ fa[fx]=fy,siz[fy]+=siz[fx]; for(int i:d[fx]){ d[fy].push_back(i); vis[i]^=w[fx]^w[fy]; if(cnt[i]==k){ remove(vis[i]^w[fx]^w[fy]); add(vis[i]); } } } } }g[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinnkq; while(q--){ int id,x,y; cinidxy; g[id].merge(x,y); coutans"\n"; } return 0; } 题目 #3684 | 正睿 OI 受到题解的小点的处理方法的启发，尝试直接就这么草一下，结果草过去了，甚至榜上有名，故再次庆祝一下。 爆草代码： C++#include using namespace std; #define int long long const int N=1e5+5,M=18; int n,q,a[N],lg[N],mn[M][N],mx[M][N]; vector p[N]; map,int mp; int qmn(int l,int r){ int k=lg[r-l+1]; return min(mn[k][l],mn[k][r-(11; if(qmn(mid,y)=x&&qmx(mid,y)1; if(qmn(y,mid)=x&&qmx(y,mid)y||p[x].empty()||p[y].empty()) return 0; if(x==y){ int ans=0; for(int i=0;ip[v].size()) swap(u,v); int ans=0,lp=0; for(int i=0;iw) continue; auto it=lower_bound(p[v].begin(),p[v].end(),w); int nv=(it!=p[v].end()?*it:n+1); int lv=(it!=p[v].begin()?*prev(it):0); int tot=(w-l+1)*(r-w+1); int a1=max(0ll,w-max(l,lv+1)+1); int a2=max(0ll,min(r,nv-1)-w+1); ans+=tot-a1*a2; } return ans; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinnq; for(int i=2;ia[i]; p[a[i]].push_back(i); mn[0][i]=mx[0][i]=a[i]; } for(int j=1;jxy; if(mp.count({x,y})) cout#include using namespace std; #define int long long const int N=1e5+5,M=18; int n,q,a[N],lg[N],mn[M][N],mx[M][N]; vectorint p[N]; mappairint,int,int mp; int qmn(int l,int r)…
10.19 比赛总结
ooliver