画师：赤倉

题目链接：Codeforces Round 991 (Div. 3)

A题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    int n, x;
    cin >> n >> x;
    int sum = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        sum += s.size();
        if (sum <= x) {
            ans++;
            
        }
    }
    cout << ans << '\n';
}

B题

首先看是否可以平均分配，如果可以，则从头到尾依次按规则将它变为平均值，如果最后可以将所有数都平均，则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
void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n);
    i64 sum = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    if (sum % n != 0) {
        cout << "NO\n";
    } else {
        int ave = sum / n;
        for (int i = 0; i < n - 2; i++) {
            if (a[i] < ave) {
                while (a[i] < ave) {
                    a[i]++;
                    a[i + 2]--;
                }
            } else if (a[i] > ave) {
                while (a[i] > ave) {
                    a[i]--;
                    a[i + 2]++;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (a[i] != ave) {
                cout << "NO\n";
                return;
            }
        }
        cout << "YES\n";
    }
}

C题

如果一个数字能被9整除，那么它各位数字之和可以被9整除（可证明）。

先统计出原数字各位数字之和$sum$是多少，变换数字只有$2 \to 4$和$3 \to 9$两种选项，统计数字$2$和$3$出现的频率$cnt_2$，$cnt_3$。

下面是一种枚举$sum$加上$6k_1+2k_2$判断是否可被9整除的做法，注意先把多余的$cnt2$（大于2的部分，因为加3个2和加1个6没有区别）并入$cnt3$中，具体可见代码。

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
void solve() {
    int n;
    string s;
    cin >> s;
    n = s.size();
    int sum = 0;
    int cnt2 = 0, cnt3 = 0;
    for (int i = 0; i < n; i++) {
        sum += s[i] - '0';
        if (s[i] == '2') {
            cnt2++;
        } else if (s[i] == '3') {
            cnt3++;
        }
    }
    int times = cnt2 / 3;
    if (times > 1) {
        cnt3 += times - 1;
        cnt2 -= (times - 1) * 3;
    }
    for (int i = 0; i <= cnt3; i++) {
        for (int j = 0; j <= cnt2 && j <= 2; j++) {
            if ((sum + i * 6 + j * 2) % 9 == 0) {
                cout << "YES\n";
                return;
            }
        }
    }
    sum += cnt3 * 6;
    for (int i = 1; i <= cnt2; i++) {
        if ((sum + i * 2) % 9 == 0) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

另一种方法（来源jiangly）：

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() {
    std::string n;
    std::cin >> n;
    
    int f = 1;
    for (auto c : n) {
        int d = c - '0';
        int x = d * d;
        int nf = f << d;
        if (x < 10) {
            nf |= f << x;
        }
        nf |= nf >> 9;
        nf &= (1 << 9) - 1;
        f = nf;
    }
    
    if (f & 1) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

D题

每次从当前的填入位置和其后九个位置中选出当前位置可以使用的最大值即可，相对于下标偏移量，对每个值分别$-0，-1，-2，-3…$，选出最大值填入当前位置，再将前面的数字后移填补空缺。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    int n;
    string s;
    cin >> s;
    n = s.size();
    string ans;
    for (int i = 0; i < n; i++) {
        int idx = i, mx = -1;
        for (int j = 0; j < 10 && i + j < n; j++) {
            if (mx < s[i + j] - '0' - j) {
                idx = i + j;
                mx = s[i + j] - '0' - j;
            }
        }
        ans += mx + '0';
        for (int j = idx - 1; j >= i; j--) {
            s[j + 1] = s[j];
        }
    }
    cout << ans << '\n';
    
}

E题

dp题，a，b串的长度都为1000以内，$O(n^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
template<typename T>
inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
void solve() {
    string a, b, c;
    cin >> a >> b >> c;
    int la = a.size(), lb = b.size();
    std::vector<std::vector<int>> dp(la + 1, std::vector<int>(lb + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i <= la; i++) {
        for (int j = 0; j <= lb; j++) {
            if (i < la) {
                chmin(dp[i + 1][j], dp[i][j] + (a[i] != c[i + j]));
            }
            if (j < lb) {
                chmin(dp[i][j + 1], dp[i][j] + (b[j] != c[i + j]));
            }
        }
    }
    cout << dp[la][lb] << '\n';
}

F题

有 $a\equiv b(\bmod m)\Leftrightarrow m\mid(a-b)$，想要找出$[l,r]$之间的$m$的最大值，则需要找出所有$a_i-a_{i-1}$的最大公因数，使用线段树或者ST表实现区间查询。

（模板来源：jiangly）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int __lg(int n) {
    int ret = 0, tmp = 1;
    while (tmp < n) {
        tmp <<= 1;
        ret++;
    }
    return ret;
}
template<typename Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<typename T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<typename T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) >> 1;
            build(p << 1, l, m);
            build(p << 1 | 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) >> 1;
        if (x < m) {
            modify(p << 1, l, m, x, v);
        } else {
            modify(p << 1 | 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) >> 1;
        return rangeQuery(p << 1, l, m, x, y) + rangeQuery(p << 1 | 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    template<typename F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) >> 1;
        int res = findFirst(p << 1, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(p << 1 | 1, m, r, x, y, pred);
        }
        return res;
    }
    template<typename F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<typename F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) >> 1;
        int res = findLast(p << 1 | 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(p << 1, l, m, x, y, pred);
        }
        return res;
    }
    template<typename F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

struct Info {
    int g = 0;
    Info(int g = 0) : g(g) {}
    Info operator+(const Info &other) const {
        return {gcd(g, other.g)};
    }
};
void solve() {
    int n, q;
    cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    SegmentTree<Info> seg(n);
    for (int i = 1; i < n; i++) {
        seg.modify(i, std::abs(a[i] - a[i - 1]));
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << seg.rangeQuery(l, r).g << " \n"[i == q - 1];
    }
}

G题

一道树上dp题。

首先考虑删除单个节点，那么得到的连通图个数就是每个顶点的度数$deg$。

然后考虑以每个顶点$u$做树根的情况$dp[u]$，这里默认根从节点1开始。删除该节点和它的一个子节点$v$，得到的连通分量个数是$dp[u]+dp[v]-2$，dp数组中的数据需要传递给$u$的父节点，因此减2是减去通向它父节点和选择的节点$v$的度数，同时更新一下$ans$，它是选择当前节点及其子节点中能得到的最大值。

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
template<typename T>
inline void chmax(T& a, T b){
    if (a < b) {
        a = b;
    }
}
void solve() {
    int n;
    cin >> n;
    std::vector<std::vector<int>> a(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    std::vector<int> dp(n);
    int ans = 1;
    auto dfs = [&](this auto &&self, int u, int pre) -> void {
        int deg = a[u].size();
        chmax(ans, deg);
        dp[u] = deg - 2;
        for (int v : a[u]) {
            if (v == pre) continue;
            self(v, u);
            chmax(ans, dp[u] + dp[v] + 2);
            chmax(dp[u], dp[v] + deg - 2);
        }
    };
    dfs(0, -1);
    cout << ans << '\n';
}