2060A - Fibonacciness

暴力枚举所有的 $a_{3}$。

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
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int a1, a2, a4, a5;
        cin >> a1 >> a2 >> a4 >> a5;

        int res = 0;
        for (int a3 = -100; a3 <= 100; a3++) {
            int cnt = 0;
            cnt += a1 + a2 == a3;
            cnt += a2 + a3 == a4;
            cnt += a3 + a4 == a5;
            res = max(res, cnt);
        }
        cout << res << endl;
    }

    return 0;
}

2060B - Farmer John’s Card Game（思维）

主要是读题。每行内部顺序无要求；如果第 $i$ 行的最小值小于第 $j$ 行的最小值，那么 $i$ 应该排在 $j$ 前面。而且如果按行按列都升序排序之后，必须是形如

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
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        vector a(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> a[i][j];
            }
            sort(a[i].begin(), a[i].end());
        }
        
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&](int i, int j) {
            return a[i] < a[j];
        });  

        bool ok = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[p[i]][j] - 1 != a[p[i - 1]][j]) {
                    ok = false;
                }
            }
        }

        if (!ok) {
            cout << -1 << endl;
        } else {
            for (int i = 0; i < n; i++) {
                cout << p[i] + 1 << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

2060C - Game of Mathletes（假博弈）

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
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        vector<int> cnt(n + 1);
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            cnt[x]++;
        }

        int ans = 0;
        for (int i = 1; i < (k + 1) / 2; i++) {
            ans += min(cnt[i], cnt[k - i]);
        }
        if (k % 2 == 0) {
            ans += cnt[k / 2] / 2;
        }
        cout << ans << endl;
    }

    return 0;
}

2060D - Subtract Min Sort（思维）

一些分析：

  • 对于前两个数，如果 $a{1}>a{2}$ 那已经无解。

  • 否则设 $a{1} \leqslant a{2}$。需不需要操作前两项呢？

  • 考虑 $a{1}<a{2}>a{3}$，不能先操作 $a{2}$ 和 $a{3}$，因为这样会让 $a{3}$ 变成 0，意味着只能 $a{1}=a{2}=0$，但一般做不到。所以应当先操作 $a{1}$ 和 $a{2}$。

  • 考虑 $a{1}<a{2}a{4}$，也不能先操作 $a{2}$ 和 $a{3}$，因为这样会让 $a{2}$ 变成 0，$a{1}>a{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
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        for (int i = 1; i < n; i++) {
            int minn = min(a[i], a[i - 1]);
            a[i] -= minn;
            a[i - 1] -= minn;
        }

        cout << (is_sorted(a.begin(), a.end()) ? "YES" : "NO") << endl;
    }

    return 0;
}

2060E - Graph Composition（并查集）

如果原图有边，新图却不连通，那这条边必须删去。

现在只需要补边。用原图剩下的边建图，看有多少连通块，和新图差几个连通块就需要加几条边。

用并查集判断是否连通，时间复杂度近线性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

struct DSU {
    vector<int> p, siz;
    
    DSU(int n) : p(n + 1), siz(n + 1, 1) {
        iota(p.begin(), p.end(), 0);
    }
    
    int find(int x) {
        while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool uno(int x, int y) {
        x = find(x), y = find(y);
        if (same(x, y)) return false;
        siz[x] += siz[y];
        p[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, m1, m2;
        cin >> n >> m1 >> m2;

        vector<pair<int, int>> E1(m1);
        for (auto& [u, v] : E1) {
            cin >> u >> v;
            u--, v--;
        }

        DSU dsu1(n), dsu2(n);
        while (m2--) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            dsu2.uno(u, v);
        }

        int res = 0;
        for (auto& [u, v] : E1) {
            if (!dsu2.same(u, v)) {
                res++;
            } else {
                dsu1.uno(u, v);
            }
        }

        int siz1 = 0, siz2 = 0;
        for (int i = 0; i < n; i++) {
            siz1 += dsu1.find(i) == i;
            siz2 += dsu2.find(i) == i;
        }
        res -= siz2 - siz1;
        cout << res << endl;
    }

    return 0;
}

2060F - Multiplicative Arrays（DP 组合数学）

首先如果 $n$ 很大，这些 $a_{i}$ 大部分都是 1，具体来说，$2^{20}>10^{5}$，所以至多只有 20 个非 1 的数，从这里入手。

设 $dp{n,d}$ 表示 $a{1}a{2}\dots a{d}=n$ 的方案数，其中 $a_{i} \neq 1$，于是可以做如下转移：

表示最后一个填它某个因数，前面用已知的转移。方案数求和。

填 1。填上 1 之后总长度恰为 $\ell$，乘积为 $n$ 的方案数为

也就是选 $d$ 个位置填不是 1 的数。

现在需要求最长长度是 $L$ 的，那就是

这有两个 $\sum$，复杂度不允许，利用组合数的性质化简，

这就是最终答案。

时间复杂度 $\operatorname{O}(DN\sqrt{ N }+tDN)$，这里 $D=20,N=10^{5}$。本地能跑出来就没问题。可以用预处理因子的方法将复杂度降低到 $\operatorname{O}(DN\log N+tDN)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

constexpr int mod = 998244353;
constexpr int maxN = 1e5 + 8;
constexpr int maxD = 20;
ll dp[maxD][maxN];  // dp[d][n] : x_1 * x_2 * ... * x_d == n

ll qpow(ll a, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll inv(ll n) {
    return qpow(n, mod - 2);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    for (int n = 1; n < maxN; n++) {
        dp[1][n] = 1;
    }

    for (int d = 2; d < maxD; d++) {
        for (int n = 1; n < maxN; n++) {
            for (int i = 2; i * i <= n; i++) {
                if (n % i == 0) {
                    dp[d][n] += dp[d - 1][i];
                    dp[d][n] %= mod;
                    if (n / i != i) {
                        dp[d][n] += dp[d - 1][n / i];
                        dp[d][n] %= mod;
                    }
                }
            }
        }
    }

    int t;
    cin >> t;

    while (t--) {
        int N, D;
        cin >> N >> D;
        
        cout << D << " ";

        for (int n = 2; n <= N; n++) {
            ll res = 0;

            // 数据过大，组合数不能预处理阶乘
            // 先算 C(D + 1, 2)
            ll CC = (D + 1LL) * D / 2;
            CC %= mod;  // 记得随时取模 不然下面会爆LL

            for (int d = 1; d < min(maxD, D); d++) {
                res += CC * dp[d][n];
                res %= mod;

                // 利用 C(D + 1, d + 1) 算 C(D + 1, d + 2)
                CC *= (D - d);
                CC %= mod;
                CC *= inv(d + 2);
                CC %= mod;
            }

            cout << res << " ";
        }
        cout << endl;
    }

    return 0;
}

附：证明

高中还是蛮常用的。

2060G - Bugged Sort（思维）

有如下结论：

  • 操作一次，$a{i}$ 对面还是 $b{i}$，$b{i}$ 对面还是 $a{i}$，但是上下关系会翻转；

  • 操作一次，两组将翻转；

  • 如果 $n \geqslant 3$，则必然可以交换两列而不翻转（例如要换 1 列和 2 列，操作方案是 (1,3), (2,3), (1,2)）。

所以现在化为，可以任意排序，但只能翻转偶数次（记翻转次数为 cnt），问是否有解。

还是按 B 的思路排序（先 $a{i}$ 和 $b{i}$ 排，再按这两者的最小值排）。无法排序则无解。

  • 如果有某个下标满足 $\max\lbrace a{i-1},b{i-1} \rbrace<\min\lbrace a{i},b{i} \rbrace$，那第 $i$ 位翻不翻转都行，处于无敌状态（称这是两组的分界线）。

  • 但对于其它位置，如果前面翻转，那自己也要翻转，这两个是绑定的（称相互绑定的若干个构成一组），一个翻转整个一组都要翻转。

如果某组的长度是偶数，那翻转并不会改变 cnt 的奇偶性，没用。如果是奇数，那就能随意改变 cnt 的奇偶性。某组长度是奇数等价于存在某个分界线下标是奇数（不转换也行，统计一下所有组然后一一判断）。

在可能有解的前提下，如果能随意改变 cnt 的奇偶性，或者 cnt 本就是偶数，则有解。

时间复杂度 $\operatorname{O}(n\log n)$，主要是排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<array<int, 2>> a(n);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i][0];
        }
        for (int i = 0; i < n; i++) {
            cin >> a[i][1];
            if (a[i][0] > a[i][1]) {
                swap(a[i][0], a[i][1]);
                cnt++;
            }
        }
        sort(a.begin(), a.end());

        bool good = false;
        bool ok = true;
        for (int i = 1; i < n; i++) {
            if (a[i - 1][1] < a[i][0]) {
                if (i % 2 == 1) {
                    good = true;  // 无敌
                }
            } else if (a[i - 1][1] > a[i][1]) {  // 不是有序的
                ok = false;
            }      
        }

        if (ok && (good || cnt % 2 == 0 || n % 2 == 1)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}