【题解】Google Kick Start

Posted on Edited on In Disqus:

老年人做点笔试题算了。

注：一切以 Hard 模式为准。

写在最前

文件头

有点长，就不重复贴了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------

2019

Round E

Cherries Mesh

最小生成树。需要的边的条数是 n-1，希望在其中尽可能利用黑边，数一下有多少黑边是有效的即可。

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
const int N = 1e5 + 100;

int fa[N];
int findset(int x) { return fa[x] == -1? x : fa[x] = findset(fa[x]); }

int solve() {
    int n, m; cin >> n >> m;
    fill(fa, fa + n + 1, -1);
    int cnt = 0;
    FOR (_, 0, m) {
        int u, v; scanf("%d%d", &u, &v);
        int fu = findset(u), fv = findset(v);
        if (fu != fv) {
            ++cnt;
            fa[fu] = fv;
        }
    }
    return 2 * (n - 1) - cnt;
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: %d\n", Ca, solve());
    }
}

Code-Eat Switcher

判断点是否在凸包内。先不考虑把一个 time slot 分割的情况，肯定是按照某一方（比如 coding）的性价比排序，然后一侧全是 coding，另一侧全是 eating。每一个分界线的位置对应一个点，考虑所有点，把相邻的连起来，就是所有最优解构成的凸包。剩下的问题就是如何判断一个点是否在凸包内了，找出这个点 x 轴上附近的两个点（二分搜索），看是否在那两个点构成的直线的下方（叉积判正负）。

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
const int N = 1e5 + 100;
struct P {
    LL c, e;
};
P p[N];

bool test(const P& a, const P& b, LL c, LL e) {
    LL ax = a.c - c, ay = a.e - e;
    LL bx = b.c - c, by = b.e - e;
    return ax * by - bx * ay <= 0;
}

void solve() {
    int D, S; cin >> D >> S;
    FOR (i, 0, S) scanf("%lld%lld", &p[i].c, &p[i].e);
    sort(p, p + S, [](const P& a, const P& b) {
        return a.c * b.e > a.e * b.c;
    }); // coding up, eating down
    LL se = 0, sc = 0;
    FOR (i, 0, S) se += p[i].e;
    vector<P> c; c.push_back({sc, se});
    FOR (i, 0, S) {
        se -= p[i].e; sc += p[i].c;
        c.push_back({sc, se});
    }

    FOR (i, 0, D) {
        LL qe, qc; scanf("%lld%lld", &qc, &qe);
        auto it = lower_bound(c.begin(), c.end(), P{qc, qe}, [](const P& a, const P& b) {
            return a.c < b.c;
        });
        if (it == c.end()) { putchar('N'); continue; }
        if (it == c.begin()) { putchar(it->e >= qe ? 'Y' : 'N'); continue; }
        auto l = it, r = it;
        --l;
        putchar(test(*l, *r, qc, qe) ? 'Y' : 'N');
    }
    puts("");
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Street Checker

数论题，求 [L, R] 区间内有多少数字的奇因子个数和偶因子个数差的绝对值不超过 2。

为了寻找满足要求的数，考虑一个数的 2 因子个数：

  • 如果个数为 0：那么这个数必须是素数，有且仅有两个奇因子。
  • 如果个数为 1：那么所有的奇因子乘 2 之后就能刚好对应一个偶因子，数量相等，满足要求。
  • 如果个数为 2：那么偶因子的数量是奇因子的两倍，奇因子数量可以为 1 或者 2，2 的时候这个数就是素数的 4 倍，1 的时候就是 4。
  • 如果个数为 3：那么这个数就是 8。

唯一的难点就是怎么求一个区间范围内的素数，方法是用 \(\sqrt R\) 内的素数去筛。

注：一开始把 \(R - L \le 10^5\) 看成 Test Set 1 限定的条件了，还在想怎么会考亚线性筛。

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
const LL p_max = 1E6 + 100;
LL pr[p_max], p_sz;
void get_prime() {
    static bool vis[p_max];
    FOR (i, 2, p_max) {
        if (!vis[i]) pr[p_sz++] = i;
        FOR (j, 0, p_sz) {
            if (pr[j] * i >= p_max) break;
            vis[pr[j] * i] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}

const int N = 1E5 + 100;
bool f[N];
set<LL> S;

void count(LL L, LL R, LL multiplier = 1) {
    if (L > R) return;
    fill(f, f + R - L + 1, true);
    FOR (i, 0, p_sz) {
        LL p = pr[i];
        if (p * p > R) break;
        FOR (j, max((L + p - 1) / p, 2LL), R / p + 1) {
            f[j * p - L] = false;
        }
    }
    FOR (i, L, R + 1) if (f[i - L]) S.insert(i * multiplier);
}

void solve() {
    S.clear();
    LL L, R; cin >> L >> R;
    count(L, R);
    FOR (i, L, R + 1) if ((i & 3) == 2) S.insert(i);
    count((L + 3) / 4, R / 4, 4);
    if (L <= 4 && 4 <= R) S.insert(4);
    if (L <= 8 && 8 <= R) S.insert(8);
    dbg(S);
    cout << S.size() << endl;
}


int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    get_prime();
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Round F

Flattening

\(f[i][k]\) 表示前 \(i\) 个数中相邻不同的数量不超过 \(k\) 的最少操作数，有转移式 \(f[i][k] = \min_{j<i} f[j][k -1]+m(j+1,i)\)，其中 \(m(l, r)\) 表示把 \(l\) 和 \(r\) 之间的 \(a[i]\) 变为相同需要的最小数，可以线性预处理。

还有一种思维复杂度和时间复杂度更高的做法，\(f[i][k][last]\) 表示前 \(i\) 个数相邻不同的数量小于 \(k\) 且修改后 \(a[i]\) 的值是 \(last\) 的最小操作数，转移就有点复杂了。

官方题解中有一个观察，修改操作可以用删除替换，不过好像区别不大？官方题解中还提供了一种复杂度更低的做法，二分答案，然而我并不知道怎么判是否可行（我看了差不多十份代码也没找到用二分的）。

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
const int N = 100 + 5, M = 1000 + 5;
int a[N], f[N][N];
int d[M], m[N];

void up(int& x, int y) { x = min(x, y); }

void solve() {
    int n, K; cin >> n >> K;
    FOR (i, 0, n) scanf("%d", a + i);
    memset(f, 0x3f, sizeof f);
    FOR (i, 0, K + 1) f[0][i] = 0;
    FOR (i, 1, n) {
        int _m = 0;
        FORD (j, i, -1) {
            _m = max(_m, d[a[j]]++);
            m[j] = (i - j) - _m;
        }
        FOR (j, 0, i + 1) --d[a[j]];
        f[i][0] = m[0];
        FOR (k, 1, K + 1) {
            f[i][k] = f[i][k - 1];
            FOR (j, 0, i)
                up(f[i][k], f[j][k - 1] + m[j + 1]);
        }
    }
    printf("%d\n", f[n - 1][K]);
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Teach Me

考虑问题的反面，有多少对不能 mentor。对于一个人 x，y 不能 mentor 他的充要条件是 y 是 x 的子集。然后枚举子集，哈希后用 map 统计一下就好了。

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
const int N = 5E4 + 100;
map<LL, int> mp;

void solve() {
    mp.clear();
    vector<LL> a, x;

    int n, S; cin >> n >> S;
    FOR (i, 0, n) {
        x.clear();
        int k; scanf("%d", &k);
        FOR (_, 0, k) { int t; scanf("%d", &t); x.push_back(t); }
        sort(x.begin(), x.end());
        FOR (j, 1, 1 << x.size()) {
            LL v = 0;
            FOR (k, 0, x.size()) if ((j >> k) & 1) v = v * 1001 + x[k];
            ++mp[v];
            if (j == (1 << x.size()) - 1) a.push_back(v);
        }
    }
    LL ans = 0;
    for (LL& v: a) ans += n - mp[v];
    cout << ans << endl;
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Spectating Villages

经典树形 DP，f[u][0~2] 表示 u 这个节点：

  • 0 - 自己没选：可以从子节点的 0 或者 1 状态转移，无额外约束。
  • 1 - 被子节点选了：可以从子节点的 0 或者 1 或者 2 转移过来，但至少有一个 2。这个稍微有点 trick，先求出 012 状态的最大值以及从 012 坍缩成 2 的最小损失，计算时两者相减就好了。
  • 2 - 自己选了并导致父亲也要被选：从子节点 0 或者 1 或者 2 转移过来，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
const int N = 1e5 + 100;

int w[N];
vector<int> G[N];
LL f[N][3];  // 0 - 自己没选，1 - 被子节点选了，2 - 自己选了，导致父节点也被选

void go(int u, int fa) {
    LL sum = 0, m1 = 1e18;
    f[u][2] = w[u];
    for (int& v: G[u]) {
        if (v == fa) continue;
        go(v, u);
        LL s = max(f[v][0], max(f[v][1], f[v][2]));
        m1 = min(m1, s - f[v][2]);
        sum += s;
        f[u][2] += max(f[v][0] + w[v], max(f[v][1], f[v][2]));
        f[u][0] += max(f[v][0], f[v][1]);
    }
    f[u][1] = sum - m1 + w[u];
    dbg(u, f[u][0], f[u][1], f[u][2]);
}

LL solve() {
    int n; cin >> n;
    FOR (i, 0, n + 1) {
        f[i][0] = 0;
        f[i][1] = f[i][2] = -1e18;
        G[i].clear();
    }

    FOR (i, 1, n + 1) scanf("%d", w + i);
    FOR (_, 1, n) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    go(1, -1);
    return *max_element(f[1], f[1] + 3);
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: %lld\n", Ca, solve());
    }
}

Round G

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e02

Book Reading

考虑被撕掉的每一页，当询问是页数的因数时会减少对答案的贡献。预处理每个数的因数，统计一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 1E5 + 100;
vector<int> a[N];
int c[N], d[N];

int main() {
    FOR (i, 1, N)
        for (int j = i; j < N; j += i)
            a[j].push_back(i);
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        int n, m, Q; cin >> n >> m >> Q;
        FOR (i, 0, m) scanf("%d", d + i);
        FOR (i, 0, m) for (int t: a[d[i]]) ++c[t];
        LL ans = 0;
        FOR (_, 0, Q) {
            int x; scanf("%d", &x);
            ans += n / x - c[x];
        }
        printf("%lld\n", ans);
        FOR (i, 0, m) for (int t: a[d[i]]) --c[t];
    }
}

The Equation

从高到低枚举答案二进制的每一位，如果枚举到的这一位能是 1，那么就放 1，否则只能放 0。判断某一位是不是能放 1，只要让剩下的那些没确定的位放最优（也就是能让异或和结果尽可能小的），再判断是否满足条件即可。

注意数据范围，不要在运算过程中爆 long long。

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
const int N = 1000 + 100, C = 50;
LL c[C], d[C];

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        memset(c, 0, sizeof c);
        printf("Case #%d: ", Ca);
        LL n, M; scanf("%lld%lld", &n, &M);
        FOR (_, 0, n) {
            LL t; scanf("%lld", &t);
            FOR (i, 0, C) if ((t >> i) & 1) ++c[i];
        }
        FOR (i, 0, C) d[i] = min(c[i], n - c[i]) << i;
        FOR (i, 1, C) d[i] += d[i - 1];
        if (d[C - 1] > M) { puts("-1"); continue; }
        LL ans = 0, S = 0;
        FORD (i, C - 1, -1) {
            if (S + ((n - c[i]) << i) + (i ? d[i - 1] : 0) <= M) {
                ans += 1LL << i;
                S += (n - c[i]) << i;
            } else S += c[i] << i;
        }
        assert(S <= M);
        printf("%lld\n", ans);
    }
}

Shifts

\(O(3^{20})\) 显然不怎么行，考虑两边相遇。分别处理 \(O(3^{10})\)，把每种组合看成坐标的一个点，对于左边的每一个点，需要知道在右边的某个矩形里的点的个数。做法就是按照一维排序，另一维用数据结构维护，代码中用了 pb_ds 里的平衡树，离散化用树状数组或者用 cdq 分治也行。

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
const int N = 20 + 10;
using VLL = vector<pair<LL, LL>>;
VLL L, R;
pair<LL, LL> a[N];

void go(const VLL& a, pair<LL, LL> s, VLL& ret, int k) {
    if (k == a.size()) { ret.push_back(s); return; }
    go(a, {s.first + a[k].first, s.second + a[k].second}, ret, k + 1);
    go(a, {s.first, s.second + a[k].second}, ret, k + 1);
    go(a, {s.first + a[k].first, s.second}, ret, k + 1);
}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using Tree = tree<pair<LL, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
Tree t;

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        L.clear(); R.clear(); t.clear();
        int n; LL H;
        cin >> n >> H;
        FOR (i, 0, n) scanf("%lld", &a[i].first);
        FOR (i, 0, n) scanf("%lld", &a[i].second);
        go(VLL(a, a + n / 2), {0, 0}, L, 0);
        go(VLL(a + n / 2, a + n), {0, 0}, R, 0);
        sort(L.begin(), L.end());
        sort(R.begin(), R.end(), greater<>());
        LL k = 0, ans = 0;
        int clk = 0;
        for (auto& x: L) {
            while (k < R.size() && R[k].first + x.first >= H) t.insert({R[k++].second, clk++});
            ans += k - t.order_of_key({H - x.second, -1});
        }
        cout << ans << endl;
    }
}

Round H

H-Index

方法1：无脑模拟，相比起方法2代码复杂度高了一些，但是思维复杂度很低。需要有一个支持边插入边查询求第 K 大，或者求小于某个数的数量的数据结构。代码中使用了树状数组。

方法2：不需要高级数据结构的做法，搞一个普通平衡树或者优先队列（小根堆），维护属于 H-Index 内的东西，如果偏小则略过，较大则插入并根据情况增加 H-Index 并删除较小的部分。

方法3：题解里说可以线性。想了想，只需要把方法2中的优先队列改成数组或者哈希表就好了。

方法1

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
const int M = 1e5 + 100;
namespace bit {
    LL c[M];
    inline int lowbit(int x) { return x & -x; }
    void add(int x, LL v) {
        for (int i = x; i < M; i += lowbit(i))
            c[i] += v;
    }
    LL sum(int x) {
        LL ret = 0;
        for (int i = x; i > 0; i -= lowbit(i))
            ret += c[i];
        return ret;
    }
}

void solve() {
    int n; cin >> n;
    int h = 0;
    vector<int> history;
    FOR (i, 0, n) {
        int v; scanf("%d", &v);
        history.push_back(v);
        bit::add(v, 1);
        while (i + 1 - bit::sum(h) >= h + 1) h += 1;
        printf("%d ", h);
    }
    for (int& v: history) bit::add(v, -1);
    puts("");
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    int n; cin >> n;
    int h = 0;
    priority_queue<int, vector<int>, greater<>> pq;
    FOR (i, 0, n) {
        int v; scanf("%d", &v);
        if (v > h) pq.push(v);
        h += pq.size() > h;
        while (!pq.empty() && pq.top() <= h) pq.pop();
        printf("%d ", h);
    }
    puts("");
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

方法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
    int n; cin >> n;
    int h = 0, sz = 0, cur = 0;
    unordered_map<int, int> mp;
    FOR (i, 0, n) {
        int v; scanf("%d", &v);
        if (v > h) { mp[v] += 1; ++sz; }
        if (sz > h) sz -= mp[++h];
        printf("%d ", h);
    }
    puts("");
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Diagonal Puzzle

考虑这样一种转化，每一条对角线作为方程的一个未知量，如果翻转就是 1，不操作就是 0。对于每一个格子，如果当前是黑色的，那么对应的两条对角线对应的变量异或和为 0（也就是要么都取要么都不取），如果是白色，那么异或和为 1（必须一个取一个不取）。

对于大小为 n * n 的方阵，得到了一组未知数个数为 2 * (2 * n - 1)，方程个数为 n * n 的异或方程组，最后需要在解空间内最小化所有未知量之和。

方法 2：如果光是求解的话，可以用 2-SAT 解决，现在需要最小化操作数。对于每一对强连通分量有两种选择，选择操作数较少的那种就好了。

方法 1：需要额外的观察，但不需要什么算法，实现起来也容易很多。这个方程组有一个特点，就是方程个数远大于未知数个数，如果假设其中某个（或者若干个）未知数的解的话，其它的未知数也迎刃而解，只需要考虑有没有矛盾就可以了。可以假定的未知量有很多，最合适的就是最长的对角线以及次长的对角线（同一方向），然后发现所有反向的对角线是否需要翻转就确定了，然后再检查一下光靠同向的其他对角线能否达到题目要求就行了，如果可以的话记录一下操作数。

方法 1

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
const int N = 100 * 2 + 5, INF = 1e5;
bool G[N][N];
bool GG[N][N];
char s[N];

int fix(int n, int x, int y) {
    int cnt = 0, sum = 0;
    while (x < n && y < n) {
        cnt += 1; sum += G[x][y];
        ++x; ++y;
    }
    if (cnt == sum) return 0;
    if (sum == 0) return 1;
    return INF;
}

void flip(bool& f) { f = !f; }

int check(int n, int op1, int op2) {
    memcpy(G, GG, sizeof G);
    int ans = op1 + op2;
    FOR (i, 0, n) {
        if (op1) flip(G[i][i]);
        if (!G[i][i]) {
            ++ans;
            FOR (j, 0, i + i + 1) {
                flip(G[j][i + i - j]);
            }
        }
    }
    FOR (i, 0, n - 1) {
        if (op2) flip(G[i][i + 1]);
        if (!G[i][i + 1]) {
            ++ans;
            FOR (j, 0, i + i + 2) {
                flip(G[j][i + i + 1 - j]);
            }
        }
    }
    FOR (i, 0, n) ans += fix(n, i, 0) + fix(n, 0, i);
    return ans;
}

void solve() {
    int n; cin >> n;
    FOR (i, 0, n) {
        scanf("%s", s);
        FOR (j, 0, n) GG[i][j] = s[j] == '#';
    }
    int ans = INF;
    FOR (op1, 0, 2) FOR (op2, 0, 2) ans = min(ans, check(n, op1, op2));
    cout << ans << endl;
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

方法2

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
const int N = 100 * 2 * 2 * 2 + 10;
vector<int> G[N], rG[N], vs;
int used[N], cmp[N];

void add_edge(int from, int to) {
    G[from].push_back(to);
    rG[to].push_back(from);
}

void dfs(int v) {
    used[v] = true;
    for (int u: G[v]) {
        if (!used[u])
            dfs(u);
    }
    vs.push_back(v);
}

void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for (int u: rG[v])
        if (!used[u])
            rdfs(u, k);
}

int scc(int n) {
    memset(used, 0, sizeof(used));
    vs.clear();
    for (int v = 0; v < n; ++v)
        if (!used[v]) dfs(v);
    memset(used, 0, sizeof(used));
    int k = 0;
    for (int i = (int) vs.size() - 1; i >= 0; --i)
        if (!used[vs[i]]) rdfs(vs[i], k++);
    return k;
}

char s[N];
int ans[N * 8], cnt[N * 8];
void solve() {
    int n; cin >> n;
    FOR (i, 0, n * 8) {
        G[i].clear(); rG[i].clear();
    }
    // i, j
    //   /: (i + j) * 2 ^ ?
    //   \: (i - j + 3 * n) * 2 ^ ?
    FOR (i, 0, n) {
        scanf("%s", s);
        FOR (j, 0, n) {
            int u = (i + j) * 2, v = (i - j + 3 * n) * 2;
            if (s[j] == '#') {
                add_edge(u, v); add_edge(u ^ 1, v ^ 1);
                add_edge(v, u); add_edge(v ^ 1, u ^ 1);
            } else {
                add_edge(u, v ^ 1); add_edge(u ^ 1, v);
                add_edge(v, u ^ 1); add_edge(v ^ 1, u);
            }
        }
    }
    int k = scc(n * 8);
    dbg(k);
    memset(ans, 0, sizeof ans); memset(cnt, 0, sizeof cnt);
    FOR (i, 0, n * 8) if (i % 2 == 0) {
        if (G[i].empty()) continue;
        assert(cmp[i] != cmp[i ^ 1]);
        int kk = min(cmp[i], cmp[i ^ 1]);
        dbg(i, cmp[i], cmp[i + 1]);
        cnt[kk] += 1;
        ans[kk] += cmp[i] > cmp[i ^ 1];
    }
    int res = 0;
    FOR (i, 0, k) {
        res += min(ans[i], cnt[i] - ans[i]);
    }
    cout << res << endl;
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Elevanagram

我看了题解才知道大数据怎么做，虽然，明明是我擅长的数论。另外我觉得很奇怪，明明比第二题更难，而且分值更好，通过的人却比第二题多。

对于小数据：直接 dp，dp[i][delta][m] 表示前 i 个数字，取正和取负的数量差为 delta，这些数的和模 11 的余数是 m 是否可能。

对于大数据：显然需要一些观察，对于特定的情况（或者说自由度很高的情况），可以直接判为可行。一个条件就是任意两个数字数量都大于等于 10。证明也很简单，先让一个数字全正，另一个全负，然后一次次交换正负号，总共能操作 11 次。而两个数之差的两倍一定是与 11 互素的，所以一定会有余数为 0 的状态。这样的话，可能一个数字特别多，别的都小于 10，对于特别多的数字特别考虑一下。 题解中引入了三个数字的观察，使得可以不依赖 DP 而直接爆搜，我觉得能考虑到这个的可能性很低，就算了（因为两个数的观察就足够解出这道题了，不会想下去了）。

小数据

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
const int K = 10, M = 11, D = 20 * 10 + 10;
LL a[K];
bool f[K][D * 2][M];
bool solve() {
    memset(f, 0, sizeof f);
    FOR (i, 1, K) {
        scanf("%lld", a + i);
    }
    LL s = accumulate(a, a + K, 0LL);
    f[0][D][0] = true;
    FOR (i, 1, K) {
        FOR (j, 0, a[i] + 1) {
            int delta = j - (a[i] - j);
            FOR (d, 0, D * 2) if (0 <= d + delta && d + delta < D * 2) {
                FOR (m, 0, M) {
                    f[i][d + delta][(m + (delta + 1111) * i) % 11] |= f[i - 1][d][m];
                }
            }
        }
    }
    return f[K - 1][(s & 1) + D][0];
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        puts(solve() ? "YES" : "NO");
    }
}

大数据

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
const int K = 10, M = 11, D = 20 * 10 + 10;
struct P { int v; int cnt; };
bool f[K][D * 2][M];
bool solve() {
    memset(f, 0, sizeof f);
    vector<P> p;
    LL sum = 0;
    FOR (i, 1, K) {
        int t; scanf("%d", &t); sum += t;
        p.push_back({i, t});
    }
    sort(p.begin(), p.end(), [](const P& a, const P& b){
        return a.cnt > b.cnt;
    });
    if (p[1].cnt >= 10) return true;

    f[0][D][0] = true;
    FOR (i, 1, p.size()) {
        FOR (j, 0, p[i].cnt + 1) {
            int delta = j - (p[i].cnt - j);
            FOR (d, 0, D * 2) if (0 <= d + delta && d + delta < D * 2) {
                    FOR (m, 0, M) {
                        f[i][d + delta][(m + (delta + 1111) * p[i].v) % 11] |= f[i - 1][d][m];
                    }
                }
        }
    }

    FOR (d, 0, D * 2) {
        int dd = d - D + (sum & 1);
        if (abs(dd) > p[0].cnt || (p[0].cnt + abs(dd)) % 2 != 0) continue;
        if (f[p.size() - 1][d][(1111 + dd * p[0].v) % 11]) return true;
    }
    return false;
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        puts(solve() ? "YES" : "NO");
    }
}

2021

Round B

这场参加了，Rank 57。

Increasing Substring

题意：求字符串的最长严格上升子串。

题解：从头到尾扫一遍，如果满足严格递增就答案 +1，否则答案归 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int last = 33, ans = 0;
    FOR (i, 0, n) {
        int c = s[i] - 'A';
        if (c <= last) ans = 1;
        else ++ans;
        last = c;
        printf("%d%c", ans, i == _i - 1 ? '\n' : ' ');
    }
}

int main() {
#ifdef zerol
    freopen("in.txt", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Longest Progression

题意：给定一个数组，至多替换一个元素，求可能的最长的等差数列的长度。

题解：只考虑差分数组，原来的修改操作相当于可以改相邻的两个元素（但是和必须不变），或者单独修改首尾元素，目标是使得数组中连续的相同数字最长。预处理一下每个位置向前和向后的最长相同元素长度，然后考虑对于每一对位置的修改，如果对答案有提升，肯定是把相邻的两个元素变为相同（因此元素和必须能被 2 整除），然后看一看向前向后能接多长（利用预处理的结果）。

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
const int N = 3e5 + 100;
LL a[N];
int f[N], rf[N];

void solve() {
    int n; cin >> n;
    FOR (i, 0, n) scanf("%lld", a + i);
    --n;

    FOR (i, 0, n) a[i] -= a[i + 1];
    f[0] = 1;
    FOR (i, 1, n) f[i] = a[i] == a[i - 1] ? f[i - 1] + 1 : 1;
    rf[n - 1] = 1;
    FORD (i, n - 2, -1) rf[i] = a[i] == a[i + 1] ? rf[i + 1] + 1 : 1;
    
    int ans = *max_element(f, f + n);
    if (ans < n) ++ans;
    
    FOR (i, 0, n - 1) {
        LL t = a[i] + a[i + 1];
        if (t % 2 != 0) continue;
        t /= 2;
        int cur = 2;
        if (i - 1 >= 0 && t == a[i - 1]) {
            cur += f[i - 1];
        }
        if (i + 2 < n && t == a[i + 2]) {
            cur += rf[i + 2];
        }
        ans = max(ans, cur);
    }
    cout << ans + 1 << endl;
}

int main() {
#ifdef zerol
    freopen("in.txt", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Consecutive Primes

题意：求不超过给定数字的，是相邻两个素数之积的最大的数。

题解：对于给定的数字 \(Z\)，考虑 \(a < b < \sqrt Z \le c\)，其中 \(a, b, c\) 为相邻的素数，如果 \(b \cdot c \le Z\)，那么答案就是 \(b \cdot c\)，否则就是 \(a \cdot b\)。

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
bool check(LL x) {
    FOR (i, 2, int(sqrt(x + 0.5)) + 1) {
        if (x % i == 0) return false;
    }
    return true;
}


void solve() {
    LL x; cin >> x;
    LL o = sqrt(x + 0.5);
    LL t1 = o;
    while (!check(t1)) --t1;
    LL t2 = t1 - 1;
    while (!check(t2)) --t2;
    ++o;
    while (!check(o)) ++o;
    if (o * t1 <= x) cout << o * t1 << endl;
    else cout << t1 * t2 << endl;
}

int main() {
#ifdef zerol
    freopen("in.txt", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Truck Delivery

题意：给一棵树，每条边都有一个 \(L_i\) 和 \(A_i\)，然后很多次询问，需要回答从节点 1 到给定节点（必须简单路径），载货量为 \(W\)，支付的若干费用的 GCD（如果没支付过，记为 0）。费用是指，经过 \(L_i < W\) 的边时，需要支付 \(A_i\)。

题解：离线计算，把边和询问按照 \(L\) 和 \(W\) 放在一起从小到大排序，按顺序加边或者回答询问。问题转换成了需要有个东西，支持加边，询问一个点到树根的路径边权的 GCD。再转化一下就是，支持给一棵子树批量 GCD 上一个东西，然后求一个点的值。配合 DFS 序，问题就成了区间 GCD，单点查询，然后就线段树了。

这题很没意思（套路题 + 模板题），kick start 不应该出这种题。

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
const int N = 1e5 + 100;
vector<int> G[N];
int clk = 0;
int fa[N];
int in[N], out[N];
int n;

const int maxn = N;
namespace sg {
    struct Q {
        LL setv;
        explicit Q(LL setv = 0): setv(setv) {}
        void operator += (const Q& q) { setv = __gcd(setv, q.setv); }
    };
    struct P {
        LL g;
        explicit P(LL g = 0): g(g) {}
        void up(Q& q) { g = __gcd(g, q.setv); }
    };
    template<typename T>
    P operator & (T&& a, T&& b) {
        return P(__gcd(a.g, b.g));
    }
    P p[maxn << 2];
    Q q[maxn << 2];
#define lson o * 2, l, (l + r) / 2
#define rson o * 2 + 1, (l + r) / 2 + 1, r
    void up(int o, int l, int r) {
        if (l == r) p[o] = P();
        else p[o] = p[o * 2] & p[o * 2 + 1];
        p[o].up(q[o]);
    }
    void down(int o, int l, int r) {
        q[o * 2] += q[o]; q[o * 2 + 1] += q[o];
        q[o] = Q();
        up(lson); up(rson);
    }
    template<typename T>
    void build(T&& f, int o = 1, int l = 1, int r = n) {
        if (l == r) q[o] = f(l);
        else { build(f, lson); build(f, rson); q[o] = Q(); }
        up(o, l, r);
    }
    P query(int ql, int qr, int o = 1, int l = 1, int r = n) {
        if (ql > r || l > qr) return P();
        if (ql <= l && r <= qr) return p[o];
        down(o, l, r);
        return query(ql, qr, lson) & query(ql, qr, rson);
    }
    void update(int ql, int qr, const Q& v, int o = 1, int l = 1, int r = n) {
        if (ql > r || l > qr) return;
        if (ql <= l && r <= qr) q[o] += v;
        else {
            down(o, l, r);
            update(ql, qr, v, lson); update(ql, qr, v, rson);
        }
        up(o, l, r);
    }
}

void dfs(int u, int f) {
    fa[u] = f; in[u] = ++clk;
    for (auto& v: G[u]) {
        if (v == f) continue;
        dfs(v, u);
    }
    out[u] = clk;
}
struct P { int u, v, l; LL a; };
vector<P> edges;
struct Q { int idx, c, w; };
vector<Q> queries;
LL ans[N];

void solve() {
    int Qn; cin >> n >> Qn;
    FOR (i, 0, n + 1) G[i].clear();
    edges.clear(); queries.clear(); clk = 0;
    FOR (_, 1, n) {
        int u, v, l; LL a; scanf("%d%d%d%lld", &u, &v, &l, &a);
        G[u].push_back(v);
        G[v].push_back(u);
        edges.push_back({u, v, l, a});
    }
    dfs(1, -1);
    assert(clk == n);
    sort(edges.begin(), edges.end(), [](const P& a, const P& b){ return a.l < b.l; });
    FOR (i, 0, Qn) {
        int c, w; scanf("%d%d", &c, &w);
        queries.push_back({i, c, w});
    }
    sort(queries.begin(), queries.end(), [](const Q& a, const Q& b){ return a.w < b.w; });
    int cur = 0;
    sg::build([](int){ return sg::Q(); });
    for (Q& q: queries) {
        while (cur < edges.size() && edges[cur].l <= q.w) {
            auto& e = edges[cur++];
            if (fa[e.u] != e.v) swap(e.u, e.v);
            sg::update(in[e.u], out[e.u], sg::Q(e.a));
            dbg("upd", in[e.u], out[e.u], e.a);
        }
        ans[q.idx] = sg::query(in[q.c], in[q.c]).g;
        dbg("query", q.idx, in[q.c], ans[q.idx]);
    }
    FOR (i, 0, Qn) printf("%lld%c", ans[i], i == _i - 1 ? '\n' : ' ');
}

int main() {
#ifdef zerol
    freopen("in.txt", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Round C

这场参加了，第三题只做了 Test Set 1，Rank 60。

Smaller Strings

题意：给定一个字符集大小 K 和一个字符串，问字典序小于这个字符串的回文串的数量。

题解：考虑原始字符串的前半部分和后半部分，前半部分严格小于的回文串肯定符合条件，这部分统计类似于算 K 进制数。如果前半部分相同的情况下，只有后半部分比前半部分大才行。

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
const LL MOD = 1e9 + 7;
const int N = 1e5 + 100;
char s[N], ss[N];

void solve() {
    int n, k; cin >> n >> k >> s;
    int m = (n + 1) / 2;
    FOR (i, 0, m) {
        ss[i] = ss[n - 1 - i] = s[i];
    }
    bool f = strcmp(ss, s) >= 0;
    LL ans = 0;
    FOR (i, 0, m) {
        dbg(i, s[i] - 'a');
        ans = ans * k + (s[i] - 'a');
        ans %= MOD;
    }
    cout << (ans + 1 - f) % MOD << endl;
}

int main() {
#ifdef zerol
    freopen("in.txt", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Alien Generator

题意：求有多少种的连续自然数之和恰好为 \(G\)。

题解：枚举连续自然数的项数就行了，项数一定是 \(2G\) 的因数。

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
int ans = 0;

void check(LL x, LL k) {
    LL u = x / k + 1 - k;
    if (u >= 1 && u % 2 == 0) {
        ans += 1;
    }
}

void solve() {
    LL x; cin >> x;
    // x / n * 2 = k + k + n - 1
    ans = 0;
    x *= 2;
    FOR (i, 1, LL(sqrt(x + 0.5) + 1)) {
        if (i * i == x) {
            check(x, i);
        } else if (x % i == 0) {
            check(x, i); check(x, x / i);
        }
    }
    cout << ans << endl;
}

int main() {
#ifdef zerol
    freopen("in.txt", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Rock Paper Scissors

题意：石头剪刀布的交互题，题意有些复杂。每一天的得分规则不同，赢了得 W 分，平了得 E 分，其中 E 有四种可能的取值，为 \(W, W / 2, W / 10, 0\)。对手的策略是已知的，它出石头、剪刀、布的概率之比为那天之前你出的剪刀、布、石头的次数的比例，特别地，第一天视为等概率。目标是 200 天后（每天都是独立的），期望收益超过某个定值。

这题翻车了，我认定这是我擅长的构造题，四种情况分类讨论一下，然后凑出一个足够优的策略就好了。然后题意没读清楚把自己坑了，然后又凑了一通也没凑出来，最后只过了 Test Set 1。过 Test Set 1 的方案很简单，每天按照石头、剪刀、布的顺序出就行了。赛后看了题解，惊了，这竟然是 DP 题？？？

官方题解 for Test Set 2：随机生成策略，用随机优化算法来找到一个足够好的。

官方题解 for Test Set 3：\(f[a][b][c]\) 为第 \(a+b+c\) 天石头剪刀布分别出了 \(a, b, c\) 次的最佳期望收益，最后把最优路径输出来就好了，状态转移也很简单。

其实四种情况的 DP 得到的某个最优解长这样，凭空构造还是太难了。

1
2
3
4
RSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSP
SPPPPRRRRRRRRRRRRRRRSSSSSSSSSSSSSSSSSSSSSSSSSPPPPPPPPPPPPPPP
PRRRRRRRRRSSSSSSSSSSSSSSSSSSSSSSSSSSSPPPPPPPPPPPPPPPPPPPPPPP
PRRSSSSPPPPPPPPRRRRRRRRRRRRRRRRSSSSSSSSSSSSSSSSSSSPPPPPPPPPP

代码如下，包含 DP 过程和期望计算，或者本地把构造的结果算出来根据四种情况判一下就好了。

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
const int N = 60, M = N + 5;
int c[M];
int W, E;
double all;

void output() {
    int cnt[3] = {0, 0, 0};
    double rp[3] = {1.0 / 3, 1.0 / 3, 1.0 / 3};
    double profit = 0;
    FOR (i, 0, N) {
        if (c[i] == 0) putchar('R');
        if (c[i] == 1) putchar('S');
        if (c[i] == 2) putchar('P');
        profit += W * rp[(c[i] + 1) % 3] + E * rp[c[i]];
        cnt[c[i]] += 1;
        FOR (j, 0, 3) rp[(j + 2) % 3] = 1.0 * cnt[j] / (i + 1);
    }
    all += profit;
    puts("");
}

pair<double, int> f[M][M][M];
int from[M][M][M];
void solve() {
    cin >> W >> E;
    f[1][0][0] = {0, 0}; f[0][1][0] = {0, 1}; f[0][0][1] = {0, 2};
    int ii, jj, kk;
    double ans = -1;
    FOR (i, 0, N + 1) FOR (j, 0, N + 1) FOR (k, 0, N + 1) {
        int s = i + j + k;
        double ss = s - 1;
        if (s <= 1 || s > N) continue;
        f[i][j][k] = max({
            make_pair(i ? f[i - 1][j][k].first + k * W / ss + j * E / ss : -1, 0),
            make_pair(j ? f[i][j - 1][k].first + i * W / ss + k * E / ss : -1, 1),
            make_pair(k ? f[i][j][k - 1].first + j * W / ss + i * E / ss : -1, 2),
        });
        if (s == N && f[i][j][k].first > ans) { ii = i; jj = j; kk = k; ans = f[i][j][k].first; }
    }
    dbg(ans);
    FORD (i, N - 1, -1) {
        c[i] = f[ii][jj][kk].second;
        if (c[i] == 0) --ii; else if (c[i] == 1) --jj; else if (c[i] == 2) --kk;
    }
    output();
}


int main() {
#ifdef zerol
    freopen("in.txt", "r", stdin);
#endif
    int T, X; cin >> T >> X;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
    dbg(all / 200);
}

Binary Operator

题意：定义一种新的二元运算，记号为 #，且为全函数。要求把若干包含 + * # 和超长数字的表达式划分为若干等价类。

题解：将 a#b 的结果定为随机整数参与运算（保证对于同样的 a 和 b，a#b 的结果一致），同时对素数取模。对于不同模数重复若干次，如果某两个表达式的值始终相同，那么它们就一定在一个等价类中。

这题其实有点套路，大概就是知道随机化算法的看了就知道，没见过的可能就想不出了。 另外只需要尝试很少几个模数就行了。

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
const int N = 100 + 5;
string s[N];
const int C = 100;
const vector<LL> M = {7883129, 9124553, 10415371, 11134633, 12214801, 15589333, 17148757, 17997457, 20278487, 27256133, 28678757, 38206199, 41337119, 47422547, 48543479, 52834961, 76993291, 85852231, 95217823, 108755593, 132972461, 171863609, 173629837, 176939899, 207808351, 227218703, 306112619, 311809637, 322711981, 330806107, 345593317, 345887293, 362838523, 373523729, 394207349, 409580177, 437359931, 483577261, 490845269, 512059357, 534387017, 698987533, 764016151, 906097321, 914067307, 954169327};
int m[N][N];
LL val[N];
map<pair<LL, LL>, LL> m2;
int ans[N];
LL MOD;

mt19937 mt(time(0));
auto rd = bind(uniform_int_distribution<LL>(), mt);

LL eval(const string& s) {
    int cc = 0;
    if (s[0] == '(') {
        int n = s.length();
        assert(s[n - 1] == ')');
        FOR (i, 1, n - 1) {
            if (s[i] == '(') ++cc;
            else if (s[i] == ')') --cc;
            else if (s[i] == '+' && cc == 0) {
                return (eval(s.substr(1, i - 1)) + eval(s.substr(i + 1, n - 1 - (i + 1)))) % MOD;
            } if (s[i] == '*' && cc == 0) {
                return eval(s.substr(1, i - 1)) * eval(s.substr(i + 1, n - 1 - (i + 1))) % MOD;
            } if (s[i] == '#' && cc == 0) {
                LL x = eval(s.substr(1, i - 1)), y = eval(s.substr(i + 1, n - 1 - (i + 1)));
                auto it = m2.find({x, y});
                if (it == m2.end()) return m2[{x, y}] = rd() % MOD;
                return it->second;
            }
        }
    } else {
        LL x = 0;
        for (char c: s) {
            x = x * 10 + c - '0';
            x %= MOD;
        }
        return x;
    }
    assert(0);
}

void solve() {
    memset(m, 0, sizeof m);
    int n; cin >> n;
    dbg(n);
    FOR (i, 0, n) cin >> s[i];
    for (auto x: M) {
        MOD = x;
        m2.clear();
        FOR (i, 0, n) {
            val[i] = eval(s[i]);
        }
        FOR (i, 0, n)
            FOR (j, i + 1, n)
                m[i][j] += val[i] == val[j];
    }
    memset(ans, -1, sizeof ans);
    int cnt = 1;
    FOR (i, 0, n) {
        if (ans[i] != -1) continue;
        ans[i] = cnt++;
        FOR (j, i + 1, n)
            if (m[i][j] == M.size())
                ans[j] = ans[i];
    }
    FOR (i, 0, n) cout << ans[i] << ' ';
    cout << endl;
}

int main() {
#ifdef zerol
    freopen("in.txt", "r", stdin);
#endif
    int T; cin >> T;
    FOR (Ca, 1, T + 1) {
        printf("Case #%d: ", Ca);
        solve();
    }
}

Round D

这场参加了，Rank 71，最后一题只做了小数据。这场 Google 评测出现了积压，测了几十分钟才能出结果，最后邮件中也对于这个问题道歉了。

Arithmetic Square

题意：给一个 3x3 的整数方阵（缺了中心的那个），中心任意填整数，问行列对角线（共八条）最多能形成多少等差数列。

题解：其中有四条是固定的，对于其他四条，求出中心填什么能形成等差数列，然后选择一个效果最好的。

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
const int N = 3;
int a[N][N];

int ck(int x, int y, int z) {
    return y * 2 - x - z == 0;
}

map<int, int> mp;
void add(int x, int y) {
    int v = x + y;
    if (v % 2 == 0) mp[v] += 1;
}

void solve() {
    mp.clear();
    FOR (i, 0, N) FOR (j, 0, N) if (i != 1 || j != 1) {
        scanf("%d", &a[i][j]);
    }
    int s = 0;
    s += ck(a[0][0], a[0][1], a[0][2]);
    s += ck(a[2][0], a[2][1], a[2][2]);
    s += ck(a[0][0], a[1][0], a[2][0]);
    s += ck(a[0][2], a[1][2], a[2][2]);
    add(a[0][0], a[2][2]); add(a[0][2], a[2][0]);
    add(a[0][1], a[2][1]); add(a[1][0], a[1][2]);
    int m = 0;
    for (auto it: mp) {
        m = max(m, it.second);
    }
    printf("%d\n", s + m);
}

Cutting Intervals

题意：给若干个区间（可能重复，重叠），问砍 C 刀之后最多能形成几个区间（砍在端点上无效）。

题解 1（开开区间）：考虑区间相邻端点分割出的线段，求出线段的长度以及被区间包含的次数，然后排序，优先考虑被包含次数多的。方法就是把区间的左右端点分别看作进入和离开两个事件，然后排序扫一遍，就能求出每个地方重叠的次数了。但是对于刚好在端点上的情况需要特殊考虑，忽略所有进入事件但是得统计离开事件。

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
struct P {
    LL v, d;
};
struct Q {
    LL len, c;
};
vector<P> a;
vector<Q> b;

void solve() {
    a.clear(); b.clear();
    int n; LL C; cin >> n >> C;
    FOR (i, 0, n) {
        LL l, r; scanf("%lld%lld", &l, &r);
        a.push_back({l, 1}); a.push_back({r, -1});
    }
    sort(a.begin(), a.end(), [](const P& a, const P& b){ return a.v < b.v; });
    LL u = 0, last = -1;
    LL cu = 0;
    for (auto v: a) {
        if (v.v != last) {
            b.push_back({1, u + cu});
            if (u) b.push_back({v.v - last - 1, u});
            cu = 0;
        }
        if (v.d == 1) cu -= 1;
        u += v.d; last = v.v;
    }
    sort(b.begin(), b.end(), [](const Q& a, const Q& b){ return a.c > b.c; });
    LL ans = n;
    for (auto v: b) {
        LL c = max(0LL, min(C, v.len)); C -= c;
        ans += c * v.c;
    }
    printf("%lld\n", ans);
}

题解 2（闭开区间）：这种题就很适合闭开区间，你会发现就没有乱七八糟的边界和特殊情况了。代码上区别很小，就是把特殊处理端点处的部分去掉了。之前那个之所以是开开区间，是因为 [l, r] 中对答案有贡献的只有 [l + 1, r - 1]，所以拿到的其实是两边开的区间。与之相对的，如果考虑的是 [l + 1, r]，那么相当于是 [l + 1, r - 1] 的闭开区间，一切都变得刚刚正好了。

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
struct P {
    LL v, d;
};
struct Q {
    LL len, c;
};
vector<P> a;
vector<Q> b;

void solve() {
    a.clear(); b.clear();
    int n; LL C; cin >> n >> C;
    FOR (i, 0, n) {
        LL l, r; scanf("%lld%lld", &l, &r);
        a.push_back({l + 1, 1}); a.push_back({r, -1});
    }
    sort(a.begin(), a.end(), [](const P& a, const P& b){ return a.v < b.v; });
    LL u = 0, last = -1;
    for (auto v: a) {
        if (v.v != last) b.push_back({v.v - last, u});
        u += v.d; last = v.v;
    }
    sort(b.begin(), b.end(), [](const Q& a, const Q& b){ return a.c > b.c; });
    LL ans = n;
    for (auto v: b) {
        LL c = min(C, v.len); C -= c;
        ans += c * v.c;
    }
    printf("%lld\n", ans);
}

用 map 写起来会方便一些：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Q { LL len, c; };

void solve() {
    int n; LL C; cin >> n >> C;
    map<LL, int> mp;
    FOR (i, 0, n) {
        LL l, r; scanf("%lld%lld", &l, &r);
        mp[l + 1]++; mp[r]--;
    }
    LL last = -1, u = 0;
    vector<Q> b;
    for (auto [x, v]: mp) {
        if (u) b.push_back({x - last, u});
        u += v; last = x;
    }
    sort(b.begin(), b.end(), [](const Q& a, const Q& b){ return a.c > b.c; });
    LL ans = n;
    for (auto v: b) {
        LL c = min(C, v.len); C -= c;
        ans += c * v.c;
    }
    printf("%lld\n", ans);
}

Final Exam

转换后的题意：给一些不重叠的区间，要求支持查询离给定数字最近的数，以及删除一个数。

题解：拿一个 set 维护一下。（比较考验对于 lower_bound 和 upper_bound 的理解。）

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
const int N = 1e5 + 100;
const LL INF = 1e18;
struct P { LL l, r; };
bool operator < (const P& a, const P& b) { return a.l < b.l; }
set<P> s;

void ins(LL l, LL r) { if (l <= r) s.insert({l, r}); }

void del(LL x) {
    auto u = *--s.upper_bound({x, -1});
    assert(u.l <= x && x <= u.r);
    s.erase(u); ins(u.l, x - 1); ins(x + 1, u.r);
}

LL find_l(LL x) {
    auto it = s.upper_bound({x, -1});
    if (it == s.begin()) return -INF;
    auto u = --it;
    if (u->l <= x && x <= u->r) return x;
    return u->r;
}

LL find_r(LL x) {
    auto u = s.lower_bound({x, -1});
    if (u == s.end()) return -INF;
    return u->l;
}

void solve() {
    s.clear();
    int n, m; cin >> n >> m;
    FOR (i, 0, n) {
        LL l, r; scanf("%lld%lld", &l, &r);
        s.insert({l, r});
    }
    FOR (i, 0, m) {
        LL v; scanf("%lld", &v);
        LL l = find_l(v), r = find_r(v);
        LL ans = abs(l - v) <= abs(r - v) ? l : r;
        del(ans);
        printf("%lld ", ans);
    }
    puts("");
}

Primes and Queries

题意：给一个数组，要求支持两种操作，修改一个数，以及给定 \(S, L, R\)，求 \(\sum_{i=L}^R V_p(A_i^S - (A_i \bmod P)^S)\)，其中 \(V_p(x)\) 表示 \(x\) 中质因子 \(p\) 的数量。

题解：肯定要搞个线段树维护些什么。对于小数据，有 \(1 \le S\le 4\)，那么只要对于每个可能的 \(S\) 维护一下。对于大数据，需要维护一点什么，然后可以对于任意 \(S\) 快速计算区间和。然后就需要一个数论公式，然后有几种情况需要讨论，维护一下。

Z: 这题很没意思，感觉完全没必要考这种东西，想考察什么，数论水平？有没有听说过某个公式或者搜索能力？还有线段树抄模板的水平？

懒得贴代码了。

Round F

这场参加了，Rank 39，AK 了。

Trash Bins

题意：给一个 01 串，求所有位置到最近的 1 的距离之和，保证存在 1。

题解：分别预处理左边最近的 1 和右边最近的 1，然后取 min 求和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int l[n], r[n];
    memset(l, 0, sizeof l); memset(r, 0, sizeof r);
    l[0] = s[0] == '1' ? 0 : 1e9;
    r[n - 1] = s[n - 1] == '1' ? 0 : 1e9;
    FOR (i, 1, n) l[i] = s[i] == '1' ? 0 : l[i - 1] + 1;
    FORD (i, n - 2, -1) r[i] = s[i] == '1' ? 0 : r[i + 1] + 1;
    LL ans = 0;
    FOR (i, 0, n) ans += min(l[i], r[i]);
    cout << ans << endl;
}

Festival

题意：给若干区间，每个区间对应一个值。找一个点，使得包含它的所有区间的值中任取 K 个之和最大，求这个最大值。

题解：转化为闭开区间，每个区间看做左端点插入和右端点删除两个操作，按顺序遍历，然后用两个 set 维护，同时保证第一个 set 中的最小值大于等于第二个 set 中的最大值且第一个 set 的大小不超过 K，答案就是第一个 set 在整个过程中所有值之和的最大值。

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
multiset<int> a, b;
struct P { int h; bool start; };
void solve() {
    int d, n, k; cin >> d >> n >> k;
    map<int, vector<P>> mp;
    FOR (i, 0, n) {
        int h, s, e; cin >> h >> s >> e;
        mp[s].push_back({h, true});
        mp[e].push_back({h, false});
    }
    a.clear(); b.clear();
    LL ans = -1, cur = 0;
    for (auto& [_, v]: mp) {
        for (P& p: v) {
            if (p.start) {
                a.insert(p.h); cur += p.h;
                if (a.size() > k) {
                    cur -= *a.begin();
                    b.insert(*a.begin());
                    a.erase(a.begin());
                }
            } else {
                if (b.count(p.h)) {
                    b.erase(b.find(p.h));
                } else {
                    cur -= p.h;
                    a.erase(a.find(p.h));
                    if (!b.empty()) {
                        a.insert(*b.rbegin());
                        cur += *b.rbegin();
                        b.erase(--b.end());
                    }
                }
            }
        }
        assert(a.size() <= k);
        ans = max(ans, cur);
    }
    cout << ans << endl;
}

Star Trappers

题意：给 300 个点以及一个目标点，选择若干点构成包含目标点的多边形，求最小的可能周长。

题解：首先这个多边形一定是凸多边形，其次它的边数至多为 4（如果更多的话总能砍掉一个不包含目标点的角）。然后分两种情况：

  • 三角形：直接枚举三角形的三个顶点
  • 四边形：四边形不能砍掉一个角变成三角形的唯一一种可能性在于，目标点落在四边形对角线的交点上。对于这种情况，枚举所有线段，如果目标点在这个线段上，再在线段的两侧分别找一个距离最近的点构成四边形。

另：题解中处理四边形的方法是极角排序，最先想到的也是这个，但感觉会比较难写。

代码（用了模板，有一些没用到的东西，还有一些东西不需要浮点数运算）：

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
typedef double LD;
const LD eps = 1E-10;
int sgn(LD x) { return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1); }
struct L;
struct P;
typedef P V;
struct P {
    LD x, y;
    explicit P(LD x = 0, LD y = 0): x(x), y(y) {}
    explicit P(const L& l);
};
struct L {
    P s, t;
    L() {}
    L(P s, P t): s(s), t(t) {}
};

P operator - (const P& a, const P& b) { return P(a.x - b.x, a.y - b.y); }

LD dist(const P& p) { return sqrt(p.x * p.x + p.y * p.y); }
LD dot(const V& a, const V& b) { return a.x * b.x + a.y * b.y; }
LD det(const V& a, const V& b) { return a.x * b.y - a.y * b.x; }
LD cross(const P& o, const P& s, const P& t) { return det(s - o, t - o); }
// --------------------------------------------
bool p_on_seg(const P& p, const L& seg) {
    P a = seg.s, b = seg.t;
    return !sgn(det(p - a, b - a)) && sgn(dot(p - a, p - b)) < 0;
}

bool in_triangle(P p1, P p2, P p3, P o) {
    if (sgn(cross(p1, p2, p3)) == 0) return false;
    if (sgn(cross(p1, p2, p3)) < 0) return in_triangle(p1, p3, p2, o);
    return sgn(cross(p1, p2, o)) > 0 && sgn(cross(p2, p3, o)) > 0 && sgn(cross(p3, p1, o)) > 0;
}

void solve() {
    int n; cin >> n;
    vector<P> v;
    FOR (i, 0, n) {
        int x, y; cin >> x >> y;
        v.emplace_back(x, y);
    }
    P p; cin >> p.x >> p.y;
    double ans = 1e18;
    FOR (i, 0, n)
        FOR (j, i + 1, n)
            FOR (k, j + 1, n) {
                P &a = v[i], &b = v[j], &c = v[k];
                if (in_triangle(a, b, c, p)) {
                    ans = min(ans, dist(a - b) + dist(b - c) + dist(a - c));
                }
            }

    FOR (i, 0, n) FOR (j, i + 1, n) if (p_on_seg(p, L(v[i], v[j]))) {
        double d1 = 1e18, d2 = 1e18;
        FOR (k, 0, n) if (k != i && k != j) {
            if (sgn(cross(v[k], v[i], v[j])) > 0) {
                d1 = min(dist(v[k] - v[i]) + dist(v[k] - v[j]), d1);
            }
            if (sgn(cross(v[k], v[i], v[j])) < 0) {
                d2 = min(dist(v[k] - v[i]) + dist(v[k] - v[j]), d2);
            }
        }
        ans = min(ans, d1 + d2);
    }

    if (ans > 1e17) puts("IMPOSSIBLE");
    else printf("%.6f\n", ans);
}

Graph Travel

题意 & 题解：状态压缩 DP 裸题，实在是没啥好写的。

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
const int N = 16, M = 1 << N;
LL f[M], sum[M];
bool G[N][N];
LL l[N], r[N], a[N];
void solve() {
    LL n, m, K; cin >> n >> m >> K;
    memset(f, 0, sizeof f); memset(G, 0, sizeof G);
    FOR (i, 0, n) cin >> l[i] >> r[i] >> a[i];
    FOR (_, 0, m) {
        int x, y; cin >> x >> y;
        G[x][y] = G[y][x] = true;
    }
    FOR (i, 0, 1 << n) {
        LL s = 0;
        FOR (k, 0, n) if ((i >> k) & 1) s += a[k];
        sum[i] = s;
    }
    FOR (i, 0, n) f[1 << i] = 1;
    FOR (u, 1, 1 << n) {
        if (__builtin_popcount(u) == 1) continue;
        FOR (k, 0, n) if ((u >> k) & 1) {
            int v = u ^ (1 << k);
            if (sum[v] < l[k] || sum[v] > r[k]) continue;
            bool can = false;
            FOR (z, 0, n) can |= ((v >> z) & 1) && G[z][k];
            if (can) f[u] += f[v];
        }
    }
    LL ans = 0;
    FOR (i, 0, 1 << n) if (sum[i] == K)  {
        ans += f[i];
    }
    cout << ans << endl;
}