UVA这题我总是WA，在这里就AC了。不知道为什么……
附程序：

#include<stdio.h>
const long maxn=10000;
char ch,s[maxn+5];
long l,n,m,sz[maxn+5],tree[maxn+5],leaf[maxn+5];

long run(long x){
	long tot,p,i;
	tot=0;p=tree[x];
	for (i=x;i>0;i--){
		if (tree[i]==p){
			tot+=sz[i];p=p/2;
		}
	}
	return tot;
}

int main()
{
	long te,i,j,p,mark,bj;
	while(scanf("%ld",&n)!=EOF)
	{
		scanf("%c",&ch);while (ch!='(') scanf("%c",&ch);
		te=1;l=0;
		while (te>0){
			scanf("%c",&ch);
			if (ch>='0'&&ch<='9'||ch=='('||ch==')'||ch=='-'){
				l++;s[l]=ch;
				if (ch=='(') te++;
				else if (ch==')') te--;
			}
		}
		p=1;i=1;m=0;
		while (p>0&&i<=l){
			if (s[i]>='0'&&s[i]<='9'||s[i]=='-'){
				te=0;mark=0;
				if (s[i]=='-'){
					i++;mark=1;
				}
				while (s[i]>='0'&&s[i]<='9'){
					te=te*10+s[i]-'0';i++;
				}
				m++;sz[m]=te;
				if (mark) sz[m]=-sz[m];
				tree[m]=p;
				if (i+3<=l&&s[i]=='('&&s[i+1]==')'&&s[i+2]=='('&&s[i+3]==')') leaf[m]=1;
				else leaf[m]=0;
			}else{
				if (s[i]=='('){
					i++;p=p*2;bj=1;
					for (j=1;j<=m&&bj;j++){
						if (tree[j]==p) bj=0;
					}
					if (!bj) p++;
				}else{
					p=p/2;i++;
				}
			}
		}
		if (m==0) printf("no\n");
		else{
			bj=1;
			for (i=m;i>0&&bj;i--){
				if (leaf[i]&&run(i)==n) bj=0;
			}
			if (!bj) printf("yes\n");
			else printf("no\n");
		}
	}
	return 0;
}

• Re:uva的题目比较重基本功吧 (1815) pyh119 2008-11-29 12:49:03
  • Re:uva的题目比较重基本功吧 (1954) snowbirds 2009-05-14 18:34:05