題意：
? ? ? 兩個人玩剪刀石頭布，他們玩了n把，給了你A這n把都出了什么，問你B能否會贏，其中A會限制B某些局數出的要相同，某些局數出的要不同，只要B滿足他的限制，并且沒沒有輸掉任何一把就算贏（沒有輸掉就是平或者贏）。

思路：

? ? ? 首先考慮下，對于每一步，我們知道A出了什么，那么也就知道B在這不可以出什么，比如A在這一步出了1 那么B可以出1,2。對于每一步B都有兩種選擇，并且在步于步之間有一些限制，兩種選擇，一些限制，顯然2sat，把每一次可以出的兩個看成一組，一個是a,一個是~a,對于每一種限制我們只要找出它的矛盾對就行了，矛盾對的建邊遵循 x ,y矛盾則有add(x ,~y) ,add(y ,~x) ,要注意這里面的 x,~x是相對而言，x = ~x^1 同時 x^1 = ~x,建邊的時候別糊涂就行了，總之這個題目應該是2算是sat的簡單題目。

#include<stdio.h> #include<string.h> #include<stack>#define N_node 20000 + 100 #define N_edge 50000 + 500 using namespace std;typedef struct {int to ,next; }STAR;STAR E1[N_edge] ,E2[N_edge]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,cnt; int mark[N_node]; int A[11000][2]; stack<int>st;void add(int a ,int b) {E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;E2[tot].to = a;E2[tot].next = list2[b];list2[b] = tot; }void DFS1(int s) {mark[s] = 1;for(int k = list1[s] ;k ;k = E1[k].next)if(!mark[E1[k].to])DFS1(E1[k].to);st.push(s); }void DFS2(int s) {mark[s] = 1 ,Belong[s] = cnt;for(int k = list2[s] ;k ;k = E2[k].next)if(!mark[E2[k].to])DFS2(E2[k].to); }bool ok(int n) {memset(mark ,0 ,sizeof(mark));while(!st.empty()) st.pop();for(int i = 0 ;i < n * 2 ;i ++)if(!mark[i]) DFS1(i);memset(mark ,0 ,sizeof(mark));cnt = 0;while(!st.empty()){int xin = st.top();st.pop();if(mark[xin]) continue;cnt ++;DFS2(xin);}int mk = 0;for(int i = 0 ;i < n * 2 && !mk ;i += 2)if(Belong[i] == Belong[i^1]) mk = 1;return !mk; }int main () {int t ,n ,m ,i ,a ,b ,c ,cas = 1;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);for(i = 1 ;i <= n ;i ++){scanf("%d" ,&a);A[i][0] = a;A[i][1] = a % 3 + 1;}memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d %d" ,&a ,&b ,&c);int x1 = a * 2 ,x2 = a * 2 + 1;int y1 = b * 2 ,y2 = b * 2 + 1;if(!c && A[a][0] != A[b][0] || c && A[a][0] == A[b][0])add(x1 ,y1^1) ,add(y1 ,x1^1);if(!c && A[a][0] != A[b][1] || c && A[a][0] == A[b][1])add(x1 ,y2^1) ,add(y2 ,x1^1);if(!c && A[a][1] != A[b][0] || c && A[a][1] == A[b][0])add(x2 ,y1^1) ,add(y1 ,x2^1);if(!c && A[a][1] != A[b][1] || c && A[a][1] == A[b][1])add(x2 ,y2^1) ,add(y2 ,x2^1);}printf("Case #%d: " ,cas ++);if(!ok(n)) puts("no");else puts("yes");}return 0; }

總結

以上是生活随笔為你收集整理的hdu4115 2sat 石头剪刀布的全部內容，希望文章能夠幫你解決所遇到的問題。

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