51nod--1087 1 10 100 1000

题目描述

---

题目来源： Ural 1209 基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注 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

---

解题思想

---

/* 找规律+打表 例如：1101001000 map[i]表示第i个1所在的位置(下标从0开始)， map[0] = 1; map[1] = 2; map[2] = 4; map[3] = 7; 不难发现：规律已经出现了：map[i] = map[i-1] + i;(i>0) map[0] = 1;(i==0) 总体解题思路：t个数据，先求出其中的最大值为max，然后开辟一个打表数组map[sqrt(max*2)],为甚吗开 这么大？假如现在n的长度为1e9， 第一个是 序号 a1 1 长度 1 a2 10 2 a3 100 3 an … n 总长度=n(n+1)/2 = max; n个序号有n个1，map数组只是存每个1的位置，即1 的个数，但是题目给的是总长度，所以我们开的数组大小 就是求n，n = sqrt(max*2)-1 最后就是打表，查表，输出 */

---

代码

---

import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[] a = new int[T]; int max = Integer.MIN_VALUE; for(int i=0; i<T; ++i){ a[i] = sc.nextInt(); if(a[i] > max) max = a[i]; } int Max =(int) Math.sqrt(max*2); int[] map = new int[Max+1]; //打表 map[0] = 1; for(int i=1; i<=Max; ++i) map[i] = map[i-1] + i; //查表 for(int i=0; i<T; ++i){ if(find(a[i],map)) System.out.println("1"); else System.out.println("0"); } } //二分查找 public static boolean find(int k, int[] map){ //在有序数组map里面查找k int left = 0; int right = map.length-1; int mid = -1; while(left <= right){ mid = left + (right-left)/2; if(k < map[mid]){ right = mid-1; }else if(map[mid] < k){ left = mid+1; }else{ return true; } } return false; } }