Codeforces Round 981 (Div. 3)

如果没有特殊情况，以后每场 CF 都会写题解 > <

A. Sakurako and Kosuke

奇偶题。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int t;
    cin >> t;

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

        cout << (n & 1 ? "Kosuke" : "Sakurako") << "\n";
    }

    return 0;
}

B. Sakurako and Water

统计$2n-1$ 条从左上到右下的斜线上所有负数的最小值，再求和即是答案。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int t;
    cin >> t;

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

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

        ll sum = 0;
        for (int k = -n + 1; k < n; k++) {
            int mx = 0;
            for (int i = max(-k, 0); i + k < n && i < n; i++) {
                if (a[i][i + k] < 0) {
                    mx = max(mx, -a[i][i + k]);
                }
            }
            sum += mx;
        }
        cout << sum << "\n";
    }

    return 0;
}

C. Sakurako’s Field Trip

从最中间开始确定，这样两边的就只和靠中间的那个数有关，贪心地交换即可。最后统计所求的数量。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    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; n / 2 + i < n; i++) {
            if (a[n / 2 + i] == a[n / 2 + i - 1] || a[n - 1 - n / 2 - i] == a[n - 1 - n / 2 - i + 1]) {
                swap(a[n / 2 + i], a[n - 1 - n / 2 - i]);
            }
        }

        int cnt = 0;
        for (int i = 1; i < n; i++) {
            cnt += a[i] == a[i - 1];
        }
        cout << cnt << "\n";
    }

    return 0;
}

D. Kousuke’s Assignment

开个 map 记录前缀和，遇到前缀和相同的就记录答案，并将桶清空（因为要求区间不能相交）。

注意不要用 unordered_map，会 T。

时间复杂度$\Theta(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int t;
    cin >> t;

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

        map<ll, int> mp;
        mp[0] = 1;
        ll sum = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            sum += x;
            if (mp.count(sum)) {
                ans++;
                mp.clear();
            }
            mp[sum]++;
        }

        cout << ans << "\n";
    }

    return 0;
}

E. Sakurako, Kosuke

小清新置换环题。

每个置换环对答案的贡献是 (环大小 - 1) / 2。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int t;
    cin >> t;

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

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

        vector<vector<int>> cycs;
        vector<int> vis(n);
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue;
            int u = i;
            vector<int> cyc;
            do {
                cyc.push_back(u);
                vis[u] = true;
                u = p[u];
            } while (u != i);
            cycs.push_back(cyc);
        }

        int res = 0;
        for (auto& cyc : cycs) {
            res += (cyc.size() - 1) / 2;
        }
        cout << res << "\n";
    }

    return 0;
}

F. Kosuke’s Sloth

递推数列具有模周期性，而且我们知道，对于斐波那契数列，这个周期不会超过$6\times$ 模数。暴力计算一个周期内的所有斐波那契数值，统计为 0 的个数，再计算所求。

时间复杂度$\Theta\left( \sum k\log k \right)$。

不太理解为什么要用巨大的$n$ 然后取模，本题完全可以将$n$ 的范围设为$10^{9}$，不要求取模。。

赛时因为取模不到位 WA 了两次，二分不单调的 cnt 数组 WA 了一次，式子推错了 WA 了一次。。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;

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

    int t;
    cin >> t;

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

        if (k == 1) {
            cout << (n % mod) << "\n";  // 这里也要取模
        } else {
            vector<int> f(6 * k), cnt(6 * k, mod);
            f[0] = f[1] = 1;
            cnt[0] = cnt[1] = 0;
            for (int i = 2; ; i++) {
                f[i] = (f[i - 1] + f[i - 2]) % k;
                cnt[i] = cnt[i - 1] + (f[i] == 0);
                if (f[i] == 1 && f[i - 1] == 1) {
                    int len = i - 1;
                    cout << (((n - 1) / cnt[len] % mod * len) % mod + lower_bound(cnt.begin(), cnt.end(), (n - 1) % cnt[len] + 1) - cnt.begin() + 1) % mod << "\n";
                    break;
                }
            }
        }
    }

    return 0;
}

G. Sakurako and Chefir

树上倍增。

本题需要求每个点$u$ 向上跳至多$x$ 步到$v$，$\operatorname{dep} u-\operatorname{dep} v+\operatorname{dis}'v$ 的最大值，这里的$\operatorname{dis}'v$ 表示$v$ 不经过点$u$ 向下到叶子的最大距离。

因此需要维护每个点向下的最长链和次长链，如果$u$ 在最长链上，那么$\operatorname{dis}'v$ 表示$v$ 的次长链的长度，否则是最长链的长度。

用类似求 LCA 的方法做树上倍增即可维护。

时间复杂度$\Theta(n\log n+q\log n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int t;
    cin >> t;

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

        vector<vector<int>> E(n);
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            E[u].push_back(v);
            E[v].push_back(u);
        }

        vector p(n, vector<int>(20, -1));
        vector<int> dep(n);
        vector<int> dis(n), dis2(n);   // 到叶子的最长距离和次长距离
        auto dfs1 = [&](this auto&& self, int u) -> void {
            for (auto v : E[u]) {
                if (v == p[u][0]) continue;
                dep[v] = dep[u] + 1;
                p[v][0] = u;
                for (int bit = 1; bit <= __lg(dep[v]); bit++) {
                    p[v][bit] = p[p[v][bit - 1]][bit - 1];
                }
                self(v);
                int tmp = dis[v] + 1;
                if (tmp >= dis[u]) {
                    dis2[u] = dis[u];
                    dis[u] = tmp;
                } else if (dis[v] + 1 >= dis2[u]) {
                    dis2[u] = tmp;
                }
            }
        };
        dfs1(0);
        
        vector<array<int, 20>> dp(n);
        auto dfs2 = [&](this auto&& self, int u) -> void {
            for (auto v : E[u]) {
                if (v == p[u][0]) continue;
                dp[v][0] = ((dis[u] == dis[v] + 1) ? dis2[u] : dis[u]) + 1;
                for (int bit = 1; bit <= __lg(dep[v]); bit++) {
                    dp[v][bit] = max(dp[v][bit - 1], dp[p[v][bit - 1]][bit - 1] + (1 << bit - 1));
                }
                self(v);
            }
        };
        dp[0][0] = dis[0];
        dfs2(0);

        int q;
        cin >> q;

        while (q--) {
            int u, x;
            cin >> u >> x;
            u--;
            x = min(x, dep[u]);

            int res = dis[u], sum = 0;
            for (int bit = 19; bit >= 0; bit--) {
                if ((1 << bit) <= x) {
                    res = max(res, dp[u][bit] + sum);
                    u = p[u][bit];
                    x -= (1 << bit);
                    sum += (1 << bit);
                }
            }

            cout << res << " \n"[!q];
        }
    }

    return 0;
}