POJ 1426 Find The Multiple - DFS

╰+哭是因爲堅強的太久メ 2021-09-30 09:14 317阅读 0赞

题目地址

分析:

　　简单DFS，也可以用BFS做，有看到其他博主的代码。

　　找一个只含0和1的数ans是所输入的数n的倍数。

　　第一位一定是1，所以DFS从 ans = 1 开始找，只有 ans*10 / ans*10+1， 满足ans只含0和1。 // 开始一直不懂为啥。。为什么大家都是（ k == 19 ）return; 后来终于看到有人写，数据最大应该就是19了。 

  1. 1 #include<iostream>
  2.  2 #include<algorithm>
  3.  3 #include<cstring>
  4.  4 #define LL long long
  5.  5 using namespace std; 6 
  6.  7 int n, flag; 8 void dfs(int k, LL ans) 9 { 10     if(k == 19 || flag) return; 11     if(ans % n == 0){ 12         cout << ans << endl; 13         flag = 1; 14         return; 15 } 16     dfs(k+1,ans*10); 17     dfs(k+1,ans*10+1); 18 } 19 int main() 20 { 21     int k; 22     while(cin >> n && n){ 23         flag = 0; 24         dfs(0,1); 25 } 26     return 0; 27 }

转载于:https://www.cnblogs.com/JiaaaaKe/p/9517984.html

发表评论

表情：
评论列表 （有 0 条评论，317人围观）

还没有评论，来说两句吧...

相关阅读