1087 1 10 100 1000

1087 1 10 100 1000

1,10,100,1000...组成序列1101001000...,求这个序列的第N位是0还是1。 输入 第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000) 第2 - T + 1行:每行1个数N。(1 <= N <= 10^9) 输出 共T行,如果该位是0,输出0,如果该位是1,输出1。 输入样例 3 1 2 3 输出样例 1 1 0

解题思路

通过观察序列发现 1 , 2 , 4 , 7 ... 所有为1的位置 f[2] = f[1] + 1 = 2 f[3] = f[2] + 2 = 4 f[4] = f[3] + 3 = 7

............. f[n] = f[n-1] + n-1 ;

然后通过二分得出结果,找到就是1,没有就是0。

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std ;
typedef long long LL;  
const LL inf = 0x3f3f3f3f3f3f3f3f; 
// 1014 
const LL maxn = 1e18+999 ; 
const int MAX = 1000010 ;
LL dp[MAX] ;  
void init() {

	dp[1] = 1 ; 
	LL j = 1 ;  
	for(LL i = 2 ; i<=100000;i++ ) {
		dp[i] = dp[i-1] +j ; 
		j++ ;  
	}	
}

int main() {
	int t ; 
	init() ;
	cin >>t ; 
	while(t--) {
		int n ; 
		cin >>  n ; 
		int l = 0 , r = 100000 ; 
		int mid ; 
		bool flag = true ; 
		while(l<=r) {
			mid = (l+r)>>1 ;
			 
			if(dp[mid] ==n) {
				flag = false ; 
				cout<<"1"<<endl ; 
				break  ; 
			}
			else if (dp[mid] < n ){
				l = mid + 1 ; 
			}
			else {
				r = mid - 1 ; 
			}
		
		}
			if(flag)
			cout<<"0"<<endl;
			
		
	} 
	
	
	return 0 ; 
}


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×