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:这题也可以爆搜的

Posted by wangyiling at 2016-10-03 22:28:56 on Problem 2718
In Reply To:Re:这题也可以爆搜的 Posted by:vjudge110 at 2016-03-05 23:00:52
你们爆搜水过 我10!的复杂度爆搜竟然超时。。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int minn=999999999;
int m;
char a[11]={0};
char perm1[11]={0},perm2[11]={0};
	
int powa(int i,int j)
{
	int powar=i;
	if(j>0)
	{
		for(int k=1;k<=j-1;k++)
		{
			powar*=i;
		}
		return powar;
	}
	else if(j==0)
	{
		powar=1;
		return powar;
	}
}

int sum(char perm[])
{
	int len=strlen(perm);
	int num=0;
	int jlen=len;
		while(jlen>=1)
		{
			for(int i=0;i<len;i++)
			{
				int t=jlen-1;
				num+=(perm[i]-'0')*powa(10,t);
				jlen--;
			}
			
		}
	return num;
}

int main()
{
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	scanf("%d\n",&m);
	char ch;
	for(int i=0;i<m;i++)
	{
		minn=99999999;
		int k;
		int tag=0;
		while((ch=getchar())!='\n')
		{
			if(ch!=' ')
			{
			a[tag]=ch;
			tag++;
			}
		}
		int len=strlen(a);
		do
		{
			int flag=0;
			if(len%2==1)
			{
				for(k=0;k<len/2+1;k++)
				{
					perm1[k]=a[k];
				}
				for(int j=k;j<len;j++)
				{
					perm2[flag]=a[j];
					flag++;
				}
				if(perm1[0]!='0' && perm2[0]!='0')
				{
					int tag1=sum(perm1);
					int tag2=sum(perm2);
					int del=abs(tag1-tag2);
					if(minn>del) 
					{
						minn=del;
					}
				}
			}
			else if(len%2==0)
			{
				for(k=0;k<len/2;k++)
				{
					perm1[k]=a[k];
				}
				for(int j=k;j<len;j++)
				{
					perm2[flag]=a[j];
					flag++;
				}
				if(perm1[0]!='0' && perm2[0]!='0' && perm2[0]-perm1[0]==1)
				{
					int tag1=sum(perm1);
					int tag2=sum(perm2);
					int del=abs(tag1-tag2);
					if(minn>del) 
					{
						minn=del;
					}
				}
			}
		}while(next_permutation(a,a+len));
		printf("%d\n",minn);
	}
		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