poj3295Tautology

这几天补一补poj之前落下的题吧
枚举
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<cmath>
  7 using namespace std;
  8 char s[101],ko[510];
  9 int f[10],ta[110],ff[10],p[10];
 10 int main()
 11 {
 12     int i,j,k;
 13     ko['p'] = 1;
 14     ko['q'] = 2;
 15     ko['r'] = 3;
 16     ko['s'] = 4;
 17     ko['t'] = 5;
 18     while(gets(s)!=NULL)
 19     {
 20         if(s[0]=='0')
 21         break;
 22         int flag = 0,g=0,e=0;
 23         memset(ff,0,sizeof(ff));
 24         k = strlen(s);
 25         for(i = 0 ; i < k  ;i++)
 26         {
 27             if(ko[s[i]]&&!ff[ko[s[i]]])
 28             {
 29                 ff[ko[s[i]]] = 1;
 30                 p[e++] = ko[s[i]];
 31             }
 32         }
 33         for(i = 0 ; i  < (1<<e) ; i++)
 34         {
 35             memset(f,0,sizeof(f));g=0;
 36             for(j = 0 ; j < e ; j++)
 37             {
 38                 if(i&(1<<j))
 39                 {
 40                     f[p[j]] = 1;
 41                 }
 42             }
 43             for(j = k-1; j>=0 ; j--)
 44             {
 45                 if(s[j]>='A'&&s[j]<='Z')
 46                 {
 47                     if(s[j]=='K')
 48                     {
 49                         if(ta[g]==1&&ta[g-1]==1)
 50                         ta[g-1] = 1;
 51                         else
 52                         ta[g-1] = 0;
 53                         g--;
 54                     }
 55                     else if(s[j]=='N')
 56                     {
 57                         if(ta[g])
 58                         ta[g] = 0;
 59                         else ta[g] = 1;
 60                     }
 61                     else if(s[j]=='A')
 62                     {
 63                         if(ta[g]==0&&ta[g-1]==0)
 64                         ta[g-1] = 0;
 65                         else
 66                         ta[g-1] = 1;
 67                         g--;
 68                     }
 69                     else if(s[j]=='C')
 70                     {
 71                         if(ta[g]==1&&ta[g-1]==0)
 72                         ta[g-1] = 0;
 73                         else ta[g-1] = 1;
 74                         g--;
 75                     }
 76                     else
 77                     {
 78                         if(ta[g]==ta[g-1])
 79                         ta[g-1] = 1;
 80                         else
 81                         ta[g-1] = 0;
 82                         g--;
 83                     }
 84                 }
 85                 else
 86                 {
 87                     ta[++g] = f[ko[s[j]]];
 88                 }
 89             }
 90             if(!ta[g])
 91             {
 92                 flag = 1;
 93                 break;
 94             }
 95         }
 96         if(!flag)
 97         puts("tautology");
 98         else
 99         puts("not");
100     }
101     return 0;
102 }
View Code