求解：如何优化？（代码已加注释）

无穷的序列

时间限制：1 s 内存限制：128 MB

【题目描述】

有一个无穷序列如下：

110100100010000100000…

请你找出这个无穷序列中指定位置上的数字

【输入格式】

第一行一个正整数N，表示询问次数；

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

【输出格式】

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

【样例输入】

4 3 14 7 6

【样例输出】

0 0 1 0

【提示】

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

【来源】

冲刺NOIP2010模拟试题与解析（五）（提高组复赛）

用了模拟，但是后三个点爆T了。。。请问如何优化？

代码如下：

CPP

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int n,a[100001],b=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        b=0;
        scanf("%d",&a[i]);
        for(int j=1;j*(j-1)/2+1<=a[i];j++){//数学方法可证明第n个可输出1的序号可表示为1+n*（n-1）/2
            if(a[i]==j*(j-1)/2+1){
                printf("1\n");
                b=1;
            }
        }
        if(b==0)printf("0\n");
    }
    return 0;
}

求解：如何优化？（代码已加注释）

讨论操作

回复

相关推荐

求解：如何优化？（代码已加注释）