洛谷P1795 无穷的序列

url: https://www.luogu.com.cn/problem/P1795

tag:
二分

思路：
将每一个以1开头的片段当作一个整体ki，同时用ki表示当前片段数字的个数，那么若干个ki组合起来的片段的最后一个位置的坐标就是对ki求和Si。所以可以先用二分找到一个大于A的最小值，则A就在那个ki当中，然后求一下A距离上一个ki的偏移量，用A减去S(i - 1)，之后进行判断，如果 == 1则说明A处数字为1，否则就是0。

代码：

#include <iostream>  
#include <cstdio>  
using namespace std;  
int main()  
{  
    int n;  
    scanf("%d", &n);  
    while(n --)  
    {  
        int a;  
        scanf("%d", &a);  
        long long l = 0, r = 1e9;  
        while (l < r)  
        {  
            long long mid = (l + r) >> 1;  
            if (((mid * (mid + 1)) / 2) >= a) r = mid;  
            else l = mid + 1;  
        }  
        l --;  
        long long offset = a - (l * (l + 1)) / 2;  
        if (offset == 1) printf("%d\n", 1);  
        else printf("%d\n", 0);  
    }  
    return 0;  
}