当前位置:网站首页>P2022 有趣的数(二分&数位dp)
P2022 有趣的数(二分&数位dp)
2022-07-06 04:11:00 【Harris-H】
P2022 有趣的数(二分&数位dp)
麻了。
二分答案,然后用数位dp计算 [ 1 , x ] [1,x] [1,x]中有多少个数字字典序 < < < k k k。
数位dp的时候开两个数组 a , b a,b a,b存 x , k x,k x,k。
然后就是常规的数位dp操作。
注意如果 d p dp dp数组开到 l i m , l e a d lim,lead lim,lead 则每次 c h e c k check check 都需要初始化 d p dp dp为 − 1 -1 −1。
因为这两个变量与 x x x有关。
否则可以只初始化一次。
另外 w , w 1 w,w1 w,w1长度不一定相同,所以 p o s 2 pos2 pos2可能减到 − 1 -1 −1。因此让 w 1 w1 w1基数为 20 20 20。
// Problem: P2022 有趣的数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2022
// Memory Limit: 125 MB
// Time Limit: 400 ms
// Date: 2022-07-05 13:23:31
// --------by Herio--------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll f[20][40][2][2][2],n,m;
int a[20],w;
int b[40],w1;
ll dfs(int pos, int pos2, bool cmp, bool lim, bool lead) {
if (pos == 0)
return (cmp || pos2 > 20) && (!lead);
if ( f[pos][pos2][cmp][lim][lead] != -1)
return f[pos][pos2][cmp][lim][lead];
ll tmp = 0, up = lim ? a[pos] : 9;
for (int i = 0; i <= up; ++i) {
bool nxcmp = !(lead && i == 0) && i < b[pos2];
nxcmp |= cmp;
if (!cmp && i > b[pos2])
continue;
tmp += dfs(pos - 1, pos2 - ((lead && i == 0) ? 0 : 1), nxcmp, lim && i == a[pos], lead && i == 0);
}
return f[pos][pos2][cmp][lim][lead] = tmp;
}
ll check(ll n) {
w = 0;memset(f, -1, sizeof (f));
while (n)
a[++w] = n % 10, n /= 10;
//printf("w=%d\n",w);
ll re = dfs(w, w1, false, true, true);
return re;
}
int main()
{
scanf("%lld%lld", &n, &m);
w1 = 20;
ll l = m > n ? m : n, r = 7e17, ans = 0;
while (n)
b[++w1] = n % 10, n /= 10;
//printf("w1=%d\n",w1);
for (; l <= r;) {
ll mid = (l + r) >> 1, tmp = check(mid);
// printf("%lld %lld\n",mid,tmp);
if (tmp == m - 1) {
ans = mid; r = mid - 1;
}
else if (tmp < m - 1) l = mid + 1;
else r = mid - 1;
}
printf("%lld\n", ans);
}
边栏推荐
- Cross domain and jsonp details
- 10 exemples les plus courants de gestion du trafic istio, que savez - vous?
- Viewing and verifying backup sets using dmrman
- /usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
- Understanding of processes, threads, coroutines, synchronization, asynchrony, blocking, non blocking, concurrency, parallelism, and serialization
- DM8 archive log file manual switching
- Execution order of scripts bound to game objects
- C form application of C (27)
- 51nod 1130 n factorial length V2 (Stirling approximation)
- 自动化测试的好处
猜你喜欢
Network security - Security Service Engineer - detailed summary of skill manual (it is recommended to learn and collect)
Understanding of processes, threads, coroutines, synchronization, asynchrony, blocking, non blocking, concurrency, parallelism, and serialization
Solution to the problem that the root account of MySQL database cannot be logged in remotely
Custom event of C (31)
10 exemples les plus courants de gestion du trafic istio, que savez - vous?
TCP/IP协议里面的网关地址和ip地址有什么区别?
Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did
Class A, B, C networks and subnet masks in IPv4
自动化测试的好处
Thread sleep, thread sleep application scenarios
随机推荐
How to execute an SQL statement in MySQL
Solution to the problem that the root account of MySQL database cannot be logged in remotely
Stable Huawei micro certification, stable Huawei cloud database service practice
使用JS完成一个LRU缓存
asp. Core is compatible with both JWT authentication and cookies authentication
Overturn your cognition? The nature of get and post requests
10 exemples les plus courants de gestion du trafic istio, que savez - vous?
Global and Chinese markets for MRI safe implants 2022-2028: technology, participants, trends, market size and share Research Report
How can programmers resist the "three poisons" of "greed, anger and ignorance"?
20、 EEPROM memory (AT24C02) (similar to AD)
【按键消抖】基于FPGA的按键消抖模块开发
2/12 didn't learn anything
In depth MySQL transactions, stored procedures and triggers
1291_ Add timestamp function in xshell log
Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
MySQL about self growth
Codeforces Round #770 (Div. 2) B. Fortune Telling
MySQL master-slave replication
C (XXIX) C listbox CheckedListBox Imagelist
P2648 make money