首页 > 搜索 > BFS搜索 > HDU 4294-Multiple-BFS-[解题报告]HOJ
2015
05-23

HDU 4294-Multiple-BFS-[解题报告]HOJ

Multiple

问题描述 :

  Given a positive integer N, you’re to solve the following problem:
  Find a positive multiple of N, says M, that contains minimal number of different digits in base-K notation. If there’re several solutions, you should output the numerical smallest one. By saying numerical smallest one, we compar their numerical value, so 0xAhex < 11dec.
  You may assume that 1 <= N <= 104 and 2 <= K <= 10.

输入:

  There’re several (less than 50) test cases, one case per line.
  For each test case, there is a line with two integers separated by a single space, N and K.
  Please process until EOF (End Of File).

输出:

  There’re several (less than 50) test cases, one case per line.
  For each test case, there is a line with two integers separated by a single space, N and K.
  Please process until EOF (End Of File).

样例输入:

10 8
2 3
7 5

样例输出:

2222
2
111111

题目链接:Click here~~

题意:

找一个 n 的最小倍数 x,使 x 在 k 进制下包含最少种数字。

解题思路:

那道题解的时候有人说很类似,就趁热一起刷了。

假如只有一种数字,那么我们可以在 O(N) 的时间内 check ,一共 10 种,总复杂度 O(10 * N)。

假如只有两种数字,那么我们对于特定的两个数,可以依照和那道题目的思路,dp[mod] 记录当前余数为 mod 的状态,从小到大依次枚举,找出合法解后,不断维护解的最小值。总复杂度 O(45 * N)。

然后,可以用鸽巢原理证明两种数字一定能构造出 n 的倍数。所以问题就可以解了。

#include <queue>
#include <string>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 1e4 + 5;

#define CLR(a,v) memset(a,v,sizeof(a))

int n,k;

bool vis[N];

pair<int,int> bfs1()
{
    pair<int,int> ans = make_pair(N,N);
    for(int x=1;x<k;x++)
    {
        CLR(vis,false);
        int cur_mod = 0;
        for(int l=1;;l++)
        {
            cur_mod = (cur_mod * k + x) % n;
            if(cur_mod == 0)
            {
                ans = min(ans,make_pair(l,x));
                break;
            }
            if(vis[cur_mod])
                break;
            vis[cur_mod] = true;
        }
    }
    return ans;
}

int pre[N];

char ansAt[N];

bool legal(int a,int b)
{
    queue<int> Q;
    Q.push(0);
    int num[2] = {a,b};
    while(!Q.empty())
    {
        int cur = Q.front();Q.pop();
        for(int i=0;i<2;i++)
        {
            if(cur == 0 && num[i] == 0)
                continue;
            int nxt = (cur * k + num[i]) % n;
            if(!vis[nxt])
            {
                vis[nxt] = true;
                pre[nxt] = cur;
                ansAt[nxt] = '0' + num[i];
                Q.push(nxt);
                if(nxt == 0)
                    return true;
            }
        }
    }
    return false;
}

#define size(v) (int)v.size()

bool __less(string& a,string& b){
    return size(a) < size(b) || size(a) == size(b) && a < b;
}

string sol;

void get_ans(){
    sol = "";
    int p = 0;
    while(p != 0 || sol.empty())
    {
        sol += ansAt[p];
        p = pre[p];
    }
    reverse(sol.begin(),sol.end());
}

string bfs2()
{
    string ans;
    for(int i=0;i<k;i++)
        for(int j=i+1;j<k;j++)
        {
            CLR(vis,false);
            if(!legal(i,j))
                continue;
            get_ans();
            if(ans.empty() || __less(sol,ans))
                ans = sol;
        }
    return ans;
}

int main()
{
    //freopen("out.ads","w",stdout);
    while(~scanf("%d%d",&n,&k))
    {
        pair<int,int> ans1 = bfs1();
        if(ans1.first != N)
        {
            while(ans1.first--)
                printf("%d",ans1.second);
            puts("");
        }
        else
        {
            string ans2 = bfs2();
            printf("%s\n",ans2.c_str());
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dgq8211/article/details/12200461