算法与acm

poj1426 Find The Multiple 状态搜索

2008年11月10日 阅读(129)

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;

}

You Might Also Like