http://acm.pku.edu.cn/JudgeOnline/problem?id=1426
如果想到方法，写起来蛮快，无奈我写的if,else逻辑太复杂，直接导致wa，而且很难查错，只好重新重构了下条件判断的组合方式，才ac。
想来，这个题目的算法是晚上睡觉，偶尔想起以前在smth灌水的时候，遇到过一个题目，在脑中搜索了许久，终于想起来，那是一道求n位全1整数除以某个数m的余数为0，求n为多少之类的。。。
当时大概是这样想的，x =（x*10+1）mod m,只需要这样循环就可以了，对于mod m来说，因为余数只可能有0,1,...m-1，所以必然会出现循环节
其实这就类似于一个有理数的出发 n/m 同样它的小数形式也是必然存在循环节的，因为当我们除以m得到的某些余数，这些余数个数比如小于等于m，当我们进行了大于m次除法时，产生的这些大于m个余数，根据鸽巢原理，必然存在相同的两个，而这两个变构成了一个循环，总会如此轮回下去，直到永远。。。
这个题目，不过是对上述题目的一个扩充，把全1换成了可以取0，1实际上思想还是一样的，
{a1a2.......ai},原来的ai只能取1，现在可以取0，1.实际上我们可以任意扩充到某个集合，比如0,1,2。。。如此等等
原来的状态空间是个线，现在变成了二叉树
0
0 1
01 01
不过树中节点，同样是在mod m，也同样会存在循环节，这样就可以把余数作为一个状态保存，当再次到达该余数时，说明会进入循环，这样就不必再去搜索了。
符：AC代码
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define MAX_N 210
using namespace std;
bool is_found[MAX_N];
char result[MAX_N];
bool is_finish;
int n;
void init(){
memset(is_found,0,sizeof(is_found));
is_finish = false;
result[0] = '1';
}
//使用dfs会使长度超过100
void dfs(int mod_res,int index){
if(is_finish || index > 100 || is_found[mod_res])return;
if(mod_res == 0 ){ for(int j = 0 ; j < index ; j++){
printf("%c",result[j]);
}
printf("\n");
is_finish = true;
return;
}
else if(index < 100){
is_found[mod_res] = true;
result[index] ='0';
dfs((mod_res*10)%n,index+1);
result[index] ='1';
dfs((mod_res*10+1)%n,index+1);
}
}
int main()
{
n = 0;
while(scanf("%d",&n) && n != 0){
if(n == 1){printf("1\n");continue;}
init();
dfs(1,1);
}
return 0;
}
评论