UPC 2223: A-Number and B-Number（数位DP+二分）

积累点：

1: (l&r)+((l^r)>>) == (l+r)/2 
2: 注意判断现在是否有限制。当枚举下一个量时，是(isQuery && j==end),不要搞错。

传送门：http://acm.upc.edu.cn/problem.php?id=2223

题意：

能被7整除或者含7的数称为A-Number，所有A-Number从小到大写好，下标编号（从1开始），去掉那些下标为A-Number的数，剩下的数称为B-Number。求第N个B-Number是多少。

思路：

求A-Number就是简单的数位DP。

dp[i][mod] 表示所有i位数中，%7==mod 的数的个数

dp[i][mod] = (j != 7) dp[i-1][(mod-(j*10^i-1)%7+7)%7]

(j == 7) 10^i-1(nowx%10^i-1+1)

(j=0~9(end))

之后二分答案就行了。[0~B]包含 cal(B) - cal(cal(B)) 个B-Number。(B包含的ANumber的数目，就是下标最大。这么大的下标范围内有多少ANumber，减掉，剩下就是BNumber的数量）

二分的时候注意二分到最小的那个。就是说。二分的可能是这样

7 7 7 8 8 8

如果查的是8, 则这时候应该二分到第一个8那个位置。

代码：

#include <cstdio>

#include <cstring>

long long dp[][];

int num[];

long long nowx;

long long dfs(int i, int mod, bool isQuery) {

    if (i == ) {

        return mod == ;

    }

    long long &nowdp = dp[i][mod];

    if (!isQuery && ~nowdp) {

        return nowdp;

    }

    int end = isQuery?num[i]:;

    long long ans = ;

    long long ten = ;

    for (int k = ; k < i-; k++) ten *= ;

    for (int j = ; j <= end; j++) {

        if (j == ) {

            ans += (isQuery&&j==end)?((nowx%ten)+):ten;  // 这一句要小心。

        } else {

            ans += dfs(i-, (mod-(j*ten)%+)%, isQuery && j == end);

        }

    }

    if (!isQuery) nowdp = ans;

    return ans;

}

long long cal(long long x) {

    nowx = x;

    int len = ;

    if (x == ) return ;

    while (x) {

        num[++len] = x%;

        x/=;

    }

    return dfs(len, , true)-; // 减掉0

}

long long solve(long long number) {

    long long l = ;

    long long r = 10e19;

    while (l<r) {

        long long mid = (l&r)+((l^r)>>);

        long long Anum = cal(mid);

        long long Bnum = Anum - cal(Anum);

        if (Bnum >= number) r = mid;

        else l = mid+;

    }

    return l;

}

int main(){

    long long n;

    memset(dp, -, sizeof(dp));

    while (scanf("%lld", &n) != EOF) {

        printf("%lld\n", solve(n));

    }

}

巴特西

UPC 2223: A-Number and B-Number（数位DP+二分）

最新文章

热门文章