kick start 2018 Round B

Posted on | In | 阅读
  1. No Nine

  1. No Nine

    给定一个区间[x1, x2]，确定区间内有多少个不包含9且不被9整除的数，由于两个端点都是非9数，就是求[0, x1], [0, x2]的差+1。

    如果只找不包含9的数。其实就是找如果把九进制数当作十进制来看的话，落在这个区间内的九进制数有多少个0-8，10-18，……

    从十位(第1位)数开始往后，每位下面都包含完整9^i个数

    算出来有多少个不包含9的数之后，就要去掉9的倍数，最后正好每组9个数中有1个是9的倍数

    例如12345，剔除包含9的数之后剩下9个一组的00000-00008，00010-00018，……，12330-12338。每一组必定只有一个9的倍数，所以*8/9

    最后再加上12340-12345中不是9的倍数的数就行。

C++ 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
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

long long solve(long long n) {
    long long ans = 0;
    long long last_ans = 0;
    long long n_0 = n % 10;
    for(long long i = 0; i <= n_0; ++i) {
        if((n - i) % 9 != 0) {
            ++last_ans;
        }
    }
    long long cnt = 9;
    n /= 10;
    while(n > 0) {
        long long pos = n % 10;
        ans += pos * cnt;
        n /= 10;
        cnt *= 9;
    }
    ans = ans / 9 * 8;
    return last_ans + ans;
}

int main() {
    int t;
    cin >> t;
    long long f, l;
    for(int c = 1; c <= t; ++c) {
        cin >> f >> l;
        long long ans = solve(l) - solve(f) + 1;
        printf("Case #%d: %lld\n", c, ans);
    }
    return 0;
}

  1. Sherlock and the Bit Strings

    给定一个01字符串的长度以及一些限制(a, b, c)，保证[a, b]区间内的1的个数恰好为c，同时返回满足条件的第p个字典序解。

    用动态规划，dp[i][j]代表前i个bit确定并且前i个中最后15个bit（题目中说b-a不超过15）与j的二进制表示相同时解的个数。用一个limits数组记录每个位置为右端点b的时候限制的区间长度（b-a+1）和限制数c。每次检查的时候都将送进来的j的后b-a+1位与1然后计算个数。

    初始化：dp[n][j] = 1 if 不违背限制 else 0

    递推：dp[i][j] = dp[i+1][(j<<1)&((1<<16) - 1)] + dp[i+1][(j<<1))&((1<<16) - 1) + 1] if j不违背限制 else 0

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <string.h>
#define N 100


using namespace std;

const long long max_p = 1e18;
vector<pair<int, int>> limits[N+1];
long long dp[N+1][1<<16];
int cnt[1<<16];
int shl[1<<16];

bool check(int pos, int status) {
    for(int i = 0; i < limits[pos].size(); ++i) {
        if(cnt[status & ((1 << limits[pos][i].first) - 1)] != limits[pos][i].second) {
            return false;
        }
    }
    return true;
}


int main() {
    cnt[0] = 0;
    shl[0] = 0;
    for(int i = 1; i < (1<<16); ++i) {
        cnt[i] = cnt[i>>1] + (i & 1);
        shl[i] = (i << 1) & ((1 << 16) - 1);
    }

    int t, n, k, a, b, c;
    long long p;
    scanf("%d", &t);
    for(int ca = 1; ca <= t; ++ca) {
        scanf("%d%d%lld", &n, &k, &p);
        for(int i = 1; i <= n; ++i) {
            limits[i].clear();
        }
        for(int i = 0; i < k; ++i) {
            scanf("%d%d%d", &a, &b, &c);
            limits[b].push_back(make_pair(b-a+1, c));
        }
        memset(dp, 0, sizeof(dp));
        for(int j = 0; j < (1<<16); ++j) {
            if(check(n, j)) {
                dp[n][j] = 1;
            }
        }
        for(int i = n-1; i >= 1; --i) {
            for(int j = 0; j < (1<<16); ++j) {
                if(check(i, j)) {
                    dp[i][j] = dp[i+1][shl[j]] + dp[i+1][shl[j] ^ 1];
                    if(dp[i][j] > max_p) {
                        dp[i][j] = max_p+1;
                    }
                }
            }
        }

        printf("Case #%d: ", ca);
        for(int i = 1, j = 0; i <= n; ++i, j = shl[j]) {
            if(dp[i][j] >= p) {
                printf("0");
            }else {
                p -= dp[i][j];
                j ^= 1;
                printf("1");
            }
        }
        printf("\n");

    }
    return 0;
}