首页 > 代码库 > [51nod] 1087 1 10 100 1000
[51nod] 1087 1 10 100 1000
1,10,100,1000...组成序列1101001000...,求这个序列的第N位是0还是1。
Input
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 - T + 1行:每行1个数N。(1 <= N <= 10^9)
Output
共T行,如果该位是0,输出0,如果该位是1,输出1。
Input示例
3
1
2
3
Output示例
1
1
0
一开始的做法是先对1的位数进行打表,然后进行二分
#include <iostream> #include <stdio.h> #include <cstring> using namespace std; const int maxn = 100100; int One[maxn]; void preOne() { int i = 1; One[0] = 1; while (i < maxn) { One[i] = One[i-1]+i; i++; } } bool Find(int x) { int l = 0, r = maxn-1, mid; while (l <= r) { mid = (l+r)>>1; if (One[mid] > x) r = mid-1; else if (One[mid] < x) l = mid+1; else return true; } return false; } int main() { //freopen("1.txt", "r", stdin); preOne(); int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); if (Find(n)) printf("1\n"); else printf("0\n"); } return 0; }
直接用bool类型对i位置是不是1进行打表也可以
其实是有规律的
1 = 1
2 = 1 + (1)
4 = 1 + (1+2)
7 = 1 + (1+2+3)
.....
即 X*(X-1)/2 + 1 == n有解
另t = (int)sqrt(2*n-2) t*(t+1)==2*(n-1)成立时有解
#include <iostream> #include <stdio.h> #include <math.h> using namespace std; int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); int t = (int)sqrt(2*(n-1)); if (t*(t+1) == 2*(n-1)) printf("1\n"); else printf("0\n"); } return 0; }
[51nod] 1087 1 10 100 1000
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。