文章目錄

• 前言
• 題目解析
• • 染色計(jì)劃（color）
  • 奇度邊集（edges）
  • 猜拳游戲（guess）
• 代碼
• • T1
  • T2
  • • LCT
    • 整體二分
• 總結(jié)

前言

120pts
期望：40+100+20=160
實(shí)際：40+60+20=120
rnk 9

我yue了。
怎么又是不可抗力性掛分…
ybt的數(shù)據(jù)鍋了，點(diǎn)編號(hào)竟然有0，splay（0）直接RE到天荒地老。
就這還有人過？
但這次這個(gè)T2做的還是挺不錯(cuò)的，雖然做了兩個(gè)點(diǎn)，但是確實(shí)是一道挺難的題。
為什么分都這么高啊qwq
人強(qiáng)我菜。

題目解析

染色計(jì)劃（color）

這個(gè)題挺妙的。
不是特別難，但做完B確實(shí)沒有太多時(shí)間想這個(gè)題了。

考慮點(diǎn)分治。
我們每次對(duì)于分治重心，都強(qiáng)制讓它被選取，把其顏色的點(diǎn)加入隊(duì)列。每次彈出隊(duì)首，每次往當(dāng)前的父親（即重心方向）跳，將途中未入隊(duì)的顏色加入隊(duì)列。如果遇到當(dāng)前分治聯(lián)通塊以外的點(diǎn)，就直接放棄這次更新答案。
關(guān)于正確性：反過來想，對(duì)于最優(yōu)方案，必然存在一個(gè)點(diǎn)分治過程中的聯(lián)通塊，使得最優(yōu)方案的聯(lián)通子樹出現(xiàn)在一個(gè)極大的分治聯(lián)通塊中，且經(jīng)過這個(gè)聯(lián)通塊。（一開始可以把這個(gè)聯(lián)通塊設(shè)為全集，若不過重心，就可以往一個(gè)聯(lián)通塊遞歸）

還有一個(gè)虛樹的做法，但pdf講的很草率，我也沒明白…但是似乎就是對(duì)我寫的那個(gè)暴力思路的一定優(yōu)化。

奇度邊集（edges）

大概在九點(diǎn)的時(shí)候看到了本題的關(guān)鍵性質(zhì)：合法的充要條件是所有聯(lián)通塊的點(diǎn)數(shù)均為偶數(shù)。
于是決定這次考試就搞它了。
這個(gè)題確實(shí)挺難的，我以為看到這個(gè)性質(zhì)之后應(yīng)該就呼之欲出了，結(jié)果呼了半天也沒出來…
想了很多方面，由于顯然的二分性，也想過整體二分，但是常規(guī)的整體二分做不了之后我就放棄了，也是因?yàn)檎w二分是比較冷門的算法。

LCT的做法似乎還是比較好想的。
從已經(jīng)存在解的時(shí)刻（可以并查集簡(jiǎn)單求出），然后開始考慮優(yōu)化答案。
最優(yōu)解必然在最小生成森林上，這也是LCT的拿手好戲。
然后每次只需要嘗試刪去權(quán)值最大的邊，這個(gè)邊可以用 set 來找到。
能刪去當(dāng)且僅當(dāng)邊兩側(cè)的聯(lián)通塊都是偶數(shù)大小。
個(gè)人的做法比較粗暴，就是維護(hù)虛子樹大小，然后暴力把邊斷開，看看兩遍大小，如果不能斷就再連回去。
由于每條邊只能刪一次，總復(fù)雜度 $O(n\log n)$。
然而修完數(shù)據(jù)后一交發(fā)現(xiàn)T成70，啊哈！
CF神機(jī)尚且給4s，ybt破機(jī)器給1s就離譜。

無奈只好看看整體二分怎么做。
（似乎主流說這個(gè)做法是sdq分治，但個(gè)人認(rèn)為更像整體二分，但名字也不重要吧）
實(shí)現(xiàn)不是特別難，但是不太容易想到。（和LCT正好反過來）
顯然但重要的性質(zhì)：答案單調(diào)不升。
常規(guī)的遞歸函數(shù) $solve(l,r,L,R)$，表示 $(l,r)$ 處理的詢問，答案屬于 $[L,R]$。
需要保證在執(zhí)行該函數(shù)時(shí)加入且僅加入了 $[1,l?1]$ 的所有邊權(quán)屬于 $[1,L]$ 的邊。
嘗試求出 $mid$ 的答案。先把 $[l,mid]$ 邊權(quán)屬于 $[1,L]$ 的邊加入，再?gòu)?$L$ 開始權(quán)值從小到大枚舉邊，把所有 $[1,mid]$ 的邊加入，直到符合要求，當(dāng)前邊權(quán)即 $an{s}_{mid}$。

然后就是遞歸處理 $solve(l,mid?1,an{s}_{mid},R),solve(mid+1,r,L,an{s}_{mid})$，注意依然要滿足前提保證。
考慮單層復(fù)雜度是 $O((r?l)+(R?L))$，由于遞歸的每層值域和詢問區(qū)間的大小都是 $O(m)$，所以遞歸樹大小為 $O(m\log m)$
需要啟發(fā)式合并帶log的可撤銷并查集，總復(fù)雜度 $O(m\log m\log n)$。

猜拳游戲（guess）

三進(jìn)制 FWT神題。
然鵝我FWT已經(jīng)全忘光樂，啊哈！
好像還需要一點(diǎn)矩陣相關(guān)，可我線代還幾乎屬于知識(shí)荒漠…
直接開擺

代碼

T1

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=3e5+100;int n,m; int ans=2e9;struct node{int to,nxt; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt;return; } vector<int>v[N]; int hson[N],S,rt,siz[N],mx[N],vis[N],tag[N],tim,fa[N]; int col[N]; void findrt(int x,int f){siz[x]=1;tag[x]=tim;mx[x]=0;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f||vis[to]) continue;findrt(to,x);siz[x]+=siz[to];if(mx[x]<siz[to]) mx[x]=siz[to];}mx[x]=max(mx[x],S-siz[x]);if(mx[x]<mx[rt]) rt=x;return; } void dfs(int x,int f){fa[x]=f;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f||vis[to]) continue;dfs(to,x);}return; } int q[N],st,ed,jd[N],inque[N]; bool add(int c){jd[c]=tim;for(int x:v[c]){if(tag[x]!=tim) return false;q[++ed]=x;inque[x]=tim;//printf(" add: %d\n",x);}return true; } void calc(int rt){st=1;ed=0;if(!add(col[rt])) return;int res(0);while(st<=ed){int now=q[st++];if(fa[now]) now=fa[now];while(inque[now]!=tim){//printf("now=%d\n",now);if(jd[col[now]]!=tim){if(!add(col[now])) return;++res;}now=fa[now];}}ans=min(ans,res); } void solve(int x,int nS){++tim;S=nS;rt=0;findrt(x,0);x=rt;vis[x]=1;dfs(x,0);//printf("x=%d\n",x);calc(x);for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]) continue;solve(to,nS-mx[to]);}return; }signed main(){freopen("color.in","r",stdin);freopen("color.out","w",stdout);memset(fi,-1,sizeof(fi));cnt=-1;n=read();m=read();mx[0]=2e9;for(int i=1;i<n;i++){int x=read(),y=read();addline(x,y);addline(y,x);}for(int i=1;i<=n;i++){col[i]=read();v[col[i]].push_back(i);}solve(1,n);printf("%d\n",ans);return 0; } /* */

T2

LCT

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } void write(ll x){if(x>9) write(x/10);putchar('0'+x%10); } const int N=4e5+100;int n,m;struct edge{int x,y,w,id;bool operator < (const edge oth)const{if(w!=oth.w) return w<oth.w;else return id<oth.id;} }e[N]; set<edge>s;int tr[N][2],f[N],rev[N],val[N],mx[N],tot,siz1[N],siz2[N]; inline bool nroot(int x){return tr[f[x]][0]==x||tr[f[x]][1]==x; } inline bool which(int x){return tr[f[x]][1]==x; } inline void pushup(int x){mx[x]=x;if(tr[x][0]){if(val[mx[tr[x][0]]]>val[mx[x]]) mx[x]=mx[tr[x][0]];}if(tr[x][1]){if(val[mx[tr[x][1]]]>val[mx[x]]) mx[x]=mx[tr[x][1]];}siz1[x]=siz1[tr[x][0]]+siz1[tr[x][1]]+siz2[x]+(x<=n);return; } inline void Rev(int x){if(x){rev[x]^=1;swap(tr[x][0],tr[x][1]);} } inline void pushdown(int x){if(rev[x]){rev[x]=0;Rev(tr[x][0]);Rev(tr[x][1]);} } inline void rotate(int x){int fa=f[x],gfa=f[fa];int d=which(x),son=tr[x][d^1];f[x]=gfa;if(nroot(fa)) tr[gfa][which(fa)]=x;f[fa]=x;tr[x][d^1]=fa;if(son){f[son]=fa;}tr[fa][d]=son;pushup(fa);pushup(x);return; } int zhan[N]; inline void splay(int x){int y(x),top(0);zhan[++top]=y;//debug("splay %d\n",x);while(nroot(y)) zhan[++top]=y=f[y];//debug(" %d\n",y);while(top) pushdown(zhan[top--]);for(int fa;fa=f[x],nroot(x);rotate(x)){if(nroot(fa)) which(fa)==which(x)?rotate(fa):rotate(x);} } inline void access(int x){for(int y(0);x;y=x,x=f[x]){splay(x);siz2[x]+=siz1[tr[x][1]];tr[x][1]=y;siz2[x]-=siz1[tr[x][1]];pushup(x);} } inline void makeroot(int x){access(x);splay(x);Rev(x); } inline int findroot(int x){access(x);splay(x);while(pushdown(x),tr[x][0]) x=tr[x][0];return x; } inline void split(int x,int y){makeroot(x);access(y);splay(y); } inline void link(int x,int y){//printf("link: %d %d\n",x,y);//assert(findroot(x)!=findroot(y));makeroot(x);//makeroot(y);access(y);splay(y);f[x]=y;siz2[y]+=siz1[x];pushup(y);return; } inline void cut(int x,int y){//printf("cut: %d %d\n",x,y);split(x,y);//if(tr[y][0]!=x||tr[x][1]){// printf("!!\n");// print();// exit(0);//}//assert(tr[y][0]==x&&!tr[x][1]);tr[y][0]=f[x]=0;pushup(y);return; } inline int Siz(int x){makeroot(x);return siz1[x]; }int fa[N],siz[N]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]); } inline void merge(int x,int y){x=find(x),y=find(y);if(x==y) return;if(siz[x]>siz[y]) swap(x,y);fa[x]=y;siz[y]+=siz[x];return; }int calc(){for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;int num=n;for(auto e:s){int x=find(e.x),y=find(e.y);if(x!=y&&(siz[x]&1)&&(siz[y]&1)) num-=2;merge(x,y);//printf(" (%d %d) tot=%d\n",x,y,tot);if(!num) return e.w;}return -1; } void bf(){for(int i=1;i<=m;i++){//printf("\ni=%d\n",i);e[i]=(edge){(int)read(),(int)read(),(int)read(),i};s.insert(e[i]);printf("%d\n",calc());} } int nam[N],bel[N]; void solve(){for(int i=0;i<=n;i++) val[i]=-1;tot=n;for(int i=1;i<=n;i++){fa[i]=i,siz[i]=siz1[i]=1;mx[i]=i;}int num=n;for(int i=1;i<=m;i++){//ok;int x=read(),y=read(),w=read();e[i]=(edge){x,y,w,i};if(x!=y){//printf("i=%d (%d %d %d) findroot=%d %d\n",i,x,y,w,findroot(x),findroot(y));if(find(x)!=find(y)){s.insert(e[i]);++tot;val[tot]=w;link(x,tot);link(y,tot);nam[i]=tot;bel[tot]=i;}else{split(x,y);int o=mx[y];if(val[o]>w){s.insert(e[i]);makeroot(o);//splay(o);tr[o][0]=f[tr[o][0]]=0;tr[o][1]=f[tr[o][1]]=0;s.erase(e[bel[o]]);++tot;val[tot]=w;link(x,tot);link(y,tot);nam[i]=tot;bel[tot]=i;}}}if(find(x)!=find(y)&&(siz[find(x)]&1)&&(siz[find(y)]&1)) num-=2;//printf("x=%d y=%d find=%d %d siz=%d %d num=%d\n",//x,y,find(x),find(y),siz[find(x)],siz[find(y)],num);merge(x,y);if(num) puts("-1");else{while(1){//debug("1\n");edge o=(*s.rbegin());//debug("2\n");int x=o.x,y=o.y,k=o.id,id=nam[k]; cut(id,x);cut(id,y);//debug("2\n");//printf(" k=%d (%d %d) id=%d siz=%d %d\n",k,x,y,id,Siz(x),Siz(y));if((Siz(x)&1)==0&&(Siz(y)&1)==0){s.erase(s.find(o));}else{//printf("recover\n");link(id,x);link(id,y);printf("%d\n",o.w);break;}}}//print();}return; }signed main(){freopen("edges.in","r",stdin);freopen("edges.out","w",stdout);n=read();m=read();if(n<=1000&&m<=3000) bf();else solve();//solve();return 0; } /* */

整體二分

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=8e5+100; const int M=1e6+100;int n,m,p,q;int fa[N],siz[N],u[N],v[N],top,num; int find(int x){return fa[x]==x?x:find(fa[x]); } inline void merge(int x,int y){if(!x||!y) return;x=find(x);y=find(y);if(x==y) return;if((siz[x]&1)&&(siz[y]&1)) num-=2;if(siz[x]>siz[y]) swap(x,y);fa[x]=y;siz[y]+=siz[x];++top;u[top]=x;v[top]=y;//printf("merge: %d %d num=%d\n",x,y,num);return; } inline void recover(int goal){while(top!=goal){int x=u[top],y=v[top];fa[x]=x;siz[y]-=siz[x];if((siz[x]&1)&&(siz[y]&1)) num+=2;--top;}return; }struct edge{int x,y,w,id; }e[N],E[N]; bool cmp(edge x,edge y){return x.w<y.w; } int mx; int ans[N]; void solve(int l,int r,int L,int R){if(l>r) return;if(L==R){for(int i=l;i<=r;i++) ans[i]=L;return;}//printf("solve: (%d %d) (%d %d)\n",l,r,L,R);int mid=(l+r)>>1,pre=top;for(int i=l;i<=mid;i++){if(e[i].w<=E[L].w) merge(e[i].x,e[i].y);}int o=top;//recover(pre);for(int i=L;i<=R;i++){if(E[i].id<=mid) merge(E[i].x,E[i].y);if(!num){ans[mid]=i;break;}}if(!ans[mid]) ans[mid]=m+1;//printf("mid=%d ans=%d\n",mid,ans[mid]);recover(o);solve(mid+1,r,L,ans[mid]);recover(pre);for(int i=L;i<=min(m,ans[mid]);i++){if(E[i].id<l) merge(E[i].x,E[i].y);}solve(l,mid-1,ans[mid],R);recover(pre); } signed main(){freopen("edges.in","r",stdin);freopen("edges.out","w",stdout);n=read();m=read();num=n;for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;for(int i=1;i<=m;i++){e[i]=E[i]=(edge){(int)read(),(int)read(),(int)read(),i};mx=max(mx,e[i].w);//printf("(%d %d)\n",e[i].x,e[i].y);}sort(E+1,E+1+m,cmp);solve(1,m,1,m+1);for(int i=1;i<=m;i++) printf("%d\n",ans[i]<=m?E[ans[i]].w:-1);return 0; } /* */

總結(jié)

沒有掛分，就還是不錯(cuò)的。
但是今天在T2上花的時(shí)間有點(diǎn)過長(zhǎng)了…
但是確實(shí)沒有浪費(fèi)時(shí)間，想解法，碼代碼，debug，對(duì)拍，過程中一直在做事。
還是要加快節(jié)奏吧。

總結(jié)

以上是生活随笔為你收集整理的2.12 模拟的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。