当前位置:网站首页>P2022 interesting numbers (binary & digit DP)
P2022 interesting numbers (binary & digit DP)
2022-07-06 04:16:00 【Harris-H】
P2022 Interesting numbers ( Two points & digit dp)
It's numb .
Two points answer , Then use digits dp Calculation [ 1 , x ] [1,x] [1,x] How many numbers in the dictionary order < < < k k k.
digit dp Open two arrays when a , b a,b a,b save x , k x,k x,k.
Then there are conventional digits dp operation .
Note that if d p dp dp Open the array to l i m , l e a d lim,lead lim,lead Every time c h e c k check check All need to be initialized d p dp dp by − 1 -1 −1.
Because these two variables are related to x x x of .
Otherwise, you can initialize only once .
in addition w , w 1 w,w1 w,w1 The length is not necessarily the same , therefore p o s 2 pos2 pos2 May be reduced to − 1 -1 −1. So let w 1 w1 w1 The base number is 20 20 20.
// Problem: P2022 Interesting numbers
// 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);
}
边栏推荐
- /usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
- ESP32_ FreeRTOS_ Arduino_ 1_ Create task
- asp. Core is compatible with both JWT authentication and cookies authentication
- Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
- 2/12 didn't learn anything
- C. The Third Problem(找规律)
- Viewing and verifying backup sets using dmrman
- MySQL master-slave replication
- Global and Chinese markets for otolaryngology devices 2022-2028: Research Report on technology, participants, trends, market size and share
- What is the difference between gateway address and IP address in tcp/ip protocol?
猜你喜欢
math_ Derivative function derivation of limit & differential & derivative & derivative / logarithmic function (derivative definition limit method) / derivative formula derivation of exponential functi
One question per day (Mathematics)
电脑钉钉怎么调整声音
[adjustable delay network] development of FPGA based adjustable delay network system Verilog
Redis (replicate dictionary server) cache
1291_Xshell日志中增加时间戳的功能
Basic use of MySQL (it is recommended to read and recite the content)
ESP32_ FreeRTOS_ Arduino_ 1_ Create task
[PSO] Based on PSO particle swarm optimization, matlab simulation of the calculation of the lowest transportation cost of goods at material points, including transportation costs, agent conversion cos
Chinese brand hybrid technology: there is no best technical route, only better products
随机推荐
Global and Chinese market of plasma separator 2022-2028: Research Report on technology, participants, trends, market size and share
View 工作流程
Fedora/REHL 安装 semanage
[introduction to Django] 11 web page associated MySQL single field table (add, modify, delete)
【leetcode】1189. Maximum number of "balloons"
Record an excel xxE vulnerability
2/13 review Backpack + monotonic queue variant
Tips for using dm8huge table
C. The third problem
. Net interprocess communication
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
【leetcode】22. bracket-generating
Database, relational database and NoSQL non relational database
Understanding of processes, threads, coroutines, synchronization, asynchrony, blocking, non blocking, concurrency, parallelism, and serialization
Global and Chinese markets for MRI safe implants 2022-2028: technology, participants, trends, market size and share Research Report
TCP/IP协议里面的网关地址和ip地址有什么区别?
Execution order of scripts bound to game objects
P2022 有趣的数(二分&数位dp)
拉格朗日插值法
Codeforces Round #770 (Div. 2) B. Fortune Telling