- 浏览: 196928 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
大致题意:
给出一个整数n,(1 <= n <= 200)。求出任意一个它的倍数m,要求m必须只由十进制的'0'或'1'组成。
解题思路:
首先暴力枚举肯定是不可能的 1000ms 想不超时都难,而且枚举还要解决大数问题。。
要不是人家把这题放到搜索,怎么也想不到用BFS。。。
解题方法: BFS+同余模定理
不说废话。
首先说说朴素的不剪枝搜索方法:
我以n=6为例
首先十进制数,开头第一个数字(最高位)一定不能为0,即最高位必为1
设6的 ”01十进制倍数” 为k,那么必有k%6 = 0
现在就是要用BFS求k值
1、先搜索k的最高位,最高位必为1,则此时k=1,但1%6 =1 != 0
因此k=1不是所求,存储余数 1
2、搜索下一位,下一位可能为0,即 k*10+0,此时k=10,那么k%6=4
可能为1,即 k*10+1,此时k=11,那么k%6=5
由于余数均不为0,即k=10与k=11均不是所求
3、继续搜索第三位,此时有四种可能了:
对于k=10,下一位可能为0,即 k*10+0,此时k=100,那么k%6=4
下一位可能为1,即 k*10+1,此时k=101,那么k%6=5
对于k=11,下一位可能为0,即 k*10+0,此时k=110,那么k%6=2
下一位可能为1,即 k*10+1,此时k=111,那么k%6=3
由于余数均不为0,即k=100,k=101,k=110,k=111均不是所求
4、继续搜索第四位,此时有八种可能了:
对于k=100,下一位可能为0,即 k*10+0,此时k=1000,那么k%6=4
下一位可能为1,即 k*10+1,此时k=1001,那么k%6=5
对于k=101,下一位可能为0,即 k*10+0,此时k=1010,那么k%6=2
下一位可能为1,即 k*10+1,此时k=1011,那么k%6=3
对于k=110,下一位可能为0,即 k*10+0,此时k=1100,那么k%6=2
下一位可能为1,即 k*10+1,此时k=1101,那么k%6=3
对于k=111,下一位可能为0,即 k*10+0,此时k=1110,那么k%6=0
下一位可能为1,即 k*10+1,此时k=1111,那么k%6=1
我们发现k=1110时,k%6=0,即1110就是所求的倍数
如果给的n较大,得到的将是一个大数,这个时候int类型将不能满足需要,我们就开一个__int64的数组供我们使用,具体代码如下:
#include <iostream>
using namespace std;
__int64 q[9999999];
int n;
void BFS()
{
int rear,front;
rear=front=0;
q[rear]=1;//初始化最高位
rear++;
__int64 top;
while (rear>front)
{
top=q[front];
if (top%n==0)
{
break;
}
top*=10;//像一个队列一样双向循环
q[rear]=top;
rear++;
q[rear]=top+1;
rear++;
front++;
}
printf("%I64d\n",top);
}
int main()
{
while (cin>>n&&n!=0)
{
BFS();
}
return 0;
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 789虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 787选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 813题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 949题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 935字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1398题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 977大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1572题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2673是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1207在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 777从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2352题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1062题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1227大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 949大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 964题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1797
2012-04-24 15:05 1590题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1225题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 896题意:Ted今年100岁,给出n对他家族的关系:“父 ... -
poj 1656
2012-04-19 10:07 1094题目要求:一道纯的模拟题目。 直接上代码: ...
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
1426 POJ 3126 POJ 3414 POJ 2251 简单搜索技巧和剪枝 POJ 1010 :star: POJ 2362 POJ 1011(搜索+剪枝) POJ 1416 POJ 2676 POJ 1129:white_question_mark: 数据结构 串 POJ 1016 POJ 1035 POJ 3080 POJ 1936 排序...
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案