首页 > ACM题库 > HDU-杭电 > HDU 4474-Yet Another Multiple Problem-字符串-[解题报告]HOJ
2015
07-16

HDU 4474-Yet Another Multiple Problem-字符串-[解题报告]HOJ

Yet Another Multiple Problem

问题描述 :

There are tons of problems about integer multiples. Despite the fact that the topic is not original, the content is highly challenging. That’s why we call it “Yet Another Multiple Problem”.
In this problem, you’re asked to solve the following question: Given a positive integer n and m decimal digits, what is the minimal positive multiple of n whose decimal notation does not contain any of the given digits?

输入:

There are several test cases.
For each test case, there are two lines. The first line contains two integers n and m (1 ≤ n ≤ 104). The second line contains m decimal digits separated by spaces.
Input is terminated by EOF.

输出:

There are several test cases.
For each test case, there are two lines. The first line contains two integers n and m (1 ≤ n ≤ 104). The second line contains m decimal digits separated by spaces.
Input is terminated by EOF.

样例输入:

2345 3
7 8 9
100 1
0

样例输出:

Case 1: 2345
Case 2: -1

这道题比赛的时候很坑,不要以为N=10^4就可以暴力,答案都能超过Long long你还暴力搞?

其实对付数位的题,我感觉还是搜索最应该优先考虑,而实际上这道题就是搜索,怎样剪枝呢?这是难点,其实记录得到的数对n取模就好,并且搜索时按照往后加数,这样的话叶子节点总是new = odd*10 +b[i],其中b[i]是可以用到的数位,这样的话,若存在两个点x,y,它们对n取模相同,这样的话保留小数是不是就可以了?

还有一个坑点,就是结果会比较大,要用字符串记录大数~附代码:

#include <iostream>
#include <cstdio>
#include <queue>
#include <string>

#define N 10005
#define ll __int64
#define ss(a) scanf("%d",&a)
#define cl(a) memset(a,0,sizeof(a))

using namespace std;

int a[12],f[N];
queue<pair<string,int> > rec;

string find_ans(int n,int m)
{
    while (!rec.empty()) rec.pop();
    pair<string,int>init;
    init.first="";init.second=0;
    rec.push(init);
    int i;
    while (!rec.empty())
    {
        pair<string,int> curr=rec.front();
        for (i=0;i<10;i++)
        {
            if (curr.first.length()==0&&i==0) continue;
            if (a[i]) continue;
            char ch='0'+i;
            string ss=curr.first+ch;
            int x=(curr.second*10+i)%n;
            if (!f[x])
            {
                if (x==0) return ss;
                pair<string,int>u;
                u.first=ss;u.second=x;
                rec.push(u);
                f[x]=1;
            }
        }
        rec.pop();
    }
    return "-1";
}

int main()
{
    int i,n,m,x,cas=0;
    while (ss(n)!=EOF)
    {
        ss(m);
        cl(a);cl(f);
        for (i=1;i<=m;i++) 
        {
            ss(x);a[x]=1;
        }
        printf("Case %d: ",++cas);
        cout<<find_ans(n,m)<<endl;
    }
    return 0;
}

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

参考:http://blog.csdn.net/liverpippta/article/details/9822803