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

wzd(temp)

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. using namespace std;
   
4. int x;
   
5. int init()
   
6. {
   
7.         int temp;
   
8.         scanf("%d",&temp);
   
9.         x=temp;
   
10.         int ans;
    
11.         do
    
12.         {
    
13.                 ans++;
    
14.                 temp/=10;
    
15.         }while(temp>0);
    
16.         return ans;
    
17. }
    
18. 
    
19. int d[2];
    
20. long long A_0_1;
    
21. 
    
22. bool dfs(int remain)
    
23. {
    
24.         if(remain==0)
    
25.         {
    
26.                 if(A_0_1!=0 && A_0_1%x==0)
    
27.                 {
    
28.                         printf("%lld\n",A_0_1/x);
    
29.                         return true;
    
30.                 }
    
31.                 return false;
    
32.         }
    
33.         
    
34.         for(int j=0;j<=1;j++)
    
35.         {
    
36.                 if(d[j]>0)
    
37.                 {
    
38.                         d[j]--;
    
39.                         A_0_1=A_0_1*10+j;
    
40.                         if(dfs(remain-1))
    
41.                                 return true;
    
42.                         A_0_1=(A_0_1-j)/10;
    
43.                         d[j]++;
    
44.                 }
    
45.         }
    
46.         
    
47.         return false ;
    
48. }
    
49. bool BAO_search(int qwe)
    
50. {
    
51.         d[0]=qwe; d[1]=qwe;
    
52.         if(dfs(qwe))
    
53.                 return true;
    
54.         return false;
    
55. }
    
56. 
    
57. int main()
    
58. {
    
59.         int t=init();
    
60.         for(int qwe=t;!BAO_search(qwe);qwe++);
    
61.         
    
62.         return 0;
    
63. }

复制代码

WZD同学你的DFS框架都是类似的但是我感觉有点臃肿，可以优化一下的，你看你的return那么多

lyc

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<algorithm>
   
4. #include<cmath>
   
5. #define ll long long
   
6. using namespace std;
   
7. ll w[1000010];
   
8. int main()
   
9. {
   
10.     ll n;
    
11.     cin>>n;
    
12.     for(ll i=1; i; i++)
    
13.     {
    
14.         ll k = i;
    
15.         ll js=0;
    
16.         ll ans = 0;
    
17.         while(k)
    
18.         {
    
19.             w[++js] = k % 2;
    
20.             k /= 2;
    
21.         }
    
22.         for(ll j=js; j>=1; j--)
    
23.             ans = ans * 10 + w[j];
    
24.         if(ans % n == 0)
    
25.         {
    
26.             ans/=n;
    
27.             cout<<ans;
    
28.             return 0;
    
29.         }
    
30.     }
    
31.     return 0;
    
32. }
    

复制代码

无解怎么判断……

admin

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

张笑宇

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

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

wzd(temp)

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

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

吴语林

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. }

复制代码

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;
}

admin

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