海胖博客

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4474

题解

感觉应该是第一次接触这种类型的题目（数位搜索），发一篇马克一下。

n的最小倍数：要求不存在题中给的m个数字0~9；

即x%n==0;不存在输出-1；

结果会爆64位，应当用字符串储存；

用符合条件的数字进行bfs，最早找到的就是答案；

记录：pre[t]记录到达t的前一节点u，num[t]记录形成t的最后一位数字。

另一种说法：

按照数的位数BFS，从小向大枚举就可以保证构造出来的数是递增的，如果不加判断就直接搜索的话，复杂度非常高，因此需要剪枝。

优化方法：

如果一个数%N==0，那么这个数就是N的倍数。

在没有找到的前提下，如果A%N==B%N，而且A<B，那么其实我们就可以取A而不取B，因为如果在A末尾增加C可以使得AC%N==0，那么BC%N也等于0，易得：如果A和B追加数之后%N==0，那么最优条件下追加的数肯定相同。因此我们只需要维护组合出来的数%N的值即可，如果在搜索的途中出现了相同的%N值，就可以直接忽略了，因为肯定没有前面的优秀。

/*
 * Author: Haipz
 * School: HDU
 * File Name: 4474.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int N = 10000;
queue<int> Q;
bool a[10];
int pre[N + 5], num[N + 5];

void PRINT(int v) {
    if (pre[v] != -1) PRINT(pre[v]);
    printf("%d", num[v]);
}

void bfs(int n) {
    memset(pre, -1, sizeof(pre));
    memset(num, -1, sizeof(num));
    while (!Q.empty()) Q.pop();
    for (int i = 1; i < 10; ++i)
        if (a[i]) {
            if (i % n == 0) {
                printf("%d", i);
                return;
            }
            Q.push(i % n);
            num[i % n] = i;
        }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int i = 0; i < 10; ++i)
            if (a[i]) {
                int v = (u*10 + i) % n;
                if (num[v] == -1) {
                    Q.push(v);
                    num[v] = i;
                    pre[v] = u;
                }
                if (v == 0) {
                    PRINT(v);
                    return;
                }
            }
    }
    printf("-1");
    return;
}

int main() {
    int ics = 0, n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(a, true, sizeof(a));
        while (m--) {
            int t;
            scanf("%d", &t);
            a[t] = false;
        }
        printf("Case %d: ", ++ics);
        bfs(n);
        printf("\n");
    }
    return 0;
}

转载保留版权：http://haipz.com/blog/i/5554 - 海胖博客