注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

01串(qchr)解题报告  

2015-07-28 09:00:50|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

【问题描述】

考虑这样一个序列”110100100010000……”就是”1” + ”10”+”100”+”1000”+……要求求出每i位是0 还是1。

【数据范围】

第一行:N,测试点的个数(0<N<10000)

第二行:N个数(>0),每个数均不超过10^4

【解题思路】

有五种方法:

方法一:当然是暴力破解(范围那么小01串(qchr)解题报告 - 杨鸿飞 - 一个叫杨鸿飞的人的博客),题目怎么说就怎么做——用字符串模拟,用一个数,刚开始是1,后来变成10,100,1000……每一次都用字符串装着,就行了。如果x代表每个数的大小,时间复杂度O(N×x);龟速。空间复杂度是要开x那么大的数组。

方法二:发现1的位置是有规律的,是跟等差数列一样,相邻两个1之间的位置是+2,+3,+4……所以,就用打表的方法,开一个布尔数组,数组下标代表本位是0,还是1。如果x代表每个数的大小,时间复杂度O(x+N),非常快,空间复杂度是要开x那么大的数组。

方法三:更方法二的想法是一样的,只是不用打表,每输入一个数,就用反复用与思路二相同的规律求解。时间复杂度O(N×sqrt(x)),挺快,空间复杂度非常小,都不用开数组。跟方法二比起来,时间慢了,空间小了。

方法四:更方法二的想法是一样的,不过数组记得是1的位置如1,2,4,7,11……在输入一个数时,用二分查找判断是1还是0。时间复杂度O(N×log2x),挺快,空间复杂度比方法二少,比方法三多,是间接与方法二与方法三之间的方法。

方法五,更方法二的想法是一样的,用的是解方程的方法,假如输入一个x,就看看2+2+3+4+5+...+y能否等于x,方程式可化简成 2+2+3+4+5+...+y=x → (1+y)×y÷2+1=x → y?+y=2x-2 。再用二分查找枚举y的答案,找得到是1,找不到是0。时间复杂度O(N×log2x),挺快,空间复杂度非常小,都不用开数组。方法五虽然没有方法二那么快,但总体来说最优。

程序只有方法二:

#include<iostream>
#include<Fstream>

using namespace std;

int f[200000];

void init()    //打表
{
 f[1]=1; f[2]=1;
 int s=2; int p=2;
 while (p<=100000)
 {
  p+=s;
  f[p]=1;
  s++;
 }
}

int main()
{   freopen("qchr.in","r",stdin);
    freopen("qchr.out","w",stdout);
 int n,p;
 init();
 cin>>n;
 for (int i=0; i<n; i++)
 {
  scanf("%d",&p);
  printf("%d\n",f[p]);
 }
}

  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018