当前位置:网站首页>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);
}
边栏推荐
- 10個 Istio 流量管理 最常用的例子,你知道幾個?
- Explain in simple terms node template parsing error escape is not a function
- Redis (replicate dictionary server) cache
- 图应用详解
- Python book learning notes - Chapter 09 section 01 create and use classes
- ESP32_ FreeRTOS_ Arduino_ 1_ Create task
- Global and Chinese market of plasma separator 2022-2028: Research Report on technology, participants, trends, market size and share
- Use js to complete an LRU cache
- Viewing and verifying backup sets using dmrman
- Chinese brand hybrid technology: there is no best technical route, only better products
猜你喜欢
Path of class file generated by idea compiling JSP page
When debugging after pycharm remote server is connected, trying to add breakpoint to file that does not exist: /data appears_ sda/d:/segmentation
[disassembly] a visual air fryer. By the way, analyze the internal circuit
[FPGA tutorial case 11] design and implementation of divider based on vivado core
10 exemples les plus courants de gestion du trafic istio, que savez - vous?
Query the number and size of records in each table in MySQL database
Data processing methods - smote series and adasyn
Web components series (VII) -- life cycle of custom components
Database, relational database and NoSQL non relational database
Stack and queue
随机推荐
ESP32_ FreeRTOS_ Arduino_ 1_ Create task
Figure application details
[leetcode question brushing day 33] 1189 The maximum number of "balloons", 201. The number range is bitwise AND
2328. Number of incremental paths in the grid graph (memory search)
R note prophet
Web components series (VII) -- life cycle of custom components
About some basic DP -- those things about coins (the basic introduction of DP)
P3500 [POI2010]TES-Intelligence Test(二分&离线)
Ipv4中的A 、B、C类网络及子网掩码
Lambda expression learning
题解:《单词覆盖还原》、《最长连号》、《小玉买文具》、《小玉家的电费》
About some basic DP -- those things about coins (the basic introduction of DP)
Detailed explanation of serialization and deserialization
View 工作流程
Solution of storage bar code management system in food industry
解决“C2001:常量中有换行符“编译问题
Comprehensive ability evaluation system
10 exemples les plus courants de gestion du trafic istio, que savez - vous?
查询mysql数据库中各表记录数大小
Basic knowledge of binary tree, BFC, DFS