srm 546

发表于   |   分类于   |  

250

Solution

考虑奇偶性，每次定一个可以变成该数的上下界，按二进制位考虑即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct KleofasTail {
    LL gao(LL x, LL k) {
        if (k > x)  return 0;
        if (k <= 1) return x - k + 1;
        LL kk = k + (k % 2 == 0);
        LL t = 0;
        while (k <= x) {
            t += min(x, kk) - k + 1;
            k <<= 1;
            kk = (kk << 1 | 1);
        }
        return t;
    }
    long long countGoodSequences(long long K, long long A, long long B) {
        return gao(B, K) - gao(A - 1, K);              
    }
};

500

Description

求满足大于$A(A\le 10^{15})$的且$digit1$至少出现$count1$次，$digit2$至少出现$count2次$的最小的数是多少？
$(count1+count2\le 15,digit1,digit2\le 10)$

Solution

很容易想到数位$dp$,常见数位$dp$套路，用一个$f$表示当前数是否与最小值相等，还有$cnt1个x1,cnt2个x2$没有用，是否成立。
正常转移即可，注意一点，除了$x1,x2,lim,lim+1$以外，其他数是没什么意义的，$dp$即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>//dp
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
int a[16];
LL ans;
struct FavouriteDigits {
    bool dfs(int p, bool f, int x1, int cnt1, int x2, int cnt2, LL now) {
        if (p == -1) {
            if (cnt1 <= 0 && cnt2 <= 0) {
                ans = now;
                return 1;
            }
            return 0;
        }
        int lim = f ? a[p] : 0;
        for (int i = lim; i <= 9; ++i) {
            if (f) {
                if (!(i == lim || i == x1 || i == x2 || i == lim + 1))  continue;
            }
            else {
                if (!(i == lim || i == x1 || i == x2))  continue;
            }
            int d1 = cnt1 - (i == x1);
            int d2 = cnt2 - (i == x2);
            if (!now && !x1)    d1 = cnt1;
            if (dfs(p - 1, f & (i == lim), x1, d1, x2, d2, now * 10 + i))   return 1;
        }
        return 0;
    }
    long long findNext(long long N, int x1, int cnt1, int x2, int cnt2) {
        if (x1 > x2)    swap(x1, x2), swap(cnt1, cnt2);
        int p = 0;
        while (N) {
            a[p++] = N % 10;
            N /= 10;
        }
        p = max(p, cnt1 + cnt2);
        dfs(p, 1, x1, cnt1, x2, cnt2, 0);
        return ans;
    }
};