[ACM] POJ3295解题报告

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

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

#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;
}

2 thoughts on “[ACM] POJ3295解题报告

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.