[ACM] POJ3295解题报告

173 Replies

这是所谓的二叉树么.. 算法很简单, 只是因为第一次用这种结构体封装, 还是试了很多次才摸索出来的.. 很好用诶! 记一下

细节.. 地址和变量不要搞混了.. fw?fw->v():false 我写成了fw->v()? 错了好久

[cpp]#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Orz {
Orz *fw,*fx;
bool (*f)(bool w,bool x);
bool v() {
return (*f)(fw?fw->v():false,fx?fx->v():false);
};

bool p[5];
char sb[]={‘K’,’A’,’C’,’E’,’N’,’p’,’q’,’r’,’s’,’t’};
char input[201];
int count;

bool fK(bool w,bool x) { return w&x; }
bool fA(bool w,bool x) { return w|x; }
bool fC(bool w,bool x) { return !(w&&!x); }
bool fE(bool w,bool x) { return !(w^x); }
bool fN(bool w,bool x) { return !w; }
bool fp(bool w,bool x) { return p[0]; }
bool fq(bool w,bool x) { return p[1]; }
bool fr(bool w,bool x) { return p[2]; }
bool fs(bool w,bool x) { return p[3]; }
bool ft(bool w,bool x) { return p[4]; }

bool (*f[])(bool w,bool x)={fK,fA,fC,fE,fN,fp,fq,fr,fs,ft};

Orz *proc() {
char a=input[count++];
Orz *node=(Orz *)malloc(sizeof(Orz));
node->fw=node->fx=NULL;

int type;
for(type=0;sb[type]!=a;type++);
node->f=f[type];

if(type<=4)
node->fw=proc();
if(type<4)
node->fx=proc();
return node;

}

int pow2(int n) {
int r=1;
for(int i=0;i<n;i++)
r*=2;
return r;
}

int main() {
while(1) {
gets(input);
if(input[0]==’0′)
break;
count=0;
Orz *bigBang=proc();

short tester;
for(tester=0x0000;tester<=0x001f;tester++) {
for(int i=0;i<5;i++)
p[i]=tester/pow2(i)%2;
if(bigBang->v()!=true)
break;
}

if(tester==0x0020)
printf("tautology\n");
else
printf("not\n");
}

return 0;
}
[/cpp]

173 thoughts on “[ACM] POJ3295解题报告”

Leave a Reply

Your email address will not be published. Required fields are marked *