P1988 火炬

admin

https://www.luogu.org/problemnew/show/P1988

题目描述
2008北京奥运会，你想成为四川汶川的一名火炬手，经过层层选拔，终于到了最后一关，这一关是一道很难的题：任意给定一个正整数N(N<=100000)，求一个最小的正整数M，使得N * M的十进制表示形式里只含有1和0。

输入输出格式
输入格式：
一行，输入一个整数N。

输出格式：
输出一行，如果有解，输出最小的M，否则输出“No Solution”

输入输出样例
输入样例#1：
12
输出样例#1：
925

黄煦喆

1. #include<iostream>
   
2. #include<queue>
   
3. using namespace std;
   
4. typedef unsigned long long ull;
   
5. ull a,s,b;
   
6. queue<ull>pq;
   
7. int main()
   
8. {
   
9.     cin>>a;
   
10.     pq.push(1);
    
11.     while(!pq.empty()&&!b)
    
12.     {
    
13.         s=pq.front();
    
14.         pq.pop();
    
15.         if(!(s%a))b=s/a;
    
16.         else
    
17.         {
    
18.             pq.push(s*10);
    
19.             pq.push(s*10+1);
    
20.         }
    
21.     }
    
22.     cout<<b;
    
23.     return 0;
    
24. }
    

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. long long x,n,c[20],m;
    
14. void dfs(long long w,long long all)
    
15. {
    
16.         if(w==1)
    
17.         {
    
18.                 if(all%n==0)
    
19.                         m=all/n;
    
20.                 return;
    
21.         }
    
22.         if(!m) dfs(w-1,all);
    
23.         if(!m) dfs(w-1,all+c[w-1]);
    
24. }
    
25. int main()
    
26. {
    
27.         scanf("%lld",&n);
    
28.         for(long long i=1,j=1;i<=19;i++,j*=10)
    
29.                 c[i]=j;
    
30.         dfs(19,0);
    
31.         if(!m) dfs(19,1000000000000000000);
    
32.         if(m)
    
33.                 printf("%lld",m);
    
34.         else
    
35.                 printf("No Solution");
    
36.         return 0;
    
37. }

复制代码

admin

萌同学用的bfs，做法很直观，程序很短小

t20020125

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;
queue<long long>q;
int main()
{
    int n;
    cin>>n;
    q.push(1);
    while(1)
    {
        if(q.front()%n==0)
        break;
        long long temp=q.front();
        q.pop();
        q.push(temp*10);
        q.push(temp*10+1);
    }
    cout<<q.front()/n;
    return 0;
}

吴语林

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. using namespace std;
   
5. long long x,n,c[20],m;
   
6. void dfs(long long w,long long all)
   
7. {
   
8.         if(w==1)
   
9.         {
   
10.                 if(all%n==0)
    
11.                         m=all/n;
    
12.                 return;
    
13.         }
    
14.         if(!m) dfs(w-1,all);
    
15.         if(!m) dfs(w-1,all+c[w-1]);
    
16. }
    
17. int main()
    
18. {
    
19.         scanf("%lld",&n);
    
20.         for(long long i=1,j=1;i<=19;i++,j*=10)
    
21.                 c[i]=j;
    
22.         dfs(19,0);
    
23.         if(!m) dfs(19,1000000000000000000);
    
24.         if(m)
    
25.                 printf("%lld",m);
    
26.         else
    
27.                 printf("No Solution");
    
28.         return 0;
    
29. }

复制代码

wzd(temp)

wzd(temp) 发表于 2018-5-12 16:53
WZD同学你的DFS框架都是类似的但是我感觉有点臃肿，可以优化一下的，你看你的return那么多

收到。/////////////

admin

张笑宇采用把数字化成二进制然后合成为十进制数的做法，很不错

张笑宇

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. long long n,i,a[1010];
   
5. bool b=true;
   
6. void mysearch(int x)
   
7. {
   
8.     int s=0;
   
9.     while (x>0)
   
10.     {
    
11.         s++;
    
12.         a[s]=x%2;
    
13.         x=x/2;
    
14.     }
    
15.     long long sum=0;
    
16.     for (int j=s;j>=1;j--) sum=10*sum+a[j];
    
17.     if (sum%n==0)
    
18.     {
    
19.         cout<<sum/n;
    
20.         exit(0);
    
21.     }
    
22. }
    
23. int main()
    
24. {
    
25.     cin>>n;
    
26.     i=1,b=1;
    
27.     while (b)
    
28.     {
    
29.         mysearch(i);
    
30.         i++;
    
31.     }
    
32.     return 0;
    
33. }
    

复制代码

admin

LYC 问的好？ 无解怎么判断呢？大家先想想