題目描述
有一個無窮序列如下：
110100100010000100000…
請你找出這個無窮序列中指定位置上的數字
輸入輸出格式
輸入格式：?
第一行一個正整數N，表示詢問次數；
接下來的N行每行一個正整數Ai，Ai表示在序列中的位置。
?
輸出格式：?
N行，每行為0或l，表示序列第Ai位上的數字。
?
輸入輸出樣例
輸入樣例#1：?復制
4
3
14
7
6
輸出樣例#1：?復制
0
0
1
0
說明
對于100%的數據有N≤1500000，Ai≤10^9
思路：前綴和+二分。
#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; map<int,bool>ma; int n,x,sum=1; int main(){scanf("%d",&n);for(int i=1;i;i++){ma[sum]=1,sum+=i;if(sum>1000000000) break; }while(n--){scanf("%d",&x);if(ma[x]) printf("1\n");else printf("0\n");} }
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int ma[44722]; int l,r,mid; int n,x,sum=1; int main(){scanf("%d",&n);ma[1]=1;for(int i=2;i<=44721;i++)ma[i]=ma[i-1]+i-1;while(n--){scanf("%d",&x);l=1;r=44721;int flag=0;for(int i=1;i<=32;i++){mid=(l+r)/2;if(ma[mid]<x) l=mid+1;else if(ma[mid]>x) r=mid-1;else if(ma[mid]==x){ flag=1;break; }}if(flag) printf("1\n");else printf("0\n");} }
?
