#2305. 「NOI2017」游戲

題目描述

小 L 計劃進行?nnn?場游戲，每場游戲使用一張地圖，小 L 會選擇一輛車在該地圖上完成游戲。

小 L 的賽車有三輛，分別用大寫字母?AAA、BBB、CCC?表示。地圖一共有四種，分別用小寫字母?xxx、aaa、bbb、ccc?表示。

其中，賽車?AAA?不適合在地圖?aaa?上使用，賽車?BBB?不適合在地圖?bbb?上使用，賽車?CCC?不適合在地圖?ccc?上使用，而地圖?xxx?則適合所有賽車參加。

適合所有賽車參加的地圖并不多見，最多只會有?ddd?張。

nnn?場游戲的地圖可以用一個小寫字母組成的字符串描述。例如：$\mathrm{S=xaabxcbc?表示小L計劃進行?888?場游戲，其中第?111?場和第?555?場的地圖類型是?xxx，適合所有賽車，第?222場和第?333場的地圖是?aaa，不適合賽車?AAA，第?444?場和第?777?場的地圖是?bbb，不適合賽車?BBB，第?666?場和第?888?場的地圖是?ccc，不適合賽車?CCC。}$

小 L 對游戲有一些特殊的要求，這些要求可以用四元組?(i,hi,j,hj) (i, h_i, j, h_j)(i,h?i??,j,h?j??)?來描述，表示若在第?iii?場使用型號為?hih_ih?i???的車子，則第?jjj?場游戲要使用型號為?hjh_jh?j???的車子。

你能幫小 L 選擇每場游戲使用的賽車嗎？如果有多種方案，輸出任意一種方案。

如果無解，輸出?-1。

輸入格式

輸入第一行包含兩個非負整數?nnn,?ddd。

輸入第二行為一個字符串?SSS。

nnn,?ddd,?SSS?的含義見題目描述，其中?SSS?包含?nnn?個字符，且其中恰好?ddd?個為小寫字母?xxx。

輸入第三行為一個正整數?mmm?，表示有?mmm?條用車規則。

接下來?mmm?行，每行包含一個四元組?i,hi,j,hji,h_i,j,h_ji,h?i??,j,h?j???，其中?i,ji,ji,j?為整數，hi,hjh_i,h_jh?i??,h?j???為字符?AAA?、BBB?或?CCC，含義見題目描述。

輸出格式

輸出一行。

若無解輸出?-1。

樣例

樣例輸入

3 1 xcc 1 1 A 2 B

樣例輸出

ABA

小?LLL?計劃進行?333?場游戲，其中第?111?場的地圖類型是?xxx，適合所有賽車，第?222?場和第?333?場的地圖是?ccc，不適合賽車?CCC。

小?LLL?希望：若第?111?場游戲使用賽車?AAA，則第?222?場游戲使用賽車?BBB。

那么為這?333?場游戲分別安排賽車?AAA、BBB、AAA?可以滿足所有條件。

若依次為?333?場游戲安排賽車為?BBBBBBBBB?或?BAABAABAA?時，也可以滿足所有條件，也被視為正確答案。

但依次安排賽車為?AABAABAAB?或?ABCABCABC?時，因為不能滿足所有條件，所以不被視為正確答案。

數據范圍與提示

?

?

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #define maxn 50010 using namespace std; char s[maxn],ch1[5],ch2[5]; int n,d,q,w[maxn]; bool flag,mark[maxn]; struct node{int a,b,c,d;bool operator < (const node &k)const{return a<k.a;} }op[maxn]; int findl(int x){int l=1,r=q,res=0;while(l<=r){int mid=(l+r)>>1;if(op[mid].a>=x)res=mid,r=mid-1;else l=mid+1;}return res; } int findr(int x){int l=1,r=q,res=0;while(l<=r){int mid=(l+r)>>1;if(op[mid].a<=x)res=mid,l=mid+1;else r=mid-1;}return res; } bool check(){for(int i=1;i<=n;i++){if(s[i]=='a'&&w[i]==0)return 0;if(s[i]=='b'&&w[i]==1)return 0;if(s[i]=='c'&&w[i]==2)return 0;if(mark[i]){int l=findl(i),r=findr(i);for(int j=l;j<=r;j++){if(w[i]!=op[j].b)continue;if(w[op[j].c]!=op[j].d)return 0;}}}return 1; } void dfs(int pos){if(flag)return;if(pos==n+1){flag=check();if(flag){for(int i=1;i<=n;i++){if(w[i]==0)putchar('A');else if(w[i]==1)putchar('B');else putchar('C');}exit(0);}return;}if(flag)return;for(int i=0;i<3;i++){if(flag)return;w[pos]=i;dfs(pos+1);} } void work1(){scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%d%s%d%s",&op[i].a,&ch1,&op[i].c,&ch2);mark[op[i].a]=1;op[i].b=ch1[0]-'A';op[i].d=ch2[0]-'A';}sort(op+1,op+q+1);dfs(1); } int main(){scanf("%d%d",&n,&d);scanf("%s",s+1);if(n<=10){work1();return 0;}else {puts("-1");return 0;} } 35分 暴力

?

轉載于:https://www.cnblogs.com/thmyl/p/8978674.html

總結

以上是生活随笔為你收集整理的loj #2305. 「NOI2017」游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。