登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

poj1426 Find The Multiple 状态搜索  

2008-11-10 15:52:23|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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;

}

  评论这张
 
阅读(1349)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018