HDU 4474 Yet Another Multiple Problem【BFS+一个判断技能】

HDU 4474 Yet Another Multiple Problem【BFS+一个判断技巧】

题意：0-9这十个数字里面的若干个数字组合出一个数，使这个数是N的倍数，求最小的这个这样的数，不存在的话输出-1。

按照数的位数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值，就可以直接忽略了，因为肯定没有前面的优秀。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000020
struct node {
    int pre, mod;
    char c;
} q[N];
int n, m;
bool v[10010];
void print(int x) {
    if (x == 0) return ;
    print(q[x].pre);
    putchar(q[x].c);
}
int main() {
    int cas = 1, t, a[10];
    bool vis[10];
    while (scanf("%d%d", &n, &m) == 2) {
        memset(vis, false, sizeof(vis));
        for (int i=0; i<m; i++) {
            scanf("%d", &t); vis[t] = true;
        }
        m = 0;
        for (int i=0; i<10; i++) if (!vis[i]) a[m++] = i;
        printf("Case %d: ", cas++);

        if (m == 0) {
            puts("-1"); continue;
        }
        memset(v, false, sizeof(v));
        int l = 1, r = 1, ans = -1;
        for (int i=0; i<m; i++) if (a[i]) {
            q[r].pre = 0;
            v[q[r].mod = a[i] % n] = true;
            q[r].c = a[i] + '0';
            if (q[r].mod == 0) { ans = r; break; }
            r++;
        }

        while (l < r && ans == -1) {
            for (int i=0; i<m; i++) {
                q[r].mod = (q[l].mod*10 + a[i])%n;
                if (!v[q[r].mod]) {
                    v[q[r].mod] = true;
                    q[r].pre = l;
                    q[r].c = a[i] + '0';
                    if (q[r].mod == 0) { ans = r; break; }
                    r++;
                }
            }
            l++;
        }

        if (ans == -1) puts("-1");
        else {
            print(ans); printf("\n");
        }
    }


    return 0;
}