UVA 1569　Multiple

题意：

　　给定m个1位数字，要求用这些数字组成n的倍数的最小数字，如果无法组成就输出0

分析：

　　BFS，由于n最大5000，余数最多5000，利用余数去判重，并记录下路径即可

代码：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

const int maxn=5010;

int n,m,vis[maxn],pre[maxn],ans[maxn],q[maxn];

vector<int>s;

void print(int u)

{

    if(u==-1)

        return;

    print(pre[u]);

    printf("%d",ans[u]);

}

int main()

{

    while(~scanf("%d",&n))

    {

        scanf("%d",&m);

        s.clear();

        memset(vis,0,sizeof(vis));

        int head=0,rear=0;

        int num;

        while(m--)

        {

            scanf("%d",&num);

            s.push_back(num);

        }

        sort(s.begin(),s.end());

        if(n==0)

        {

            printf("0\n");

            continue;

        }

        int i;

        for(i=0;i<s.size();i++)

        {

            if(s[i]==0)

                continue;

            int tmp=s[i]%n;

            ans[rear]=s[i];

            pre[rear]=-1;

            q[rear++]=tmp;

            vis[tmp]=1;

        }

        int flag=1;

        while(head<rear)

        {

            int u=q[head];

            if(u==0)

            {

                print(head);

                flag=0;

                printf("\n");

                break;

            }

            for(i=0;i<s.size();i++)

            {

                int temp=((u*10+s[i])%n);

                if(vis[temp]==0)

                {

                    vis[temp]=1;

                    q[rear]=temp;

                    ans[rear]=s[i];

                    pre[rear++]=head;

                }

            }

            head++;

        }

        if(flag)

            printf("0\n");

    }

    return 0;

}

巴特西

UVA 1569　Multiple

最新文章

热门文章

巴特西

UVA 1569 Multiple

最新文章

热门文章

UVA 1569　Multiple