[HDU 1664] Different Digits DFS+鸽巢原理
给你一个数,要你找它的一个倍数,但是要求倍数里面出现的数字最少,比如15的倍数出现两个数字的是15,一个数字的是555,所以结果是555。
·
http://acm.hdu.edu.cn/showproblem.php?pid=1664
题意:给你一个数,要你找它的一个倍数,但是要求倍数里面出现的数字最少,比如15的倍数出现两个数字的是15,一个数字的是555,所以结果是555。
思路:对于任意的整数 n ,必然存在一个由不多于两个的数字来组成的一个倍数。 因为 a , aa , aaa…… 取 n+1 个,a, aa, aaa, …… 对n取余就是[1, n]之间的数, 则由鸽笼原理,必有两个模 n 余数相同,相减即得 n 的倍数 m ,而 m 只由 a 、 0 组成。所以n的倍数最多不会由超过两个数字的数组成,所以我么先搜索一位的情况在搜所两位的情况就可以了,搜索的过程中不断加然后取模用余数判断重复。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 65555;
struct node{
int pre, pos, key, mod;
};
int sta[maxn], minn;
bool vis[maxn]; //用余数判重,所以只要开到65536
node que[maxn];
//判断数字a和b的大小
bool Judge(int *a, int *b, int len){
for(int i = len-1; i >= 0; i--){
if(a[i] < b[i])
return false;
if(a[i] > b[i])
return true;
}
return false;
}
//搜索由x, y 组成的数
bool Bfs(int n, int x, int y)
{
node w, r;
int real = -1;
int top = 0, rear = 0;
w.mod = w.pos = 0;
w.pre = w.key = -1;
que[rear++] = w;
memset(vis, false, sizeof(vis));
while(top != rear){
r = que[top++];
if(r.mod == 0 && r.pre != -1){
real = top-1;
break;
}
w.key = x;
w.pre = top-1;
w.pos = r.pos + 1;
w.mod = (r.mod*10 + x) % n;
if((w.pos != 1 || w.key != 0) && !vis[w.mod] && w.pos <= minn){
que[rear++] = w;
vis[w.mod] = true;
}
if(x == y)
continue;
w.key = y;
w.pre = top-1;
w.pos = r.pos + 1;
w.mod = (r.mod*10 + y) % n;
if((w.pos != 1 || w.key != 0) && !vis[w.mod] && w.pos <= minn){
que[rear++] = w;
vis[w.mod] = true;
}
}
//更新最优解
if(real != -1){
if(minn > que[real].pos){
minn = 0;
while(que[real].pre != -1){
sta[minn++] = que[real].key;
real = que[real].pre;
}
}
//出现数字个数相同的情况就选最小的
else if(minn == que[real].pos){
minn = 0;
int arg[maxn];
while(que[real].pre != -1){
arg[minn++] = que[real].key;
real = que[real].pre;
}
if(Judge(sta, arg, minn)){
for(int i = 0; i < minn; i++){
sta[i] = arg[i];
}
}
}
return true;
}
return false;
}
bool Search(int n, int flag) // 搜索由flag个数字组成的n的倍数
{
if(flag == 1){
for(int i = 1; i < 10; i++){
Bfs(n, i, i);
}
if(minn != 100000000) //搜索到结果
return true;
}
else{
for(int i = 0; i < 10; i++){
for(int k = i+1; k < 10; k++){
Bfs(n, i, k);
}
}
}
return false;
}
int main()
{
int n;
// freopen("F:\\JudgeLocal\\testdata\\input.txt","r",stdin);
// freopen("F:\\JudgeLocal\\testdata\\output1.txt","w",stdout);
while(cin>>n && n){
minn = 100000000;
if(n <= 10){
cout<<n<<endl;
continue;
}
if(n <= 100){
if(!Search(n, 1)){
cout<<n<<endl;
continue;
}
}
if(!Search(n, 1)){
Search(n, 2);
}
for(int i = minn-1; i >= 0; i--){
cout<<sta[i];
}
cout<<endl;
}
return 0;
}
更多推荐
已为社区贡献2条内容
所有评论(0)