华师一附中OI组

标题: P1988 火炬 [打印本页]

作者: admin 时间: 2018-5-11 11:00
标题: P1988 火炬
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) 时间: 2018-5-12 16:53

#include <cstdio>
#include <cstdlib>
using namespace std;
int x;
int init()
{
int temp;
scanf("%d",&temp);
x=temp;
int ans;
do
{
ans++;
temp/=10;
}while(temp>0);
return ans;
}
int d[2];
long long A_0_1;
bool dfs(int remain)
{
if(remain==0)
{
if(A_0_1!=0 && A_0_1%x==0)
{
printf("%lld\n",A_0_1/x);
return true;
}
return false;
}
for(int j=0;j<=1;j++)
{
if(d[j]>0)
{
d[j]--;
A_0_1=A_0_1*10+j;
if(dfs(remain-1))
return true;
A_0_1=(A_0_1-j)/10;
d[j]++;
}
}
return false ;
}
bool BAO_search(int qwe)
{
d[0]=qwe; d[1]=qwe;
if(dfs(qwe))
return true;
return false;
}
int main()
{
int t=init();
for(int qwe=t;!BAO_search(qwe);qwe++);
return 0;
}

复制代码

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

作者: lyc 时间: 2018-5-12 23:19

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
ll w[1000010];
int main()
{
ll n;
cin>>n;
for(ll i=1; i; i++)
{
ll k = i;
ll js=0;
ll ans = 0;
while(k)
{
w[++js] = k % 2;
k /= 2;
}
for(ll j=js; j>=1; j--)
ans = ans * 10 + w[j];
if(ans % n == 0)
{
ans/=n;
cout<<ans;
return 0;
}
}
return 0;
}

复制代码

无解怎么判断……

作者: admin 时间: 2018-5-12 23:45
LYC 问的好？无解怎么判断呢？大家先想想

作者: 张笑宇 时间: 2018-5-13 17:24

#include<iostream>
#include<algorithm>
using namespace std;
long long n,i,a[1010];
bool b=true;
void mysearch(int x)
{
int s=0;
while (x>0)
{
s++;
a[s]=x%2;
x=x/2;
}
long long sum=0;
for (int j=s;j>=1;j--) sum=10*sum+a[j];
if (sum%n==0)
{
cout<<sum/n;
exit(0);
}
}
int main()
{
cin>>n;
i=1,b=1;
while (b)
{
mysearch(i);
i++;
}
return 0;
}

复制代码

作者: admin 时间: 2018-5-13 18:00
张笑宇采用把数字化成二进制然后合成为十进制数的做法，很不错

作者: wzd(temp) 时间: 2018-5-13 22:06

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

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

作者: 吴语林 时间: 2018-5-13 22:50
本帖最后由吴语林于 2018-5-13 22:51 编辑

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
long long x,n,c[20],m;
void dfs(long long w,long long all)
{
if(w==1)
{
if(all%n==0)
m=all/n;
return;
}
if(!m) dfs(w-1,all);
if(!m) dfs(w-1,all+c[w-1]);
}
int main()
{
scanf("%lld",&n);
for(long long i=1,j=1;i<=19;i++,j*=10)
c[i]=j;
dfs(19,0);
if(!m) dfs(19,1000000000000000000);
if(m)
printf("%lld",m);
else
printf("No Solution");
return 0;
}

复制代码

作者: t20020125 时间: 2018-7-4 20:55
#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 时间: 2018-7-4 23:28
萌同学用的bfs，做法很直观，程序很短小

作者: 吴语林 时间: 2018-7-29 20:58

#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
long long x,n,c[20],m;
void dfs(long long w,long long all)
{
if(w==1)
{
if(all%n==0)
m=all/n;
return;
}
if(!m) dfs(w-1,all);
if(!m) dfs(w-1,all+c[w-1]);
}
int main()
{
scanf("%lld",&n);
for(long long i=1,j=1;i<=19;i++,j*=10)
c[i]=j;
dfs(19,0);
if(!m) dfs(19,1000000000000000000);
if(m)
printf("%lld",m);
else
printf("No Solution");
return 0;
}

复制代码

作者: 黄煦喆 时间: 2018-8-25 16:24

#include<iostream>
#include<queue>
using namespace std;
typedef unsigned long long ull;
ull a,s,b;
queue<ull>pq;
int main()
{
cin>>a;
pq.push(1);
while(!pq.empty()&&!b)
{
s=pq.front();
pq.pop();
if(!(s%a))b=s/a;
else
{
pq.push(s*10);
pq.push(s*10+1);
}
}
cout<<b;
return 0;
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)