题目描述：
输入一个整数n，然后让你求出任意一个n的倍数，要求这个数字的各位数字都必须是0或者1，并输出；
基本思路：
这个大你不可能暴力枚举吧，一定会超时，然后如果不是让放在搜索里我也不知道要用搜索，然后就算我知道了要用搜索，一开始我还是不知道我该怎么写，所以，比较来比较了去，还是发现下面这个解法最稳，以后遇到类似的题目不妨考虑一下转化为搜索问题去解决，然后至于这么大一个数，自然而然想到取模；
代码如下：
#include<iostream> #include<iomanip> #include<string> #include<algorithm> #include<queue> #include<set> #include<map> #include<list> #include<stack> #include<vector> #include<cstdio> #include<cmath> #include<cstring> using namespace std; const int maxn = 200+10; struct Node { int mod; string s; };//看这个题目给的范围的话，要存这个字符串那得用string了，加的话方便； Node node[maxn],one,two; bool sign[maxn]; void bfs(int n) { memset(sign,false,sizeof(sign));//每次清空一边，因为是对不同的n取模； queue<Node>q; int x,y; one.s="1"; one.mod=1; sign[1]=1; q.push(one); while(!q.empty()) { one=two=q.front(); q.pop(); x=(one.mod*10+1)%n;//运算就是不断取模，然后就肯定不会超出范围了，然后以后如果遇到倍数的情况的话记得用取模来做，判断余数是不是零就好了； y=(one.mod*10)%n; if(!x)//余数是零，说明找得到了余数，那么直接返回好了； { node[n].s=one.s+"1"; return; } if(!y) { node[n].s=one.s+"0"; return; } if(!sign[x])//这个模会出现余数一样的情况，那么，先判断一下之前是否出现过余数一样的，如果有，这个操作在之前已经有和它等效的了； { one.s=one.s+"1"; one.mod=x; q.push(one); sign[x]=true; } if(!sign[y]) { two.s=two.s+"0"; two.mod=y; q.push(two); sign[y]=true; } } } void init() { node[1].s="1"; node[1].mod=1; for(int i=2;i<=200;i++) { if(i%2==0) node[i].s=node[i/2].s+"0"; else bfs(i); } } int main() { init();//以后看范围打表的话很直接； int n; while(scanf("%d",&n)==1&&n) { cout<<node[n].s<<endl; } }
