数位dp/二分/思维(石油大学G: A-Number and B-Number)

作者:神秘网友 发布时间:2020-09-07 11:03:44

数位dp/二分/思维(石油大学G: A-Number and B-Number)

数位dp/二分/思维(石油大学G: A-Number and B-Number)

数位dp/二分/思维(石油大学G: A-Number and B-Number)
题意:有两种序列A-Number和B-Number。A-Number是所有数位中有7的和被7整除的数。B-Number是A-Number序列除去下标是数位中有7的和被7整除的数。问:第N个B-Number是。
题解:这个题只要想明白了,就特别水。我们可以考虑二分结果。然后计算他前面有多少个B-Number。如果比N大则缩小,否则增大。那怎么找他是前面有多少个B-Number呢。很简单,我们设F(x)为[0, x]之间A-Number的数量。那么数x之前有ans个B-Number:
ans=F(x)?F(F(x)?1)ans=F(x) -F(F(x)-1)ans=F(x)?F(F(x)?1)
然后就是数位dp模板了。
下面是ac代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include <map>
#include <queue>
#include <set>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <array>
#include <cctype>
#include <time.h>

#pragma GCC optimize(2)

void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); }
void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); }
void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; }
template <typename T>
bool bacmp(const T & a, const T & b) { return a > b; }
template <typename T>
bool pecmp(const T & a, const T & b) { return a < b; }

#define ll long long
#define ull unsigned ll
#define _min(x, y) ((x)>(y)?(y):(x))
#define _max(x, y) ((x)>(y)?(x):(y))
#define max3(x, y, z) ( max( (x), max( (y), (z) ) ) )
#define min3(x, y, z) ( min( (x), min( (y), (z) ) ) )
#define pr(x, y) (make_pair((x), (y)))
#define pb(x) push_back(x);
using namespace std;

const int N = 1e5+5;
ll dp[32][8][2];
int su[32];
ll dfs(int cur, int m,  int d, int flag)
{
    if (cur < 0)
    {
        return d || m == 0;
    }
    if (dp[cur][m][d]!=-1 && !flag) return dp[cur][m][d];
    int mx = flag ? su[cur] : 9;
    ll ans = 0;
    for (int i = 0; i <= mx; i++)
        ans += dfs(cur-1, (m * 10 + i) % 7, d || i == 7, flag && i == mx);
    if (!flag) dp[cur][m][d] = ans;
    return ans;
}
ll sol(ll x)
{
    int cnt = 0;
    while(x)
    {
        su[cnt++] = x % 10;
        x /= 10;
    }
    return dfs(cnt-1, 0, 0, 1);
}
int main()
{
    memset(dp, -1, sizeof(dp));
    ll n;
    while(scanf("%lld", &n) != EOF)
    {
        ull l = 0, r = (1ull << 63) - 1;
        while(l <= r)
        {
            ull mid = (l + r) >> 1;
            ll a = sol((ll)mid);
            if (a - sol(a - 1) < n) l = mid + 1;
            else r = mid - 1;
        }
        ll c = l;
        printf("%lld\n", c);
    }
    return 0;
}

数位dp/二分/思维(石油大学G: A-Number and B-Number)相关教程

  1. [LeetCode] First Bad Version - 二分查找
  2. 数据分析的思维
  3. 二分查找算法
  4. 二分查找(个人笔记)
  5. 二分搜索非递归和递归算法
  6. Vue 超清晰思维导图,带你详细梳理知识点
  7. 高效掌握新技能的树型思维
  8. D. Decrease the Sum of Digits (思维问题+构造)Codeforces Ro