【基础练习】【数论/模拟】codevs1670 无穷的序列题解

系统管理员 2022-08-02 06:02 207阅读 0赞

文章被盗还是很严重，加版权信息

题目：

题目描述 Description

有一个无穷序列如下： 110100100010000100000… 请你找出这个无穷序列中指定位置上的数字

输入描述 Input Description

第一行一个正整数N，表示询问次数； 接下来的N行每行一个正整数Ai，Ai表示在序列中的位置。

输出描述 Output Description

N行，每行为0或1，表示序列第Ai位上的数字。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【数据范围】 对于100%的数据有N≤1500000，Ai≤10^9

我们观察序列，发现这个序列可以分为很多组，每一组为1和很多0 0的个数取决于他前面的1是第几个1

这道题目有好多做法，看数据规模，单个查询必须是O（1）的时间 但本体数据相当弱= =

先放上我自己的做法，和题解里一位同学是相似的，用模拟。

刚开始想的是存储每个位置上的数字直接查表，但显然空间不足。256M可以开一亿的数组，但本题需要十亿= =

所以改为用数组f\[i\]表示第i个1的位置 这样只需要五万左右 五万平方就是二十五亿了

之后对于每个询问查找有没有i使得f\[i\]==x即可

查找可以优化，优化为二分，还有更快的，利用每个1的位置都是n\*(n+1)/2 将查找范围缩小为几个数

但是我的优化失败了= =好在数据很弱，从1到maxn查找就可以过

上代码

//codevs1670 无穷的序列 数论/模拟
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    const int maxn=50000;
    int f[maxn],n,x;
    
    int main()
    {
    	scanf("%d",&n);
    	f[1]=1;
    	for (int i=2;i<=maxn;i++)
    	{
    		f[i]=f[i-1]+i-1;
    	}
    	for (int i=1;i<=n;i++)
    	{
    		scanf("%d",&x);
    		int l=0;
    		for (int i=1;i<=maxn;i++)
    		{
    			if (f[i]==x)
    			{
    				l=1;
    				break;
    			}
    		}
    		if (l==1) printf("1\n");
    		else {printf("0\n");}
    	}
    	return 0;
    }

显然此题还有更多更好的做法，我来总结一下：

1.里奥的做法，直接解方程n\*(n+1)/2=x的整数解 如果有就是1 否则是0

2.这种方法我不大理解

”判断8\*a-7是否为完全平方数即可  
即是否trunc(sqrt(8\*a-7))=sqrt(8\*a-7)“

3.一种数论方法：

只要求出距离k最近的1所在位置即可  
不难发现  每一个出现1位置都符合n\*(n+1)/2+1，于是进行以下推导：  
设k=n\*(n+1)/2（n为最近的1所在位置，k为询问的位数  
则有2\*k=n\*(n+1)  
可见n=trunc(sqrt(n\*(n+1)))=trunc(sqrt(2\*k))  
求出n后只要判断k是否等于n\*(n+1)/2+1即可  
t:=trunc(sqrt(2\*k));  
if k<>(t\*t+t) div 2+1 then  
ans\[i\]:=0  
else  
ans\[i\]:=1;

有的地方不大懂 尤其是取整这里 trunc是去尾

4.另一种数论 与上方类似，但也有一段不大理解

假设我们遇到了一个输入n，并假设它处于第m组。  
于是：0.5\*(m-1)\*m<n<=0.5\*m\*(m+1)  
上式乘2，得到：m\*(m-1)<2n<=m\*(m+1)  
放缩，得到：(m-1)\*(m-1)<2n<(m+1)\*(m+1)  
这样，我们就只需要将2n开方再取整，那么得到的数字要么是m，要么是m-1，进行一下判断就可以轻松的求解出m  
而m正好就是n在的组数！  
这样，我们就用O(1)的方法求出了n在的组数。秒杀掉此题。

好吧，膜拜上面诸大神，题解多来自codevs

于是这道题就这么结束了 下午还是要加油啊

——溪云初起日沉阁，山雨欲来风满楼。

文章被盗还是很严重，加版权信息

[ametake]: http://blog.csdn.net/ametake