poj 3295 Tautology

2019-04-14 21:57发布

站内文章 / 模拟电子
11513 0 1470
链接：http://poj.org/problem?id=3295
模拟了一下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_N 105 #define inf 0x7fffffff #define LL long long #define ull unsigned long long const LL INF = 9e18; const int mod = 100000000; typedef pairP; char S[MAX_N]; stackope, c; mapmp; int p, q, r, s, t; int len; void init() { mp['p'] = p; mp['q'] = q; mp['r'] = r; mp['s'] = s; mp['t'] = t; } int find(int left, int right) { if(S[left]>='a' && S[left]<='z') return left; int sum; if(S[left] == 'N') sum = 1; else sum = 2; for(int i=left+1;i<=right;i++) { if(S[i]>='a' && S[i]<='z') sum--; else if(S[i]!='N') sum++; if(!sum) return i; } return right; } bool dfs(int left, int right) { if(right == left) { return mp[S[left]]; } if(S[left] == 'N') { return !dfs(left+1, right); } else { if(S[left] <= 'z' && S[left] >= 'a') { return mp[S[left]]; } else if(S[left] == 'K') { int mid = find(left+1, right); return dfs(left+1, mid) & dfs(mid+1, right); } else if(S[left] == 'A') { int mid = find(left+1, right); return dfs(left+1, mid) | dfs(mid+1, right); } else if(S[left] == 'C') { int mid = find(left+1, right); return (!dfs(left+1, mid)) | dfs(mid+1, right); } else if(S[left] == 'E') { int mid = find(left+1, right); return dfs(left+1, mid) == dfs(mid+1, right); } } } bool check() { for(p=0;p<2;p++) { for(q=0;q<2;q++) { for(r=0;r<2;r++) { for(s=0;s<2;s++) { for(t=0;t<2;t++) { init(); if(!dfs(0, len-1)) { return false; } } } } } } return true; } int main() { while(scanf("%s",S)) { if(S[0] == '0') break; len = strlen(S); if(check()) printf("tautology "); else printf("not "); } }
评论区里看到的一个简洁递归： #include #include #include using namespace std; string s;int cur;char a[5]; void Change(char i)//穷举时改变数组用的函数 { for(int j=0;j!=5;j++) a[j]=((i>>j)&00000001); } bool Cal()//递归 { char c=s[cur];bool w,x; cur++; switch(c){ case 'p':return a[0]; case 'q':return a[1]; case 'r':return a[2]; case 's':return a[3]; case 't':return a[4]; case 'N':return !Cal(); case 'K':w=Cal();x=Cal();return (w&&x); case 'A':w=Cal();x=Cal();return (w||x); case 'C':w=Cal();x=Cal();return (w<=x); case 'E':w=Cal();x=Cal();return (w==x); default :return 0; } } int main() { int f; while(1) { cin>>s; if(s=="0") break; f=1; for(char i=0;i!=32;i++) { cur=0;Change(i); if(!Cal()) {f=0;break;} } if(f==1) cout<<"tautology"<

热门文章