Description
Solution
首先我們發(fā)現(xiàn)一個(gè)位置如果不是 \('x'\),那么就只有兩種選擇
而 \('x'\) 的個(gè)數(shù)小于等于 \(8\),直接枚舉是哪個(gè)就好了
然后就是 \(2-sat\) 連邊:
設(shè)一個(gè)點(diǎn) \(i\) 的對(duì)立點(diǎn)為 \(i'\)
如果 \(a[i]=h[i]\),那么就可以直接忽略這個(gè)限制
如果 \(a[j]=h[j]\),那么 \(i\) 就不能選 \(a[i]\),為了保證這個(gè)限制直接連邊 \((i,i')\) 就好了
如果上述兩種情況都不是,那么直接連 \((i,j),(j',i')\) 就好了
值得注意的是:
\(2-sat\) 如果沒有字典序最小的要求,可以直接 \(tarjan\) \(O(n)\) 的判斷是否合法
方法就是判斷對(duì)立點(diǎn)是否在同一強(qiáng)連通分量里即可
輸出方案(拓?fù)渑判蜇澬?:
正向貪心會(huì)有后效性
把縮點(diǎn)之后的 \(DAG\) 的邊反向,發(fā)現(xiàn)一個(gè)點(diǎn) \(i\) 選了之后,拓?fù)湫蛟?\(i'\) 之后的點(diǎn)就都不可以選了
每一次選了 \(i\) 之后,就把 \(i'\) 打上標(biāo)記即可,就不拿有標(biāo)記的點(diǎn)刪邊了
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,D,m,lis[N],fr[N],tr[N];char s[N],a[N],b[N];
int head[N],nxt[N*2],to[N*2],num=1,in[N];
inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
int dfn[N],low[N],DFN=0,st[N],top,sum,be[N];bool inst[N],vis[N],fc[N];
vector<int>v[N],sc[N];vector<int>::iterator it;
inline void Clear(){num=1;DFN=sum=top=0;for(register int i=0;i<N;i++)vector<int>().swap(sc[i]),head[i]=low[i]=dfn[i]=inst[i]=0;
}
inline int id(int i,char j){if(s[i]=='a'){if(j=='b')return i;return i+n;}if(s[i]=='b'){if(j=='a')return i;return i+n;}if(j=='a')return i;return i+n;
}
inline int f(int x){return x>n?x-n:x+n;}
inline void tarjan(int x){low[x]=dfn[x]=++DFN;inst[x]=1;st[++top]=x;for(int i=head[x],u;i;i=nxt[i]){if(!dfn[u=to[i]])tarjan(u),low[x]=min(low[x],low[u]);else if(inst[u])low[x]=min(low[x],dfn[u]);}if(low[x]==dfn[x]){int v;sum++;do{v=st[top--];be[v]=sum;inst[v]=0;sc[sum].push_back(v);}while(top && v!=x);}
}
inline void Cliear(){for(register int i=0;i<N;i++)vector<int>().swap(v[i]),in[i]=vis[i]=fc[i]=0;
}
inline void solve(){Clear();for(int i=1;i<=m;i++){if(s[fr[i]]==a[i])continue;if(s[tr[i]]==b[i])link(id(fr[i],a[i]),f(id(fr[i],a[i])));else{int x=id(fr[i],a[i]),y=id(tr[i],b[i]);link(x,y);link(f(y),f(x));}}for(int i=1,li=n*2;i<=li;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)if(be[i]==be[i+n])return ;Cliear();for(int i=1,li=n*2;i<=li;i++)for(int j=head[i];j;j=nxt[j]){int u=to[j];if(be[u]==be[i])continue;v[be[u]].push_back(be[i]);in[be[i]]++;}queue<int>Q;for(int i=1;i<=sum;i++)if(!in[i])Q.push(i);while(!Q.empty()){int x=Q.front();Q.pop();if(vis[x])continue;fc[x]=1;for(it=sc[x].begin();it!=sc[x].end();++it)vis[be[f(*it)]]=1;for(it=v[x].begin();it!=v[x].end();++it)if(!(--in[*it]))Q.push(*it);}for(int i=1;i<=n;i++){if(fc[be[i]]){if(s[i]=='a')putchar('B');else putchar('A');}else{if(s[i]=='c')putchar('B');else putchar('C');}}exit(0);
}
inline void dfs(int x){if(x==D+1){solve();return ;}s[lis[x]]='a';dfs(x+1);s[lis[x]]='b';dfs(x+1);
}
int main(){freopen("pp.in","r",stdin);freopen("pp.out","w",stdout);scanf("%d%d%s",&n,&D,s+1);for(int i=1,j=0;i<=n;i++)if(s[i]=='x')lis[++j]=i;scanf("%d",&m);char p1[2],p2[2];for(int i=1;i<=m;i++){scanf("%d%s%d%s",&fr[i],p1,&tr[i],p2);a[i]=p1[0]+32;b[i]=p2[0]+32;}dfs(1);puts("-1");return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/Yuzao/p/8591195.html
總結(jié)
以上是生活随笔為你收集整理的bzoj 4945: [Noi2017]游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
