Yet Another Multiple Problem（BFS）

最新推荐文章于 2021-11-18 17:40:00 发布

iteye_6881

最新推荐文章于 2021-11-18 17:40:00 发布

阅读量135

点赞数

分类专栏： HDOJ 文章标签： java

本文链接：https://blog.csdn.net/iteye_6881/article/details/82601350

版权

HDOJ 专栏收录该内容

71 篇文章

订阅专栏

Yet Another Multiple Problem

Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3041 Accepted Submission(s): 735

Problem Description

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?

Input

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

Output

For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) while Y is the minimal multiple satisfying the above-mentioned conditions or “-1” (without quotation marks) in case there does not exist such a multiple.

Sample Input

    2345 3 
  

    7 8 9 
  

100

1 0

Sample Output

    Case 1: 2345 
  

    Case 2: -1 
  

Source

2012 Asia Chengdu Regional Contest

题意：

给出 N（1 ~ 10000）和 M，后给出 M 个数字，输出 N 的最小倍数，这个数不包含给出的 M 个数字。

思路：

BFS。枚举 N 的倍数的话无疑会 T，所以从 0 ~ 9 构造数，判断这个数能否出现且维护这个数 % N 的余数，以第一个出现的余数为基准，因为以后出现相同余数的一定会比之前的大，所以第一次出现的余数就放进队列中，知道找到 % N == 0 的为止。下次更新新的数的时候，mod = （mod X 10 + i ）% n。注意插入第一个数的时候也要判断 % N 后是不是等于 0。

AC：

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

using namespace std;

typedef struct {
        int mod;
        string num;
} node;

bool vis[15], p[10005];
int num;

bool bfs () {
        queue<node> q;

        for (int i = 1; i <= 9; ++i) {
                if (!vis[i]) {
                        node a;
                        a.mod = i % num;
                        a.num = i + '0';
                        if (!a.mod) {
                                cout << a.num << endl;
                                return true;
                        }
                        q.push(a);
                }
        }

        while (!q.empty()) {
                node now = q.front(); q.pop();

                for (int i = 0; i <= 9; ++i) {
                        node New;

                        if (!vis[i]) {
                                string a;
                                a = i + '0';

                                New.num = now.num + a;
                                New.mod = (now.mod * 10 + i) % num;
                                if (!New.mod) {
                                        cout << New.num << endl;
                                        return true;
                                } else if (!p[New.mod]) {
                                        q.push(New);
                                        p[New.mod] = 1;
                                }
                        }
                }
        }

        return false;
}

int main() {
        int m, t = 0;

        while (~scanf("%d%d", &num, &m)) {
                memset(vis, 0, sizeof(vis));
                memset(p, 0, sizeof(p));

                while (m--) {
                        int ans;
                        scanf("%d", &ans);
                        vis[ans] = 1;
                }

                printf("Case %d: ", ++t);
                if(!bfs()) printf("-1\n");
        }

        return 0;
}