Description

小A得了憂郁綜合癥，小B正在想辦法開導(dǎo)她。
機(jī)智的小B決定陪著小A玩游戲，他從魔法的世界里變出一張無向聯(lián)通圖，每條邊上都有邊權(quán)。小B定義一條路徑的權(quán)值為所有經(jīng)過邊中的最大權(quán)值，小A則定義兩點(diǎn)的最短路徑為所有路徑中權(quán)值最小的路徑權(quán)。
每次小A和小B會(huì)選出k對(duì)點(diǎn)mi_1,mi_2，分別計(jì)算出mi_1,mi_2的最短路徑ti,然后小B會(huì)拿出k堆靈魂寶石，每堆有ti個(gè)。然后小A先從一堆中選出若干個(gè)靈魂寶石拿走，接下來小B重復(fù)同樣的操作，如此反復(fù)，直到取走最后一顆靈魂寶石，然后取走最后一顆寶石的人獲勝。
小B認(rèn)為這樣游戲太簡(jiǎn)單，于是他會(huì)不定期向這張圖上加上一些邊，以增大游戲難度。
小A具有預(yù)知未來的能力，她看到了自己和小B在未來游戲中的選擇，以及小B增加的邊。現(xiàn)在對(duì)于每次游戲，小A想知道自己是否存在必勝的方法。但是預(yù)知未來已經(jīng)消耗了她太多精力，出于疲憊她只好找到了你。

Input

第一行三個(gè)數(shù)N和M和K，表示這張無向圖初始的點(diǎn)數(shù)與邊數(shù)，以及每次詢問的點(diǎn)對(duì)的個(gè)數(shù)；
接下來M行，每行三個(gè)數(shù)u,v,q，表示點(diǎn)u和點(diǎn)v之間存在一條權(quán)值為q的
邊；
接下來一行一個(gè)數(shù)Q，表示操作總數(shù)；
接下來Q行，表示操作，每行格式為下面兩條中的一條：
1.add u v q：表示在u與v之間加上一條邊權(quán)為q的邊；
2.game m1_1 m1_2 … mk_1 mk_2：表示一次游戲中選擇的k對(duì)點(diǎn)。
數(shù)據(jù)保證1≤u,v,mi_1,mi_2≤n，1≤q，mi_1≠mi_2

Output

對(duì)于每個(gè)game輸出一行，若小A存在必勝策略，則輸出“madoka”，否則輸出“Baozika”，以回車結(jié)尾

Sample Input

5 6 2
1 2 3
2 3 6
4 2 4
5 3 5
3 4 5
5 1 5
4
game 1 3 4 3
game 1 5 2 4
add 2 5 4
game 1 5 3 4

Sample Output

Baozika
madoka
madoka

Data Constraint

Solution

• 首先考慮獲勝策略。k 堆石子，每堆石子數(shù)量為 ai 。

• A 和 B 玩游戲，輪流從其中某一堆石子中取出若干個(gè)石子，最后取完石子的人獲勝。

• 結(jié)論：如 a1?xor?a2?xor?...?xor?ak=0 ，則先手輸，否則先手贏，xor 表示異或。

• 證明：若 a1?xor?a2?xor?...?xor?an≠0 ，則一定可以從其中某堆石子中取出一些石子，

• 使得剩下的石子數(shù)異或結(jié)果為 0，若 a1?xor?a2?xor?...?xor?an=0 ，

• 則進(jìn)行一次取石子操作后 a1?xor?a2?xor?...?xor?an 一定不等于 0，

• 按照這樣的操作下去，最后一定會(huì)出現(xiàn) a1=a2=?...?=an=0 的情況。

• 問題就變成了加邊和求路徑長(zhǎng)。

算法1

• 看到詢問次數(shù)很少，考慮 倍增+LCA 。

• 根據(jù)最小生成樹的性質(zhì)，我們發(fā)現(xiàn)路徑一定在 無向圖的最小生成樹 上。

• 每次維護(hù)最小生成樹，完成詢問用樹上 LCA 即可。

• 事實(shí)上，加入一條邊只有可能改變最小生成樹上的一條邊。

• 假設(shè)加邊為 x,y,z，我們可以找到 x 到 y 的路徑上的最大邊權(quán)。

• 若該邊權(quán) >z ，顯然將新邊加入更優(yōu)，否則忽略新邊。

• 再將所有邊用 O(N) 的插入排序排序即可。

• 套上在線 LCA 算法就可以愉快的 AC 了。

• 時(shí)間復(fù)雜度 O(D?NlogN+(Q?D)?logN) ，其中 D 為加邊次數(shù)。

• 注意存邊權(quán)要開 long long 。

算法2

• 如果加邊次數(shù)不限呢？直接上 LCT 啊！

• 用 Link?Cut?Tree 維護(hù)最小生成樹即可。

• 若當(dāng)前加入的邊小于當(dāng)前樹中邊權(quán)的最大值，則將那個(gè)最大的邊刪去，再連當(dāng)前邊。

• 維護(hù)邊權(quán)的話可以開一個(gè)虛點(diǎn)存邊權(quán)，再連向兩個(gè)點(diǎn)即可。

• 注意開夠數(shù)組范圍。

Code（倍增LCA）

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int N=5002,M=105001; struct data {int x,y;LL z; }a[M]; int tot,num; int first[N],next[N<<1],en[N<<1]; LL w[N<<1]; int f[N],size[N],fa[N][13],dep[N]; LL g[N][13]; template<typename T>inline T read() {T X=0,w=0; char ch=0;while(ch<'0' || ch>'9') {w|=ch=='-';ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline LL max(LL x,LL y) {return x>y?x:y; } inline bool cmp(data x,data y) {return x.z<y.z; } inline int get(int x) {return f[x]==x?x:f[x]=get(f[x]); } inline bool merge(int x,int y) {if(get(x)==get(y)) return false;if(size[f[x]]<size[f[y]]) swap(x,y);size[f[x]]+=size[f[y]];f[f[y]]=x;return true; } inline void insert(int x,int y,LL z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void dfs(int x) {dep[x]=dep[fa[x][0]]+1;for(int i=first[x];i;i=next[i])if(en[i]^fa[x][0]){fa[en[i]][0]=x;g[en[i]][0]=w[i];dfs(en[i]);} } inline LL lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);LL mx=0;for(int i=log2(dep[x]);i>=0;i--)if(dep[fa[x][i]]>=dep[y]){mx=max(mx,g[x][i]);x=fa[x][i];}if(x==y) return mx;for(int i=log2(dep[x]);i>=0;i--)if(fa[x][i]!=fa[y][i]){mx=max(mx,max(g[x][i],g[y][i]));x=fa[x][i],y=fa[y][i];}mx=max(mx,max(g[x][0],g[y][0]));return mx; } int main() {int n=read<int>(),m=read<int>(),k=read<int>();for(int i=1;i<=m;i++)a[i].x=read<int>(),a[i].y=read<int>(),a[i].z=read<LL>();sort(a+1,a+1+m,cmp);for(int i=1;i<=n;i++) size[f[i]=i]=1;for(int i=1,k=1;i<=m;i++)if(merge(a[i].x,a[i].y)){insert(a[i].x,a[i].y,a[i].z);insert(a[i].y,a[i].x,a[i].z);a[++num]=a[i];if(++k==n) break;}dfs(1);for(int j=1,p=log2(n);j<=p;j++)for(int i=1;i<=n;i++){fa[i][j]=fa[fa[i][j-1]][j-1];g[i][j]=max(g[fa[i][j-1]][j-1],g[i][j-1]);}int q=read<int>();while(q--){char ch=getchar();while(ch!='g' && ch!='a') ch=getchar();if(ch=='g'){LL ans=0;for(int i=1;i<=k;i++) ans^=lca(read<int>(),read<int>());if(ans) puts("madoka"); else puts("Baozika");}else{int x=read<int>(),y=read<int>();LL z=read<LL>();if(lca(x,y)<=z) continue;tot=fa[1][0]=0;memset(first,0,sizeof(first));memset(g,0,sizeof(g));//a[++num]=(data){x,y,z};//sort(a+1,a+1+num,cmp);bool pd=true;for(int i=1;i<=num;i++)if(z<=a[i].z){for(int j=++num;j>i;j--) a[j]=a[j-1];a[i]=(data){x,y,z};pd=false;break;}if(pd) a[++num]=(data){x,y,z};for(int i=1;i<=n;i++) size[f[i]=i]=1;num=0;for(int i=1,k=1;i<=n;i++)if(merge(a[i].x,a[i].y)){insert(a[i].x,a[i].y,a[i].z);insert(a[i].y,a[i].x,a[i].z);a[++num]=a[i];if(++k==n) break;}dfs(1);for(int j=1,p=log2(n);j<=p;j++)for(int i=1;i<=n;i++){fa[i][j]=fa[fa[i][j-1]][j-1];g[i][j]=max(g[fa[i][j-1]][j-1],g[i][j-1]);}}}return 0; }

Code（Link-Cut-Tree）

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; typedef long long LL; const int N=110005; struct data {int x,y; }a[N]; int tot,top; int fa[N],s[N][2],mx[N],st[N]; LL key[N]; bool rev[N]; template<typename T>inline T read() {T X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline bool isroot(int x) {return s[fa[x]][0]^x && s[fa[x]][1]^x; } inline void modify(int x) {if(x) swap(s[x][0],s[x][1]),rev[x]^=1; } inline void update(int x) {mx[x]=key[mx[s[x][0]]]>key[mx[s[x][1]]]?mx[s[x][0]]:mx[s[x][1]];if(key[x]>key[mx[x]]) mx[x]=x; } inline void down(int x) {if(rev[x]){modify(s[x][0]),modify(s[x][1]);rev[x]=false;} } inline void rotate(int x) {int y=fa[x],w=pd(x);if(s[y][w]=s[x][w^1]) fa[s[x][w^1]]=y;if((fa[x]=fa[y]) && !isroot(y)) s[fa[y]][pd(y)]=x;s[fa[y]=x][w^1]=y;update(y); } inline void splay(int x) {for(int y=st[top=1]=x;!isroot(y);y=fa[y]) st[++top]=fa[y];while(top) down(st[top--]);for(int y;!isroot(x);rotate(x))if(!isroot(y=fa[x])) rotate(pd(x)==pd(y)?y:x);update(x); } inline void access(int x) {for(int y=0;x;x=fa[y=x]) splay(x),s[x][1]=y,update(x); } inline void mkroot(int x) {access(x),splay(x),modify(x); } inline void link(int x,int y) {mkroot(x),fa[x]=y; } inline void cut(int x,int y) {mkroot(x),access(y),splay(y);fa[x]=s[y][0]=0; } inline int get(int x) {access(x),splay(x);int y=x;while(s[y][0]) y=s[y][0];return y; } int main() {int n=tot=read<int>(),m=read<int>(),k=read<int>();for(int i=1;i<=m;i++){int x=read<int>(),y=read<int>();LL z=read<LL>();a[i]=(data){x,y};key[mx[++tot]=tot]=z;if(get(x)^get(y)) link(tot,x),link(tot,y); else{mkroot(x),access(y),splay(y);int del=mx[y];if(z<key[del]){cut(del,a[del-n].x),cut(del,a[del-n].y);link(tot,x),link(tot,y);}}}int q=read<int>();while(q--){char ch=getchar();while(ch^'g' && ch^'d') ch=getchar();if(ch=='g'){LL ans=0;for(int i=1;i<=k;i++){int x=read<int>(),y=read<int>();mkroot(x),access(y),splay(y);ans^=key[mx[y]];}puts(ans?"madoka":"Baozika");}else{int x=read<int>(),y=read<int>();LL z=read<LL>();a[++m]=(data){x,y};key[mx[++tot]=tot]=z;if(get(x)^get(y)) link(tot,x),link(tot,y); else{mkroot(x),access(y),splay(y);int del=mx[y];if(z<key[del]){cut(del,a[del-n].x),cut(del,a[del-n].y);link(tot,x),link(tot,y);}}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5466. 【NOIP2017提高A组冲刺11.9】玩游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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