BFS

HDU 1664 Different Digits

稍微有点不一样 这次衡量的第一标准是位数的多少 第二标准才是数的大小
这里必须有一个 数论的 知识 不然不好写(I hate number theroy ......
对于任意的整数n,必然存在一个由不多于两个的数来组成的一个倍数。(之前写过数位BFS的应该可以理解
因为a,aa,aaa……取n+1个,则必有两个模n余数相同,相减即得n的倍数m。而m只由a、0组成。(这可以说是最糟的情况
所以只要先枚举所有的 1-9 的数 如果不存在 再枚举两个数的情况 (一直很奇怪网上的题解 0-9 不是有 45种情况么…………

还有 。。。沃特么也是SB 被自己坑到了 我还以为必须是他给的数 的位数作为范围 因为样例就是这样的…… 结果WA了好几发

AC Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>

using namespace std;
const int maxn=65540;
const int inf=0x3f3f3f3f;
int n,k,num[11],a[5];
char ch[3];
bool vis[maxn],flag[11];
string curans,ans;

struct node
{
    char ch;
    int pre,mod;
}que[maxn*10];

void getstr(int x)
{
    if(que[x].pre!=-1)
        getstr(que[x].pre);
    curans+=que[x].ch;
}

bool bfs(int kk)
{
    memset(vis,false,sizeof vis);
    int l=1,r=1;
    for(int i=0;i<kk;i++) if(a[i])
    {
        que[r].pre=-1;
        vis[que[r].mod=a[i]%n]=true;
        que[r].ch=a[i]+'0';
        r++;
    }
    while(l<r)
    {
        for(int i=0;i<kk;i++)
        {
            int tmp=que[r].mod=(que[l].mod*10+a[i])%n;
            if(!vis[tmp])
            {
                vis[tmp]=true;
                que[r].pre=l;
                que[r].ch=a[i]+'0';
                if(tmp==0)
                {
                    getstr(r);
                    return true;
                }
                r++;
            }
        }
        l++;
    }
    return false;
}

bool cmp(const string& a,const string &b)
{
    if(a.size()==b.size()) return a<b;
    return a.size()<b.size();
}

int main()
{
    while(scanf("%d",&n),n)
    {
        if(n<=11)//11之前直接输出    可以减少bfs的判断
        {
            printf("%d\n",n);
            continue;
        }
        ans="";
        bool wokao=false;
        for(int i=1;i<10;i++)
        {
            a[0]=i;
            curans="";
            if(bfs(1))
                if(!wokao||cmp(curans,ans))//大小关系是未知的   必须加以判断
                {
                    wokao=true;
                    ans=curans;
                }
        }
        if(wokao)
            cout<<ans<<endl;
        else
        {
            for(int i=0;i<10;i++)
                for(int j=i+1;j<10;j++)
                {
                    a[0]=i,a[1]=j;
                    curans="";
                    if(bfs(2))
                        if(!wokao||cmp(curans,ans))
                        {
                            wokao=true;
                            ans=curans;
                        }
                }
            cout<<ans<<endl;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注