hdu4294 Multiple 数学结论 bfs

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
#define mod 1000000007
using namespace std;

int n,k,cnt,num[2],len[50010],pre[50010],v[50010];
string s,ans;

int bfs()
{
    queue<int> q;
    int now,tmp;
    memset(len,0,sizeof len);
    for(int i=0;i<cnt;i++)
    {
        if(!num[i]||len[num[i]%n]) continue;//不能0打头
        tmp=num[i]%n;
        len[tmp]=1;//串长度
        pre[tmp]=-1;//记录数字位置顺序
        v[tmp]=num[i];//记录该位置数字的值
        q.push(tmp);
    }
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(!now) return 1;
        if(ans.size() && len[now]>ans.size()) return 0;
        for(int i=0;i<cnt;i++)
        {
            tmp=(now*k+num[i])%n;
            if(!len[tmp])
            {
                len[tmp]=len[now]+1;//串长度
                pre[tmp]=now;//记录数字位置顺序
                v[tmp]=num[i];//记录该位置数字的值
                q.push(tmp);
            }

        }
    }
    return 0;
}

void get(int a)
{
    if(pre[a]!=-1) get(pre[a]);
    s+=(char)(v[a]+'0');
}

bool cmp(string a,string b)
{
    if(b.size()==0||a.size()<b.size()) return 1;
    if(a.size()>b.size()) return 0;
    return a<b;
}

int main()
{
    int i;
    while(~scanf("%d%d",&n,&k))
    {
        int flag=0;
        ans="";
        for(i=1;i<k;i++)
        {
            num[0]=i;cnt=1;
            if(bfs())
            {
                flag=1;
                s="";
                get(0);
                if(cmp(s,ans))
                    ans=s;
            }
        }
        if(!flag)
        {
            for(i=1;i<k;i++)
            {
                for(int j=0;j<i;j++)
                {
                    num[0]=j;num[1]=i;cnt=2;
                    if(bfs())
                    {
                        flag=1;
                        s="";
                        get(0);
                        if(cmp(s,ans))
                            ans=s;
                    }
                }

            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

hdu4294 Multiple 数学结论 bfs,布布扣,bubuko.com

hdu4294 Multiple 数学结论 bfs

原文：http://blog.csdn.net/u011032846/article/details/34818577