http://poj.org/problem?id=3295
这几天补一补poj之前落下的题吧
枚举
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
char s[],ko[];
int f[],ta[],ff[],p[];
int main()
{
int i,j,k;
ko['p'] = ;
ko['q'] = ;
ko['r'] = ;
ko['s'] = ;
ko['t'] = ;
while(gets(s)!=NULL)
{
if(s[]=='')
break;
int flag = ,g=,e=;
memset(ff,,sizeof(ff));
k = strlen(s);
for(i = ; i < k ;i++)
{
if(ko[s[i]]&&!ff[ko[s[i]]])
{
ff[ko[s[i]]] = ;
p[e++] = ko[s[i]];
}
}
for(i = ; i < (<<e) ; i++)
{
memset(f,,sizeof(f));g=;
for(j = ; j < e ; j++)
{
if(i&(<<j))
{
f[p[j]] = ;
}
}
for(j = k-; j>= ; j--)
{
if(s[j]>='A'&&s[j]<='Z')
{
if(s[j]=='K')
{
if(ta[g]==&&ta[g-]==)
ta[g-] = ;
else
ta[g-] = ;
g--;
}
else if(s[j]=='N')
{
if(ta[g])
ta[g] = ;
else ta[g] = ;
}
else if(s[j]=='A')
{
if(ta[g]==&&ta[g-]==)
ta[g-] = ;
else
ta[g-] = ;
g--;
}
else if(s[j]=='C')
{
if(ta[g]==&&ta[g-]==)
ta[g-] = ;
else ta[g-] = ;
g--;
}
else
{
if(ta[g]==ta[g-])
ta[g-] = ;
else
ta[g-] = ;
g--;
}
}
else
{
ta[++g] = f[ko[s[j]]];
}
}
if(!ta[g])
{
flag = ;
break;
}
}
if(!flag)
puts("tautology");
else
puts("not");
}
return ;
}