題意:

學(xué)過博弈論的同學(xué)都知道Nim游戲后手必勝的條件是異或和為0
給定一棵樹 ，支持修改單點點權(quán)，詢問鏈上異或和

預(yù)處理每個點到根的路徑的異或和
由于異或的特殊性質(zhì)，在求鏈x->y的異或和的時候，我們只需要知道x到根的異或和，y到根的異或和，將他們異或起來，最后異或上lca處的值即可。

如圖，查詢兩個灰色節(jié)點的異或和

如果一個點的值被修改，那么它和它的子樹到根的路徑的異或和的值都會被修改

所以，我們維護一棵dfs序為下標的線段樹，線段樹的sum意義是它的區(qū)間的值的異或和

修改一個值，如果該值為x，要變成y，那么給線段樹傳進一個x^y的值，這樣就能做到修改它和它的子樹的值

因為一個數(shù)異或本身等于0，然后再異或y，就變成y了

修改的區(qū)間為dfs[x]~dfs[x]+size[x]-1

查詢最近公共祖先我寫的是樹剖（常數(shù)小，又能順便求dfs序）

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int fa[500010],dep[500010],dfs[500010],top[500010],size[500010],son[500010],dfn=0; int to[1000100],next[1000100],h[500010],k=0;int a[500100],val[500010],n,m; int l[2000100],r[2000100],sum[2000100],lazy[2000100]; void ins(int u,int v){next[++k]=h[u];h[u]=k;to[k]=v;} void dfs1(int x,int d,int f) {dep[x]=d;fa[x]=f;size[x]=1;for(int i=h[x];i;i=next[i]){if(to[i]==f)continue;dfs1(to[i],d+1,x);size[x]+=size[to[i]];if(size[son[x]]<size[to[i]])son[x]=to[i];} } void dfs2(int x,int tp) {top[x]=tp;dfs[x]=++dfn;a[dfs[x]]=a[dfs[fa[x]]]^val[x];if(son[x])dfs2(son[x],tp);for(int i=h[x];i;i=next[i]){if(to[i]==son[x]||to[i]==fa[x])continue;dfs2(to[i],to[i]);} } int lca(int u,int v) {while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])v=fa[top[v]];else u=fa[top[u]];}if(dep[u]<dep[v])return u;else return v; } void pushdown(int x) {if(!lazy[x])return;lazy[x<<1]^=lazy[x];lazy[x<<1|1]^=lazy[x];sum[x<<1]^=lazy[x];sum[x<<1|1]^=lazy[x];lazy[x]=0; } void pushup(int x) {sum[x]=sum[x<<1]^sum[x<<1|1]; } void build(int x,int L,int R) {l[x]=L;r[x]=R;lazy[x]=0;if(L==R){sum[x]=a[L];return;}build(x<<1,L,(L+R)/2);build(x<<1|1,(L+R)/2+1,R);pushup(x); } void add(int x,int L,int R,int k) {if(L==l[x]&&R==r[x]){lazy[x]^=k;sum[x]^=k;return;}pushdown(x);int mid=(l[x]+r[x])/2;if(R<=mid)add(x<<1,L,R,k);else if(L>mid)add(x<<1|1,L,R,k);else {add(x<<1,L,mid,k);add(x<<1|1,mid+1,R,k);}pushup(x); } int query(int x,int k) {if(l[x]==k&&r[x]==k){return sum[x];}pushdown(x);int mid=(l[x]+r[x])/2;if(k<=mid)return query(x<<1,k);else return query(x<<1|1,k); } int main() {freopen("game.in","r",stdin);freopen("game.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&val[i]);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);ins(x,y);ins(y,x);}dfs1(1,1,0);dfs2(1,1);build(1,1,n);scanf("%d",&m);for(int i=1;i<=m;i++){char c[2];int x,y;scanf("%s%d%d",c,&x,&y);if(c[0]=='C'){add(1,dfs[x],dfs[x]+size[x]-1,val[x]^y);val[x]=y;}else{int ans=query(1,dfs[x])^query(1,dfs[y])^val[lca(x,y)];puts(ans?"Yes":"No");}} return 0; } View Code

如果把題目改成把x到y(tǒng)的鏈上加k，查詢x的值，那么怎么做呢 （數(shù)據(jù)范圍不變）

發(fā)現(xiàn)鏈修改實際上可以拆分成許多個對某個點到根的路徑上所有點的修改
給x到y(tǒng)的一條鏈加上v，假設(shè)x和y的lca是z，那么這個操作相當(dāng)于相當(dāng)于分別給x和y到根的路徑加上v，然后給z到根的路徑加上-v，給z的父親（如果有的話）到根的路徑加上-v

?

?

一個點會被影響當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)修改的那個點在他的子樹內(nèi)
對樹求dfs序，然后使用線段樹單點加，區(qū)間查詢即可。

?即更改從x到y(tǒng)的一條鏈，把x的值+k，把y的值+k，把z的值-k，把u的值-k（這些值初始為0）

我們查詢x時，查詢x及x的子樹的變化值的總和，再加上它自身的原數(shù)值即可

??

看到此題，首先想到的是文理分科的模型，但是這題比文理分科還簡單

我們發(fā)現(xiàn)相鄰的格子要選不同的東西才有額外收益，而文理分科是選相同的東西

我們可以把矩陣黑白染色，然后將一種顏色割到S和T表示的含義交換。

這樣就滿足了題目要求

#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int INF=1999999999; int r,c,d; int n,m; struct data{ int next,to,cap; } g[2000000]; int iter[11000],h[11000],level[11000],k=1,head,tail,q[11000]; void add(int from,int to,int cap) {g[++k].next=h[from];h[from]=k;g[k].to=to;g[k].cap=cap;g[++k].next=h[to];h[to]=k;g[k].to=from;g[k].cap=0; } void bfs(int s) {memset(level,0,sizeof(level));head=tail=0;q[tail++]=s;level[s]=1;while(head!=tail) {int u=q[head++];for(int i=h[u]; i; i=g[i].next) {if(!level[g[i].to]&&g[i].cap) {level[g[i].to]=level[u]+1;q[tail++]=g[i].to;}}} } int dfs(int u,int t,int f) {if(u==t)return f;int used=0,w;for(int &i=iter[u]; i; i=g[i].next) {if(g[i].cap&&level[g[i].to]==level[u]+1) {w=f-used;w=dfs(g[i].to,t,min(w,g[i].cap));if(w) {g[i].cap-=w;g[i^1].cap+=w;used+=w;if(used==f)return f;}}}return used; } int dinic(int s,int t) {int flow=0;for(;;) {for(int i=0; i<=n; i++)iter[i]=h[i];bfs(s);if(!level[t])return flow;flow+=dfs(s,t,INF);} } int main() {freopen("city.in","r",stdin);freopen("city.out","w",stdout);int r,c;scanf("%d%d",&r,&c);n=r*c;int S=0,T=n+1,tot=0;n++;for(int i=1;i<=r;i++)for(int j=1;j<=c;j++){int u;scanf("%d",&u);tot+=u;if(i%2==j%2)add(S,c*(i-1)+j,u);else add(c*(i-1)+j,T,u);}for(int i=1;i<=r;i++)for(int j=1;j<=c;j++){int u;scanf("%d",&u);tot+=u;if(i%2==j%2)add(c*(i-1)+j,T,u);else add(S,c*(i-1)+j,u);}for(int i=1;i<=r-1;i++)for(int j=1;j<=c;j++){int u;scanf("%d",&u);tot+=u;add(c*(i-1)+j,c*i+j,u);add(c*i+j,c*(i-1)+j,u);}for(int i=1;i<=r;i++)for(int j=1;j<=c-1;j++){int u;scanf("%d",&u);tot+=u;add(c*(i-1)+j,c*(i-1)+j+1,u);add(c*(i-1)+j+1,c*(i-1)+j,u);}printf("%d",tot-dinic(S,T));return 0; } View Code

以下所有數(shù)組下標從0開始

我們先預(yù)處理出每個位置開始，下一個字母的位置。

即用next[i][j]表示從第i個位置開始，下一個字母j的位置（包括本身），不存在設(shè)為451，0對應(yīng)a，1對應(yīng)b……

注意next[452][0……25]=451，next[|S|][0……25]=451

考慮狀壓DP

用dp[S]表示S中字母組成的所有排列的最后位置的最大值

舉個例子吧，S=13=1101，即acd三個字母組成的所有排列的最后位置的最大值

dp[S]=max(dp[S],next[dp[s^(1<<i)]+1][i]) ?(i∈S）dp[0]=-1;

用上面的那個例子，S=13=1101，則dp[S]=max（next[dp[12=1100]+1][0]，next[dp[9=1001]+1][2]，next[dp[5=0101]+1][3]）

最后如果dp[1111……11]=451，則不是，否則是

時間復(fù)雜度O(2^n * n)，發(fā)現(xiàn)無法通過n>21的數(shù)據(jù)

我們可以發(fā)現(xiàn)，最小長度至少為n*(n-1)+1 ?（當(dāng)n=4時，即abcdabcdabcda）

而22*21+1>450，所以輸出No

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int dp[5000000],next[500][27],n; string a; int DP(int S) {if(S==0||dp[S]!=-1)return dp[S];for(int i=0;i<n;i++)if((S>>i)&1)dp[S]=max(dp[S],next[DP(S^(1<<i))+1][i]);return dp[S]; } int main() {freopen("string.in","r",stdin);freopen("string.out","w",stdout);int T;scanf("%d",&T);while(T--){ memset(dp,-1,sizeof(dp));dp[0]=-1;memset(next,0,sizeof(next));scanf("%d",&n);cin>>a;if(n>21){puts("NO");continue;}int m=a.size()-1;for(int i=0;i<n;i++)next[m+1][i]=451,next[452][i]=451;next[m][a[m]-'a']=m;for(int i=m;i>=0;i--){for(int j=0;j<n;j++)next[i][j]=next[i+1][j];next[i][a[i]-'a']=i;}if(DP((1<<n)-1)==451)puts("NO");else puts("YES");}return 0;} View Code

轉(zhuǎn)載于:https://www.cnblogs.com/lher/p/7565248.html

總結(jié)

以上是生活随笔為你收集整理的20170908校内训练的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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