当前位置:网站首页>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);
}
原网站

版权声明
本文为[Harris-H]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/187/202207060411331210.html