求解:如何优化?(代码已加注释)

回复帖子

@YYY不吃药 2016-10-12 21:35 回复
  1. 无穷的序列

时间限制: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了。。。请问如何优化?

代码如下:

#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;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。