yoshino-nya

stat
notes

Educational Codeforces Round 195 (Rated for Div. 2)

2026-10-15 22:53:51

link: https://codeforces.com/contest/2276

依旧是打得比较一般的一场

好久没打了

也好久没更新博客了…… 有的 markdown 格式都快忘了，不写怎么行，VS Code 写 md 变得越来越爽了。。。

这场 ABCD 挺简单的，错了几次不应该。E 没有很难，不过写得后面越想脑子越乱，虽然感觉本来也写不出来，但这次有点接近了。

FG 通过人数有点过于少就先不看了。

A

签到题，错了两发，这太不应该了。

/*
date: 2026-10-14 22:37:57
path: ~/Projects/cp_code/codeforces/2276/A.cpp
*/

#include <ios>
#include <iostream>

void solve()
{
    int a, b;
    std::cin >> a >> b;
    if (a <= b) {
        std::cout << "-1\n";
        return;
    }
    if (2 * b <= a) {
        std::cout << b << "\n";
        return;
    }
    for (int i = b; i >= 0; i--) {
        if (2 * i + b - i < a) {
            std::cout << i + 1 << "\n";
            return;
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--)
        solve();
}

B

挺简单的，数一下就行。

/*
date: 2026-10-14 22:50:20
path: ~/Projects/cp_code/codeforces/2276/B.cpp
*/

#include <ios>
#include <iostream>

void solve()
{
    std::string s;
    std::cin >> s;
    // 1010101 -> 1 -> 2 -> 3
    int x = 0, y = 0;
    for (int i = 1; i + 1 < s.size(); i++) {
        if (s[i] != s[i - 1] && s[i] != s[i + 1])
            x = 1;
        else if (s[i - 1] == s[i + 1])
            y = 1;
    }
    std::cout << x + y + 1 << "\n";
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--)
        solve();
}

C

签到，前缀和一下。

/*
date: 2026-10-14 23:00:13
path: ~/Projects/cp_code/codeforces/2276/C.cpp
*/

#include "vector"
#include <ios>
#include <iostream>

void solve()
{
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n + 1), pre(n + 1), cnt(k);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        pre[i] = (pre[i - 1] + a[i]) % k;
        cnt[pre[i]]++;
    }
    int idx = 1;
    long long ans = 0;
    for (int l = 1; l + k <= n; l++) {
        // [l + k, n] 里有多少个 pre[l - 1]
        while (idx < l + k) {
            cnt[pre[idx]]--;
            idx++;
        }
        ans += cnt[pre[l - 1]];
    }
    std::cout << ans << "\n";
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--)
        solve();
}

D

咋说呢，这题也没啥难度吧。

首先，如果一个联通块只有一个点，显然就是无法达成。

如果但凡可以有一种染色方案，那么颜色取个反可以有另一种，所以答案至少就是 2 。

那么我们只需要去确认是否可以达成 Many ，先尝试给每一个联通块染色，优先把相邻的点染色成相反的颜色。

呃，当我没说，这题都不用染色的，只要联通块大小不是 1，至少一定有 2 种方式。所以只需要 check 能不能达成 Many ，那么如果有两个相邻的节点，它们都有多个相邻的节点，这两个点就可以颜色相同，就可以多一种方法。好吧那染色也没毛病，如果存在这种方式，就是至少多了一种不一样的方式。

需要注意的是，如果有多个联通块都为 2 种方案，那么组合一下也会是 Many 。

/*
date: 2026-10-14 23:11:45
path: ~/Projects/cp_code/codeforces/2276/D.cpp
*/

#include <ios>
#include <iostream>
#include <vector>

void solve()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> g(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    std::vector<int> color(n + 1, -1);
    bool ok = false;
    auto dfs = [&](auto&& self, int u) -> void {
        for (auto v : g[u]) {
            if (color[v] == -1) {
                color[v] = 1 - color[u];
                if (g[v].size() > 1 && g[u].size() > 1)
                    ok = true;
                self(self, v);
            }
        }
    };
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (g[i].empty()) {
                std::cout << "Brain Melt\n";
                return;
            }
            color[i] = 0;
            cnt++;
            dfs(dfs, i);
        }
    }
    if (ok || cnt > 1)
        std::cout << "Many\n";
    else
        std::cout << "2\n";
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--)
        solve();
}

E

对于每个左端点 ll ，我们可以找右侧出现子序列 "2025" 和 "2026" 的最小右端点，分别为 r1r_1, r2r_2。

那么仅当 r1<r2r_1 < r_2 时，ll 的右侧会有 bad string，且 bad string 的数量为 cnt=r2−r1cnt = r_2 - r_1 。

对于 [l,r1][l, r_1] 这一段，每个坐标 ii 会被包含在 cntcnt 个 bad string 中，而 (r1,r2)(r1, r2) 这一段，每个坐标 ii 会被包含在 cnt−(i−l)cnt - (i - l) 个 bad string 中。也就是前面一段都是 cntcnt ，后面一段每个比前一个 −1-1 。于是可以用差分来解决，差分还是太强大了。

由于我们可以算出每个 ii 在多少个 bad string 中，所以拿总的字符串数量减去 bad string 的数量就是答案。

我赛时想明白了 [l,r1][l, r_1] 这一段的贡献，后一段本来是没注意，后面又没想明白了。。。不过想到了估计也不太会写这个差分…… 当时是想着前一段用线段树区间加，后一段后面想着用差分但是没搞明白，时间也不够了，越想越乱。

/*
date: 2026-10-14 23:47:59
path: ~/Projects/cp_code/codeforces/2276/E.cpp
*/

#include <algorithm>
#include <array>
#include <ios>
#include <iostream>
#include <set>
#include <vector>

void solve()
{
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    std::vector<std::array<int, 10>> nxt(n);
    std::array<int, 10> lst;
    lst.fill(-1);
    for (int i = n - 1; i >= 0; i--) {
        nxt[i] = lst;
        lst[s[i] - '0'] = i;
    }
    std::vector<std::pair<int, int>> five, six;
    std::multiset<int> six_s, five_s;
    int five_idx = 0, six_idx = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '2') {
            int idx = nxt[i][0];
            if (idx == -1)
                continue;
            idx = nxt[idx][2];
            if (idx == -1)
                continue;
            if (nxt[idx][5] != -1) {
                five.push_back({ i, nxt[idx][5] });
                five_s.insert(nxt[idx][5]);
            }
            if (nxt[idx][6] != -1) {
                six.push_back({ i, nxt[idx][6] });
                six_s.insert(nxt[idx][6]);
            }
        }
    }

    std::vector<long long> diff1(n), diff2(n);
    std::vector<long long> res(n + 1);
    for (int i = 0; i < n; i++) {
        while (five_idx < five.size() && five[five_idx].first < i) {
            five_s.erase(five_s.find(five[five_idx].second));
            five_idx++;
        }
        while (six_idx < six.size() && six[six_idx].first < i) {
            six_s.erase(six_s.find(six[six_idx].second));
            six_idx++;
        }
        if (five_s.empty()) {
            break;
        }
        int r1 = *five_s.begin();
        int r2 = n;
        if (!six_s.empty()) {
            r2 = std::min(r2, *six_s.begin());
        }

        if (r1 > r2) {
            continue;
        }
        int cnt = r2 - r1;

        diff1[i] += cnt;
        if (r1 + 1 < n) {
            diff2[r1 + 1] -= 1;
        }
        if (r2 < n) {
            diff1[r2] -= 1;
            diff2[r2] += 1;
        }
    }
    // std::cerr << format("{} \n {} \n", diff1, diff2);
    long long cur = 0, add = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff1[i - 1];
        add += diff2[i - 1];
        cur += add;
        // std::cerr << std::format("{} {} | {}", cur, add, " \n"[i == n]);
        // cur += add;
        long long ans = 1LL * i * (n - i + 1) - cur;
        std::cout << ans << " \n"[i == n];
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--)
        solve();
}