link:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=353#problem/B

唉,搜索果乃神器也。。吾等一点都不懂啊,就只能瞎碰了,这题就是对几个数进行全排列,然后找出符合条件的就好了~~下面是两段代码,一段是用搜索做的,用了0.781s,还有一个用全排列做的,用时0.500s,都是好长啊,求大牛优化~~
code:
先上搜索:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int visit[20];/*判断是否遍历过*/
int num[20];/*排列之后的数*/
int a[20];/*存储输入的数*/
int n,x,k;
int sum[362880];
int flag,j;

int change(int b[])
{
    int i;
    int s=0;
    for(i=0;i<n;i++)
        s=s*10+b[i];
    return s;
}

void dfs_full_permutation(int l)
{
    int i;
    if(l==n)
    {
		if(num[0]!=0)
			sum[j++]=change(num);
		return;
    }
    for(i=0;i<n;i++)/*枚举所有的数*/
    {
        if(visit[i]==0)/*如果a[i]还没有使用*/
        {
            visit[i]=1;/*标记已经使用*/
            num[l]=a[i];/*放在l位上*/
            dfs_full_permutation(l+1);
            visit[i]=0;/*回溯清标记*/
        }
    }
}

int main()
{
    int m,i,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
	j=0;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
	sort(a,a+n);
	memset(visit,0,sizeof(visit));
        dfs_full_permutation(0);//要先搜出来再操作,否则会超时
        while(m--)
        {
			flag=0;
                        scanf("%d%d",&x,&k);
			for(i=0;i<j;i++)
			{
				if((sum[i]+x)%k==0)
				{
					printf("%d\n",sum[i]);
					flag=1;
					break;
				}
			}
			if(flag==0)
				printf("None\n");
        }

    }
    return 0;
}

全排列:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int a[10];
int sum[362880];
int n;

int change()
{
    int i,s=0;
    for(i=0;i<n;i++)
        s=s*10+a[i];
    return s;
}

int main()
{
    int m,x,k,i,t,flag;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        t=0;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        if(a[0]!=0)
            sum[t++]=change();
        while(next_permutation(a,a+n))
            if(a[0]!=0)
                sum[t++]=change();
        while(m--)
        {
            scanf("%d%d",&x,&k);
            flag=0;
            for(i=0;i<t;i++)
                if((sum[i]+x)%k==0)
                {
                     printf("%d\n",sum[i]);
                     flag=1;
                     break;
                }
            if(flag==0)
                printf("None\n");
        }

    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation