POJ 1019:Number Sequence 二分查找
2024-09-06 08:39:09
Number Sequence
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 36013 | Accepted: 10409 |
Description
A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.
For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910
For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910
Input
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)
Output
There should be one output line per test case containing the digit located in the position i.
Sample Input
2
8
3
Sample Output
2
2
题意是给定了一串有规律的数,问位置i的数是0~9中的哪一个。
自己一直再跟着POJ分类的题目在做,然后很自然地就会总看小优的博客。。。但是觉得这道题没有小优说的那么夸张,多么难。
首先计算每一个数的长度,比如11,n[11]=2。
之后计算从1到n 这一段数的长度,比如1234567891011,所以c[11]=13。
最后计算总体的长度,比如1121231234123451234561234567123456781234567891234567891012345678910111,即s[11]=70
初始化这些结束之后,剩下的就是不断切分,先二分找s数组,之后定位到哪一段,即是c数组的事情,在之后定位到是哪一个数,是n数组的事情,再然后就是这个数的第几位,手动算吧。这样逐级下来,就能得到第几个数是什么。
主要就是做的时候思路清晰,别乱就好。
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std; int c[52850];
long long s[52850];
int n[52850];
int num; int length(int x)
{
int sum=0;
while (x != 0)
{
x /= 10;
sum++;
}
return sum;
} void init()
{
int i; c[0] = 0;
s[0] = 0; for (i = 1; i <= 52849; i++)
{
n[i] = length(i);
}
for (i = 1; i <= 52849; i++)
{
c[i] = c[i - 1] + n[i];
} for (i = 1; i <= 52849; i++)
{
s[i] = s[i - 1] + c[i];
}
} int main()
{
init(); int Test,left,pos;
int i;
scanf("%d", &Test); while(Test--)
{
scanf("%d", &num); left = lower_bound(s + 1, s + 52845, num) - (s + 1);
pos = num - s[left]; left= lower_bound(c + 1, c + 52845, pos) - (c + 1);
pos = pos - c[left]; left++;
pos = n[left] - pos +1; i = 1;
while (i < pos)
{
left /= 10;
i++;
}
cout << left % 10<<endl;
} return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- netty5 HTTP协议栈浅析与实践
- iOS 编译时处理器架构选择
- .NET LINQ 限定符操作
- 0015 Java学习笔记-集合-TreeMap集合
- sublime text2 配置代码对齐快捷键
- Java Hour 29 Weather ( 2 ) Maven
- Cortex-M3/4的Hard Fault调试方法
- js 倒计时 已过去时间
- C#同步数据库的数据到Neo4J
- pickle和json模块
- 分布式监控系统Zabbix3.2添加自动发现磁盘IO并注册监控
- Linux(二十一)Shell编程
- GO map
- sflow介绍与安装过程
- AI 可视化
- [UE4]条件融合动画: Blend Posed by int
- python第二十七课——os模块
- NameValuePair方式传参数
- Android Studio 中删除项目和项目找回------ Project Structure的使用
- 循环杀死Mysql sleep进程脚本