【题解】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();
    }
}