HDU 6659 Acesrc and Good Numbers (数学 思维)
2019 杭电多校 8 1003
题目链接:HDU 6659
比赛链接:2019 Multi-University Training Contest 8
Problem Description
Acesrc is a famous mathematician at Nanjing University second to none. Playing with interesting numbers is his favorite. Today, he finds a manuscript when cleaning his room, which reads
... Let \(f(d,n)\) denote the number of occurrences of digit \(d\) in decimal representations of integers \(1,2,3,⋯,n\). The function has some fantastic properties ...
... Obviously, there exist some nonnegative integers \(k\), such that \(f(d,k)=k\), and I decide to call them \(d\)-good numbers ...
... I have found all d-good numbers not exceeding \(10^{1000}\), but the paper is too small to write all these numbers ...
Acesrc quickly recollects all \(d\)-good numbers he found, and he tells Redsun a question about \(d\)-good numbers: what is the maximum \(d\)-good number no greater than \(x\)? However, Redsun is not good at mathematics, so he wants you to help him solve this problem.
Input
The first line of input consists of a single integer \(q (1\le q\le 1500)\), denoting the number of test cases. Each test case is a single line of two integers \(d (1\le d\le 9)\) and \(x (0\le x\le 10^{18})\).
Output
For each test case, print the answer as a single integer in one line. Note that \(0\) is trivially a \(d\)-good number for arbitrary \(d\).
Sample Input
3
1 1
1 199999
3 0
Sample Output
1
199990
0
Solution
题意
定义 \(f(d, n)\) 为十进制下 \(1\) 到 \(n\) 所有数的数位中数字 \(d\) 出现的次数。给定 \(x\),找出最大的 \(n(n \le x)\) 满足 \(f(d, n) = n\)。
题解
看到了一个神仙做法。
显然如果 \(f(d, x) = x\) 时就直接输出。
否则,需要缩小 \(x\)。令 \(f(d, x) = y\),则需要将 \(x\) 缩小 \(\lceil \frac{|x - y|}{18} \rceil\)。即 \(x = x - abs(f(d, x) - x) / 18\)。原因是 \(f(d, x)\) 与 \(f(d, x - 1)\) 最多相差 \(18\) 个 \(d\) \(\ (e.g. \ f(9, 10^{18}-1)\ to\ f(9, 10^{18}-2))\)。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 计算 1 到 n 中数字 x 出现的次数
ll f(ll d, ll n) {
ll cnt = 0, k;
for (ll i = 1; k = n / i; i *= 10) {
cnt += (k / 10) * i;
int cur = k % 10;
if (cur > d) {
cnt += i;
}
else if (cur == d) {
cnt += n - k * i + 1;
}
}
return cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
ll d, x;
cin >> d >> x;
while (true) {
ll num = f(d, x);
if (num == x) {
cout << x << endl;
break;
} else {
x -= max(1LL, abs(num - x) / 18);
}
}
}
return 0;
}
Reference
2019 Multi-University Training Contest 8——Acesrc and Good Numbers(数学 想法)
最新文章
- 左右手坐标系转换时R和T的具体形式分析
- PC小技巧
- PHP框架Yii2.0安装(基础版、高级版)
- oracle学习笔记(一)配置监听
- Chronometer控件实现的Android计时器
- eclipse中 将java项目转换为web项目 博客分类: Tomcat
- Word Puzzles
- 使用PHP脚本来写Daemon程序
- 《University Calculus》-chaper13-向量场中的积分-线积分
- qwebkit - Open new window after click using QT - Stack Overflow
- jffs2reset 实现分析
- 自己动手搭建苹果推送Push服务器
- 2017 Multi-University Training Contest - Team 9 1003&;&;HDU 6163 CSGO【计算几何】
- uwsgi服务启动(start)停止(stop)重新装载(reload)
- css布局-双飞翼布局
- android中使用afinal一行源码显示网络图片
- idea工具maven生命周期clean,compile,install,package区别
- yii2常用查询
- <;亲测>;CentOS中yum安装ffmpeg
- Python多线程中阻塞(join)与锁(Lock)的使用误区
热门文章
- HTML5: HTML5 Canvas
- find pattern
- 导数与偏导数&#160;Derivative&#160;and&#160;Partial&#160;Derivative
- gentoo/funtoo 环境配置使用 valgrind
- 一个线上Java空指针问题的排查经过
- CF914D
- MySQL-技术专区-mysql数据库权限管理
- syslog-ng收集日志+ELK平台搭建教程
- ZOJ-3524 拓扑排序+完全背包(好题)
- HBase之BlockCache数据读取(转)