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