Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哎,还枉费我想了各种复杂的情况...贴代码出来,哪位好心的大大看看这在C++和G++下有什么不同吧

Posted by dynamic at 2005-11-15 08:03:49
In Reply To:!!!!!!!!!!!!!!!!真的g++就过了...汗啊,到底是什么地方不同?__int64的问题? Posted by:dynamic at 2005-11-15 08:02:24
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <utility>
#include <iostream>
#include <sstream>

typedef __int64 integer;

int n,m;
int left[50],right[50],flag[50];
char s[3000],ss[3000];
integer v[3000],maxv,sum,a[51][51];

void dfs(int cur,int d)
{
	if (left[cur]>=0) dfs(left[cur],d+1);
	if (right[cur]>=0) dfs(right[cur],d+1);
	sum+=v[cur]*d;
}

integer dp(int s,int t)
{
	int i;
	integer p=0,temp;
	if (a[s][t]>=0) return a[s][t];
	if (s>t){
		a[s][t]=0;
		return 0;
	}
	for(i=s;i<=t;i++) p+=v[i];
	a[s][t]=maxv*3000;
	for(i=s;i<=t;i++){
		temp=dp(s,i-1)+dp(i+1,t)+p;
		if (temp<a[s][t]) a[s][t]=temp;
	}
	return a[s][t];
}

bool construct(int s,int t)
{
	int i,j,k;
	integer p=0,temp;
	if (s>t) return 1;
	for(i=s;i<=t;i++) p+=v[i];
	j=0;
	for(i=s;i<=t;i++){
		temp=dp(s,i-1)+dp(i+1,t)+p;
		if (temp==a[s][t]){
			k=i;
			j++;
		}
	}
	if (j>=2) return 0;
	return construct(s,k-1) && construct(k+1,t);
}

bool solve()
{
	int i,start,l=strlen(s);
	bool zero;
	for(i=0;i<l;i++){
		if (s[i]!='\t' && s[i]!=' ' && !isdigit(s[i])) return 0;
	}
	m=0;
	start=0;
	integer temp=0;
	zero=0;
	for(i=0;i<=l;i++){
		if (isdigit(s[i])){
			if (!start && s[i]=='0'){
				if (s[i+1]=='0') return 0;
				zero=1;
			}
			start=1;
			temp=temp*10+s[i]-'0';
			if (temp>maxv) return 0;
		}else if (start){
			v[m++]=temp;
			if (zero==1 && temp!=0) return 0;
			temp=0;
			start=0;
			zero=0;
		}
	}
	if (m!=n) return 0;
	sum=0;
	memset(flag,0,sizeof(flag));
	for(i=0;i<n;i++){
		if (left[i]>=0) flag[left[i]]=1;
		if (right[i]>=0) flag[right[i]]=1;
	}
	for(i=0;i<n;i++) if (!flag[i]) break;
	dfs(i,1);
	if (sum==0) return 0;
	memset(a,0xff,sizeof(a));
	if (sum!=dp(0,n-1)) return 0;
	if (!construct(0,n-1)) return 0;
	return 1;
}

int main()
{
//	freopen("test.txt","r",stdin);

	int i;
	maxv=1;
	for(i=0;i<15;i++) maxv*=10;
	while(1){
		gets(s);
		if (strcmp(s,"#End#")==0) break;
		if (strcmp(s,"#Start Input#")!=0) continue;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d%d",&left[i],&right[i]);
			left[i]--;
			right[i]--;
		}
		while(1){
			gets(s);
			if (strcmp(s,"#End Input#")==0) break;
		}
		while(1){
			gets(s);
			if (strcmp(s,"#Start Programmer's Output#")==0) break;
		}
		gets(s);
		if (strcmp(s,"#End Programmer's Output#")==0){
			printf("Wrong\n");
			continue;
		}
		gets(ss);
		if (strcmp(ss,"#End Programmer's Output#")==0){
			if (solve()) printf("Accepted\n");
			else printf("Wrong\n");
		}else{
			printf("Wrong\n");
		}
		while(1){
			if (strcmp(ss,"#End Programmer's Output#")==0) break;
			gets(ss);
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator