首页 > 代码库 > HDU-1664-Different Digits(BFS)

HDU-1664-Different Digits(BFS)

2024-07-14 20:52:56   221人阅读

Problem Description
Given a positive integer n, your task is to find a positive integer m, which is a multiple of n, and that m contains the least number of different digits when represented in decimal. For example, number 1334 contains three different digits 1, 3 and 4.
 

Input
The input consists of no more than 50 test cases. Each test case has only one line, which contains a positive integer n ( 1<=n < 65536). There are no blank lines between cases. A line with a single `0‘ terminates the input.
 

Output
For each test case, you should output one line, which contains m. If there are several possible results, you should output the smallest one. Do not output blank lines between cases.
 

Sample Input
7 
15 
16 
101 
0
 

Sample Output
7
555
16
1111
 

Source
2004 Asia Regional Shanghai 


思路：最多只需要出现两个不同的数字，先尝试一个数字的情况，再搜两个数字的情况。


#include <stdio.h>
#define min(A,B)(A<B?A:B)
#define INF 999999999

struct N{
int len,num;
bool operator<(const struct N &p) const
{
    if(len==p.len) return num<p.num;

    return len<p.len;
}
}sin,tt;

struct S{
int val,last,m,len;
}que[1000000],t;

int i,j;
bool mod[65536];
char ans[100][1000];

void dfs(int idx)
{
    if(que[idx].last!=-1) dfs(que[idx].last);

    ans[i*10+j][que[idx].len]=que[idx].val+'0';
}

int main()
{
    int n,k,temp,id,mnlen;

    while(~scanf("%d",&n) && n)
    {
        sin.len=INF;
        sin.num=INF;

        for(i=1;i<=9;i++)
        {
            for(j=0;j<n;j++) mod[j]=0;
            temp=0;
            for(j=1;;j++)
            {
                temp=(temp*10+i)%n;

                if(!temp)
                {
                    tt.len=j;
                    tt.num=i;
                    sin=min(sin,tt);
                }

                if(!mod[temp]) mod[temp]=1;
                else break;
            }
        }

        if(sin.len<INF)
        {
            for(i=0;i<sin.len;i++) printf("%d",sin.num);
            puts("");

            continue;
        }

        if(n<100)
        {
            printf("%d\n",n);

            continue;
        }

        mnlen=INF;

        for(i=1;i<=9;i++)
        {
            for(j=0;j<=9;j++)
            {
                if(i==j) continue;

                for(k=0;k<n;k++) mod[k]=0;

                que[0].val=i;
                que[1].val=j;
                que[0].last=-1;
                que[1].last=0;
                que[0].m=i;
                que[1].m=i*10+j;
                que[0].len=0;
                que[1].len=1;

                mod[i]=mod[i*10+j]=1;

                int top=0;
                int bottom=2;

                while(top<bottom)
                {
                    t=que[top];

                    if(!t.m)
                    {
                        if(t.len<mnlen)
                        {
                            mnlen=t.len;
                            id=i*10+j;
                        }
                        dfs(top);
                        ans[i*10+j][t.len+1]=0;
                        break;
                    }

                    if(i<j)
                    {
                        if(!mod[(t.m*10+i)%n])
                        {
                            mod[(t.m*10+i)%n]=1;

                            que[bottom].last=top;
                            que[bottom].len=t.len+1;
                            que[bottom].m=(t.m*10+i)%n;
                            que[bottom++].val=i;
                        }

                        if(!mod[(t.m*10+j)%n])
                        {
                            mod[(t.m*10+j)%n]=1;

                            que[bottom].last=top;
                            que[bottom].len=t.len+1;
                            que[bottom].m=(t.m*10+j)%n;
                            que[bottom++].val=j;
                        }
                    }
                    else
                    {
                        if(!mod[(t.m*10+j)%n])
                        {
                            mod[(t.m*10+j)%n]=1;

                            que[bottom].last=top;
                            que[bottom].len=t.len+1;
                            que[bottom].m=(t.m*10+j)%n;
                            que[bottom++].val=j;
                        }

                        if(!mod[(t.m*10+i)%n])
                        {
                            mod[(t.m*10+i)%n]=1;

                            que[bottom].last=top;
                            que[bottom].len=t.len+1;
                            que[bottom].m=(t.m*10+i)%n;
                            que[bottom++].val=i;
                        }
                    }

                    top++;
                }
            }
        }

        puts(ans[id]);
    }
}



联系
我们