Code Jam Kickstart Round B 2018 题解

发表于 分类于 阅读次数：

这套题偏难 _(:з」∠)_

A. No Nine

求 [L, R] 的合法数字个数，可以转化为求 [1, x] 的合法数字个数。

不能有数字 9，也就是只允许数字 0～8，这就相当于九进制数，即 [1, x] 的不含 9 的数字个数有 base9(x) 个（x 为不含 9 的十进制数）。而且每连续 9 个不含 9 的数字里，有且只有一个被 9 整除的数（九进制下末位为 0 的数）。因此先把 x 的末位变成 0，让剩余的不含 9 的数字个数能被 9 整除，答案为 brute_force([x - x % 10, x]) + 8 / 9 * base9(x - x % 10)，两部分分别对应代码里的 ret1 和 ret2。

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
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

#define randomize srand((unsigned)time(NULL))
#define random(x) ((rand() * (rand() + rand())) % (x))
#define ms(x, y) memset(x, y, sizeof(x))
#define mc(x, y) memcpy(x, y, sizeof(x))

int T;

long long f(long long x) {
    long long ret1 = 0;
    while (x % 10) {
        if (x % 9 != 0) ++ret1;
        --x;
    }
    if (x % 9 != 0) ++ret1; // ending 0
    long long ret2 = 0, base = 1;
    while (x) {
        ret2 = ret2 + base * (x % 10);
        x /= 10;
        base *= 9;
    }
    return ret1 + ret2 / 9 * 8;
}

bool check(long long x) {
    if (x % 9 == 0) return false;
    while (x) {
        if (x % 10 == 9) return false;
        x /= 10;
    }
    return true;
}

long long bf(long long a, long long b) {
    long long ret = 0;
    for (auto i = a; i <= b; ++i)
        if (check(i)) {
//            cout << i << endl;
            ++ret;
        }
    return ret;
}

int main() {
    cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        long long F, L;
        cin >> F >> L;
        cout << "Case #" << cs << ": " << f(L) - f(F) + 1 << endl;
//        cout << "Case #" << cs << ": " << bf(F, L) << endl;
    }

    return 0;
}

B. Sherlock and the Bit Strings

关键信息 Bi - Ai ≤ 15，递推记录最近的 16 位，f[i][j] 表示前 i 位已确定，并且最后 16 位为 j（j ≤ 2^16）的可行方案数。从后往前（i 从大到小）递推，递推式为 f[i][j] = f[i + 1][shl1[j]] + f[i + 1][shl1[j] ^ 1]，shl1[j] 和 shl1[j]^1 分别为 j 去掉首位、末尾添加 0 或 1 的状态（保持 16 位）。

对于每个限制 [Ak, Bk, Ck]，只需要在求 f[i][j], i = Bk 的时候判断即可，保证不合法的方案最终不会传递到前面。

时间复杂度为 O(2 ^ 16 * (n + k))，空间复杂度为 O(2 ^ 16 * n)。

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
79
80
81
82
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

#define randomize srand((unsigned)time(NULL))
#define random(x) ((rand() * (rand() + rand())) % (x))
#define ms(x, y) memset(x, y, sizeof(x))
#define mc(x, y) memcpy(x, y, sizeof(x))

const int MAXN = 100 + 2;
const long long MAXP = 1e18;

int cnt[1 << 16], shl1[1 << 16];
int T, n, k;
long long p;
vector<pair<int, int>> limits[MAXN];
long long f[MAXN][1 << 16];

inline bool check(int pos, int status) {
    for (auto limit : limits[pos])
        if (cnt[status & ((1 << limit.first) - 1)] != limit.second)
            return false;
    return true;
}

int main() {
    cnt[0] = shl1[0] = 0;
    for (int i = 1; i < 1 << 16; ++i) {
        cnt[i] = cnt[i >> 1] + (i & 1); // number of 1
        shl1[i] = (i << 1) & ((1 << 16) - 1); // shift left ignoring the first bit
    }

    cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        cin >> n >> k >> p;
        for (int i = 1; i <= n; ++i)
            limits[i].clear();
        for (int i = 0; i < k; ++i) {
            int a, b, c;
            cin >> a >> b >> c;
            limits[b].emplace_back(make_pair(b - a + 1, c)); // (length, count)
        }

        ms(f, 0);
        for (int j = 0; j < 1 << 16; ++j)
            if (check(n, j))
                f[n][j] = 1;
        for (int i = n - 1; i > 0; --i)
            for (int j = 0; j < 1 << 16; ++j)
                if (check(i, j)) {
                    f[i][j] = f[i + 1][shl1[j]] + f[i + 1][shl1[j] ^ 1];
                    if (f[i][j] > MAXP) f[i][j] = MAXP + 1;
                }

        cout << "Case #" << cs << ": ";
        for (int i = 1, j = 0; i <= n; ++i, j = shl1[j])
            if (p <= f[i][j]) {
                cout << '0';
            } else {
                p -= f[i][j];
                j ^= 1;
                cout << '1';
            }
        cout << endl;
    }

    return 0;
}

C. King’s Circle

首先必须想好怎样的三个点可以形成矩形：

  1. 其中两点横坐标或纵坐标相等可以形成矩形；
  2. 从左向右排列，第二个点最高或最低（形如 ‘⋁’ 或 ‘⋀’），可以形成矩形；
  3. 横坐标从小到大排列下，只有纵坐标严格递增或严格递减的情况，才不可以形成矩形，且只有这一种不可以形成矩形的情况。

3 的情况比 1 和 2 的情况更好判断，于是把答案转化为 C(n, 3) - 不可以形成矩形的三点集数目。

考虑每个点 p，从它往四个方向扩展的点集分别记为 n1、n2、n3 和 n4，如下图所示：

{n1 里的任意一点, p, n3 里的任意一点} 和
{n2 里的任意一点, p, n4 里的任意一点} 的三点集不可以形成矩形，这里共有 |n1| * |n3| + |n2| * |n4| 种方案。

这种多维范围查询，可以使用 range tree 这一数据结构，可以参考这个资料：http://www.cs.wustl.edu/~taoju/cse546/lectures/Lecture21_rangequery_2d.pdf。时间复杂度 O(n * log(n) * log(n))，可以降到 O(n * log(n))。

以下版本是原生的 range tree，运行 large-practice 数据需要大概 5 分钟。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <memory>
#include <utility>
#include <algorithm>
#include <memory>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

#define randomize srand((unsigned)time(NULL))
#define random(x) ((rand() * (rand() + rand())) % (x))
#define ms(x, y) memset(x, y, sizeof(x))
#define mc(x, y) memcpy(x, y, sizeof(x))

const int MAXN = 500000 + 10;
const int MAXM = 1000000 + 10;

struct point_t {
    int x, y;
};

struct range_tree_node_t {
    int size; // # of node
    int l, r; // value range
    int mid; // <= mid, left; > mid, right
    unique_ptr<range_tree_node_t> left, right;
    unique_ptr<range_tree_node_t> ytree;

    range_tree_node_t() {
        left = nullptr;
        right = nullptr;
        ytree = nullptr;
    }
};

int T, n, m;
point_t p[MAXN];
int px[MAXN], py[MAXN];
unique_ptr<range_tree_node_t> xtree;
int tmpx[MAXN], tmpy[MAXN];

void build_range_ytree(unique_ptr<range_tree_node_t> &ytree, int l, int r) {
    if (l >= r) return;
//    printf("build_range_ytree %d %d\n", l, r);
    ytree = make_unique<range_tree_node_t>();
    ytree->size = r - l;
    ytree->l = py[l];
    ytree->r = py[r - 1];
    int m = 0;
    tmpy[m++] = py[l]; // unique y
    for (int i = l + 1; i < r; ++i)
        if (py[i] != tmpy[m - 1])
            tmpy[m++] = py[i];
    ytree->mid = tmpy[(m - 1) >> 1]; // median
    if (m > 1) {
        int mid = l;
        for (int i = l; i < r; ++i)
            if (py[i] <= ytree->mid)
                mid = i;
            else
                break;
        build_range_ytree(ytree->left, l, mid + 1);
        build_range_ytree(ytree->right, mid + 1, r);
    }
}

void build_range_xtree(unique_ptr<range_tree_node_t> &xtree, int l, int r) {
    if (l >= r) return;
//    printf("build_range_xtree %d %d\n", l, r);
    xtree = make_unique<range_tree_node_t>();
    xtree->size = r - l;
    xtree->l = px[l];
    xtree->r = px[r - 1];
    int m = 0;
    tmpx[m++] = px[l]; // unique x
    for (int i = l + 1; i < r; ++i)
        if (px[i] != tmpx[m - 1])
            tmpx[m++] = px[i];
    xtree->mid = tmpx[(m - 1) >> 1]; // median
    if (m > 1) {
        int mid = l;
        for (int i = l; i < r; ++i)
            if (px[i] <= xtree->mid)
                mid = i;
            else
                break;
        build_range_xtree(xtree->left, l, mid + 1);
        build_range_xtree(xtree->right, mid + 1, r);

        // merge sort on y
        memcpy(tmpy + l, py + l, sizeof(int) * (r - l));
        m = l;
        int i1 = l, i2 = mid + 1;
        while (m < r) {
            if (i2 >= r || i1 < mid + 1 && tmpy[i1] < tmpy[i2])
                py[m++] = tmpy[i1++];
            else
                py[m++] = tmpy[i2++];
        }
    }
    build_range_ytree(xtree->ytree, l, r);
}

int queryy(unique_ptr<range_tree_node_t> &ytree, int lx, int rx, int ly, int ry) {
    if (ytree->l > ry || ytree->r < ly) return 0;
    if (ly <= ytree->l && ytree->r <= ry)
        return ytree->size;
    return queryy(ytree->left, lx, rx, ly, ry) + queryy(ytree->right, lx, rx, ly, ry);
}

int queryx(unique_ptr<range_tree_node_t> &xtree, int lx, int rx, int ly, int ry) {
    if (xtree->l > rx || xtree->r < lx) return 0;
    if (lx <= xtree->l && xtree->r <= rx)
        return queryy(xtree->ytree, lx, rx, ly, ry);
    return queryx(xtree->left, lx, rx, ly, ry) + queryx(xtree->right, lx, rx, ly, ry);
}

int main() {
    cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        int a, b, c, d, e, f, m;
        cin >> n >> p[0].x >> p[0].y >> a >> b >> c >> d >> e >> f >> m;
        for (int i = 1; i < n; ++i) {
            p[i].x = ((long long) a * p[i - 1].x + (long long) b * p[i - 1].y + c) % m;
            p[i].y = ((long long) d * p[i - 1].x + (long long) e * p[i - 1].y + f) % m;
        }

        sort(p, p + n, [](const point_t &a, const point_t &b) {
            return a.x < b.x || a.x == b.x && a.y < b.y;
        });
        for (int i = 0; i < n; ++i) {
            px[i] = p[i].x;
            py[i] = p[i].y;
        }
        build_range_xtree(xtree, 0, n);

        long long ans = (long long) n * (n - 1) * (n - 2) / 3 / 2; // C(n, 3)
//        n2 | n1
//        ---+---
//        n3 | n4
        for (int i = 0; i < n; ++i) {
            int n1 = queryx(xtree, p[i].x + 1, MAXM, p[i].y + 1, MAXM);
            int n2 = queryx(xtree, -MAXM, p[i].x - 1, p[i].y + 1, MAXM);
            int n3 = queryx(xtree, -MAXM, p[i].x - 1, -MAXM, p[i].y - 1);
            int n4 = queryx(xtree, p[i].x + 1, MAXM, -MAXM, p[i].y - 1);
            ans -= (long long) n1 * n3 + (long long) n2 * n4;
        }
        cout << "Case #" << cs << ": " << ans << endl;
    }

    return 0;
}

以下版本利用查询特点进行优化，运行 large-practice 数据需要大概 50 秒。优化的地方包括：

  1. 由于只有包含端点的查询，第二维 ytree 不使用树结构，使用有序数组；
  2. 由于查询的 x 有序（升序），手动维护相关的 xtree 节点（xnode 数组）。
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <memory>
#include <utility>
#include <algorithm>
#include <memory>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

#define randomize srand((unsigned)time(NULL))
#define random(x) ((rand() * (rand() + rand())) % (x))
#define ms(x, y) memset(x, y, sizeof(x))
#define mc(x, y) memcpy(x, y, sizeof(x))

const int MAXN = 500000 + 10;
const int MAXM = 1000000 + 10;

struct point_t {
    int x, y;
};

struct range_tree_node_t {
    int size; // # of node
    int l, r; // value range
    int mid; // <= mid, left; > mid, right
    shared_ptr<range_tree_node_t> left, right, papa;
    vector<int> y;

    range_tree_node_t(shared_ptr<range_tree_node_t> _papa) {
        left = nullptr;
        right = nullptr;
        papa = _papa;
    }
};

int T, n, m;
point_t p[MAXN];
vector<int> px, py;
shared_ptr<range_tree_node_t> xtree;
int tmpx[MAXN], tmpy[MAXN];
shared_ptr<range_tree_node_t> dest[MAXN];
vector<shared_ptr<range_tree_node_t>> xnode;

void build_range_xtree(shared_ptr<range_tree_node_t> &xtree, shared_ptr<range_tree_node_t> papa, int l, int r) {
    if (l >= r) return;
//    printf("build_range_xtree %d %d\n", l, r);
    xtree = make_shared<range_tree_node_t>(papa);
    xtree->size = r - l;
    xtree->l = px[l];
    xtree->r = px[r - 1];
    int m = 0;
    tmpx[m++] = px[l]; // unique x
    for (int i = l + 1; i < r; ++i)
        if (px[i] != tmpx[m - 1])
            tmpx[m++] = px[i];
    xtree->mid = tmpx[(m - 1) >> 1]; // median
    if (m > 1) {
        int mid = l;
        for (int i = l; i < r; ++i)
            if (px[i] <= xtree->mid)
                mid = i;
            else
                break;
        build_range_xtree(xtree->left, xtree, l, mid + 1);
        build_range_xtree(xtree->right, xtree, mid + 1, r);

        // merge sort on y
        for (int i = l; i < r; ++i)
            tmpy[i] = py[i];
        m = l;
        int i1 = l, i2 = mid + 1;
        while (m < r) {
            if (i2 >= r || i1 < mid + 1 && tmpy[i1] < tmpy[i2])
                py[m++] = tmpy[i1++];
            else
                py[m++] = tmpy[i2++];
        }
    } else
        dest[l] = xtree;
    xtree->y = vector<int>(py.begin() + l, py.begin() + r);
}

inline int larger_than(const vector<int> &a, int x) {
    return a.end() - upper_bound(a.begin(), a.end(), x);
}

inline int smaller_than(const vector<int> &a, int x) {
    return lower_bound(a.begin(), a.end(), x) - a.begin();
}

int main() {
    cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        int a, b, c, d, e, f, m;
        cin >> n >> p[0].x >> p[0].y >> a >> b >> c >> d >> e >> f >> m;
        for (int i = 1; i < n; ++i) {
            p[i].x = ((long long) a * p[i - 1].x + (long long) b * p[i - 1].y + c) % m;
            p[i].y = ((long long) d * p[i - 1].x + (long long) e * p[i - 1].y + f) % m;
        }

        sort(p, p + n, [](const point_t &a, const point_t &b) {
            return a.x < b.x || a.x == b.x && a.y < b.y;
        });
        px.resize(n);
        py.resize(n);
        for (int i = 0; i < n; ++i) {
            px[i] = p[i].x;
            py[i] = p[i].y;
        }
        build_range_xtree(xtree, nullptr, 0, n);

        long long ans = (long long) n * (n - 1) * (n - 2) / 3 / 2; // C(n, 3)
//        n2 | n1
//        ---+---
//        n3 | n4
        int n1, n2, n3, n4;
        xnode.clear();
        for (int i = 0, j = 0; i < n; i = j) {
            while (j < n && p[j].x == p[i].x)
                ++j;

            for (int k = i; k < j; ++k) {
                n2 = n3 = 0;
                for (auto xn : xnode) {
                    n2 += larger_than(xn->y, p[k].y);
                    n3 += smaller_than(xn->y, p[k].y);
                }
                n1 = larger_than(py, p[k].y) - n2 - (j - k - 1);
                n4 = smaller_than(py, p[k].y) - n3 - (k - i);
                ans -= (long long) n1 * n3 + (long long) n2 * n4;
            }

            xnode.emplace_back(dest[i]);
            while (xnode.size() >= 2 && xnode[xnode.size() - 1]->papa == xnode[xnode.size() - 2]->papa) {
                xnode[xnode.size() - 2] = xnode[xnode.size() - 1]->papa;
                xnode.pop_back();
            }
        }
        cout << "Case #" << cs << ": " << ans << endl;
    }

    return 0;
}
0%