【二分】CF Round #587 (Div. 3)E2 Numerical Sequence (hard version)
2024-09-07 21:27:57
题目大意
有一个无限长的数字序列，其组成为1 1 2 1 2 3 1.......1 2 ... n...，即重复的1~1,1~2....1~n，给你一个\(k\)，求第\(k(k<=10^{18})\)个数字是什么。
思路
设\(a[i]\)为该数到达\(i\)的长度,\(b[i]\)为第\(i\)个数那一块的长度，\(\sum b[i]=a[i]\),发现\([10^i,10^{i+1})\)的数长度均为\(i+1\),那么在这一段中\(b[i]\)都是一个等差数列，而计算\(a[i]\)就可以分为两块计算，在\(10^i\)之前前面应该就可以处理出来，考虑\(10^i\)之后的情况,设\(l=b[10^{i−1}],cnt=x−10i+1\),所以\(b[x]=b[10^{i−1}]+l×cnt+cnt×(cnt+1)/2×(i+1)\)。
然后就好做了，两次二分就好了，第一次二分找到最大的i使\(b[i]<k\),那么解就在第\(i+1\)块中,\(k−=ssum[i]\)；第二次二分找到最大的\(i\)使\(sum[i]<k\),那么解就在数\(i+1\)中,\(k−=sum[i]\)。最后数\(i+1\)的第\(k\)位就是答案。
代码
等会放 我好难
最新文章
- PIC10F200/202/204/206/220/222/320/322芯片解密程序复制多少钱？
- [转]在Eclipse中使用JUnit4进行单元测试（中级篇）
- javascript模板库jsrender加载并缓存外部模板文件
- svn学习笔记（3）设置
- 161216、使用spring的DefaultResourceLoader自定义properties文件加载工具类
- MATLAB仿真总结
- Open SQL详解
- JavaWeb笔记——三大组件之监听器
- ASP中双引号单引号和&连接符使用技巧
- WordPress Platinum SEO插件跨站脚本漏洞
- 使用ListItem给DropDownList填充数据
- Eclipse中输入系统变量和运行参数--转
- 由fprintf和printf看C语言三种标准流
- C#属性总结
- 使用Intellij Idea自定义MVC框架
- hdu 2089 不要62（入门数位dp）
- beta冲刺5
- 利用css3+js实现简单带立体过渡效果的图片切换（chrome浏览器）
- Java基础 -- 深入理解迭代器
- [LeetCode] Largest Triangle Area 最大的三角区域