[HDU][ACM]4474 Yet Another Multiple Problem
海胖子 - 2014/08/03题目链接
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 - 海胖博客