POJ3295 Tautology 枚举+DFS

　　水题本质。数据量小，直接枚举判断即可。但要注意在搜索的时候，如果进行逻辑运算&&和||时，存在短路特性的！比如，dfs(cur+1)||dfs(cur+2),如果dfs(cur+1)==ture，那么dfs(cur+2)就不会访问了，所以导致cur的下标访问出错，那么我们在写这种表达式的时候，把dfs分别赋值然后再去进行逻辑判断是一种好习惯，可以减少不必要的错误！我开始这里没有注意好，wa了！然后还提一下，C++是从逻辑判断符的右边开始判断的，而G++是从左边开始的，也就是这题有些人C++和G++不能同时通过的原因。

 1 //STATUS:C++_AC_0MS_168KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 #include<map>
13 using namespace std;
14 #define LL long long
15 #define pii pair<int,int>
16 #define Max(a,b) ((a)>(b)?(a):(b))
17 #define Min(a,b) ((a)<(b)?(a):(b))
18 #define mem(a,b) memset(a,b,sizeof(a))
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int MAX=210,INF=0x3f3f3f3f;
22 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;
23 
24 int vis[MAX];
25 char str[MAX],s[MAX],w[MAX];
26 int n;
27 
28 int dfs(int cur)
29 {
30     if(vis[cur])return dfs(cur+1);
31     vis[cur]=1;
32     if(s[cur]<2)return s[cur];
33     if(s[cur]=='N')return !dfs(cur+1);
34     int a,b;
35     a=dfs(cur+1);b=dfs(cur+2);
36     if(s[cur]=='K')return a&&b;
37     if(s[cur]=='A')return a||b;
38     if(s[cur]=='C')return !a||b;
39     return a==b;
40 }
41 
42 int main()
43 {
44  //   freopen("in.txt","r",stdin);
45     w['p']=0,w['q']=1,w['r']=2,w['s']=3,w['t']=4;
46     int i,j,len,ok;
47     n=(1<<5);
48     while(~scanf("%s",str) && str[0]!='0')
49     {
50         len=strlen(str);
51         ok=1;
52         for(i=0;i<n;i++){
53             strcpy(s,str);
54             mem(vis,0);
55             for(j=0;j<len;j++)
56                 if(s[j]>='a' && s[j]<='z')s[j]=(i&(1<<w[s[j]]))?1:0;
57             if(!dfs(0)){ok=0;break;}
58         }
59         printf("%s\n",ok?"tautology":"not");
60     }
61     return 0;
62 }