CF1216E Numerical Sequence
2024-10-06 23:14:32
问题分析
奇奇怪怪的题。。。
首先思路达成一致,从大到小一步一步确定位置。
我们一边分析,一边讲算法。
112123123412345123456123456712345678123456789123456789101234567891011123456789101112
假设我们现在要找的是这个串中的倒数第二个位置(就是1),我们可以这样做:
首先,我们想象着把串分开,变成
1
12
123
1234
12345
123456
1234567
12345678
123456789
12345678910
1234567891011
123456789101112
由于我们发现, 最后一个数字 位数相同 的串 的长度 是一个等差数列,可以方便地求得数列和。所以我们可以枚举 所求位置所在串 的 最后一个数字 的 位数。
在这个例子中,我们先枚举 最后一个数字 的 位数 为\(1\),可以算得这样的串的总长是 \((1+9)*9/2\)。发现不到所求位置,于是把这些串扔掉,顺便所求位置减\(45\)。
12345678910
1234567891011
123456789101112
然后枚举 最后一个数字 的 位数 为\(2\),可以算得这样串的总长是 \((11+(9+2*90))*90/2\)大于所求位置。
所以我们知道了 所求位置 所在串 的 最后一个数 的 位数 是 \(2\)。
然后同样的,根据这个等差数列,我们可以二分求得 所求位置 所在串 的 最后一个数 是多少。
这个例子中,最后锁定在串
123456789101112
然后……
我们可以重复上面的操作,把串分成
1 2 3 4 5 6 7 8 9 10 11 12
然后重复上面的第一步操作确定 所求位置 所在数 的 位数。只不过这次长度数列不再是等差数列,而是值等于数字位数的常数列。
在这个例子中,我们删掉了长度为\(1\)的,留下
10 11 12
然后可以直接算出 所求位置在 12
里。然后问题就解决了!
参考程序
#include <bits/stdc++.h>
#define LL long long
using namespace std;
void Work() {
LL n;
scanf( "%lld", &n );
LL LastLen = 0, Len, Count;
for( Len = 1; ; ++Len ) {
Count = 9;
for( LL i = 1; i < Len; ++i )
Count = Count * 10;
LL Sum = ( LastLen + Len + LastLen + Count * Len ) * Count / 2;
if( n <= Sum ) break;
n -= Sum;
LastLen += Count * Len;
}
LL Left = 1, Right = Count, Mid, Ans;
while( Left <= Right ) {
Mid = ( Left + Right ) >> 1;
LL Sum = ( LastLen + Len + LastLen + Mid * Len ) * Mid / 2;
if( Sum >= n ) {
Ans = Mid;
Right = Mid - 1;
} else Left = Mid + 1;
}
--Ans;
n -= ( LastLen + Len + LastLen + Ans * Len ) * Ans / 2;
++Ans;
for( Len = 1; ; ++Len ) {
Count = 9;
for( LL i = 1; i < Len; ++i )
Count = Count * 10;
LL Sum = Count * Len;
if( Sum >= n ) break;
n -= Sum;
}
LL Num = ( n + Len - 1 ) / Len;
n = n - ( Num - 1 ) * Len;
LL T = 1;
for( LL i = 1; i < Len; ++i ) T = T * 10;
Num = T + Num - 1;
T = Len - n + 1;
for( LL i = 1; i < T; ++i ) Num = Num / 10;
printf( "%lld\n", Num % 10 );
return;
}
int main() {
LL Query;
scanf( "%lld", &Query );
for( LL i = 1; i <= Query; ++i ) Work();
return 0;
}
最新文章
- VS2015常用快捷键总结
- js键盘事件和焦点事件
- 【python】nuitka封装python
- js中let和var定义变量的区别
- 实战录 | 一起唠唠那些常见的DDoS攻击
- Python安装指南
- Installing MySQL Connector/Python using pip v1.5
- 【转】LINUX系统I/O复用技术之二:poll() -- 不错
- bzoj2789
- HDU 4035 Maze(树形概率DP)
- 初识Channel
- torisegit 保存帐号密码
- Letter Combinations of a Phone Number:深度优先和广度优先两种解法
- tensorflow Relu激活函数
- sqoop: mysql to hive
- Python 基础知识----数据类型
- mysql 视图 触发器 事物 存储过程 函数 流程控制
- 更新pip和setuptools
- 在用UEditor往后台传数据写入数据库时,出现错误:从客户端(NewsContent=";<;p>;<;img src=";http://...";)中检测到有潜在危险的 Request.。。。
- jmeter打开其他设备转过来的历史脚本出现报错
热门文章
- tracert命令详解_tracert结果详解_tracert命令使用详解
- JS基础_非布尔值的与或运算
- 【题解】codevs 3044 矩形面积合并
- maven:无效的目标发行版:11
- JSP中的普通路径写法
- tensorboardX使用中 AttributeError: &#39;function&#39; object has no attribute &#39;graph&#39;
- maven 父子工程打包 并且上传linux服务器
- 密码基础知识(2)以RSA为例说明加密、解密、签名、验签
- python 语言
- hadoop--大数据生态圈中最基础、最重要的组件