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

Re:大大来看看吧 wa的好纠结

Posted by 104GOGO at 2011-07-26 13:44:30 on Problem 2138
In Reply To:大大来看看吧 wa的好纠结 Posted by:niuzheng168 at 2009-09-16 16:37:03
> #include <iostream>//这个去掉
> #include <queue>
> #include <algorithm>//这个去掉
> #include <string.h>//加上stdio.h和stdlib.h
> using namespace std;
> 
> char str[90][1005];//str[1005][1005];
> int matrix[1005][1005];
> int visit[1005];
> 
> int cmp(const void *a,const void *b)
> {
> 	return strlen((char *)a)-strlen((char *)b);
> }
> 
> 
> int judge(char *a,char *b)
> {
> 	int len_a=strlen(a);
> 	int len_b=strlen(b);
> 	int i,j,count=0;
> 	if(len_b-len_a==1)
> 	{
> 		for(i=0,j=0;a[i]||b[j];)
> 		{
> 			if(a[i]==b[j])
> 			{
> 				i++;
> 				j++;
> 			}
> 			else
> 			{
> 				count++;
> 				j++;
> 			}
> 			if(count>1)
> 				return 0;
> 		}
> 		if(i==len_a&&j==len_b)
> 			return 1;
> 		else
> 			return 0;
> 	}
> 	else
> 		return 0;
> }
> 
> 
> void bfs(int x,int n)
> {
> 	queue<int> q;
> 	int temp,t=0,s=0;
> 	int i,j,max=0,ans=0,len=0;
> 	memset(visit,0,sizeof(visit));
> 	len=strlen(str[0]);
> 	temp=0;
> 	q.push(temp);
> 	while(!q.empty())
> 	{
> 		t=q.front();
> 		q.pop();
> 		if(!visit[t])
> 		{
> 			for(i=0;i<=n;i++)
> 			{
> 				if(matrix[t][i]!=0)
> 				{
> 					s=i;
> 					q.push(s);
> 					len=strlen(str[s]);
> 				}
> 				if(len>=max)
> 				{
> 					ans=s;
> 					max=len;
> 				}
> 			}
> 			visit[t]=1;
> 		}
> 	}
> 	printf("%s",str[ans]);//printf("%s\n",str[ans]);
> }
> 
> int main()
> {
> 	int n,i,j;
> 	scanf("%d %s",&n,str[0]);
> 	for(i=1;i<=n;i++)
> 		scanf("%s",str[i]);
> 	qsort(str+1,n,sizeof(str[0]),cmp);
> 	memset(matrix,0,sizeof(matrix));
> 	for(i=0;i<n;i++)
> 		for(j=i+1;j<=n;j++)
> 				matrix[i][j]=judge(str[i],str[j]);
> 
> 
> 	bfs(0,n);
> 	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