2025年2月19日

Educational Codeforces Round 174 (Rated for Div. 2)

比赛链接：https://codeforces.com/contest/2069

这场感觉算正常发挥吧。D题1800人AC，我做不出来倒是正常。

至于这B和C，过的人都不少，写出来的速度有点慢了。这个C我怎么想得有点烧脑。。。然后瞎搞对了。

B写得也有点烂。

A

当 \(b_i\) 为 \(1\) 时，\(b_{i-1}=b_i=b_{i+1}\) ，只有出现 \(101\) 时会有冲突，其他的都可以成立。

void solve()
{
    int n;
    cin>>n;
    vi a(n+1);
    for(int i=2;i<n;i++)
        cin>>a[i];
    for(int i=3;i+1<=n-1;i++){
        if(a[i-1]==1&&a[i+1]==1&&a[i]==0){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
}

B

本来感觉这题可能也不好做的。。

每次需要选1种颜色，且不能有相邻的，那么每种颜色需要几次操作呢？我们有必要DFS吗？没有。其实一种颜色，操作次数只会是1次或者2次。

直接枚举就行了，如果一种颜色，它有相邻的块，那么需要两次操作，否则都是1次操作。

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vi> a(n + 1, vi(m + 1));
    vi cnt(n * m + 1);
    set<int> st;
    int mx = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            cnt[a[i][j]]++;
            cmax(mx, cnt[a[i][j]]);
            st.insert(a[i][j]);
        }
    vector<bool> ok(n * m + 1);
    auto check = [&](int x, int y) {
        vector<pii> dirs { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        for (auto [xx, yy] : dirs) {
            int nx = xx + x, ny = yy + y;
            if (nx < 1 || nx > n || ny < 1 || ny > m)
                continue;
            if (a[nx][ny] == a[x][y])
                return true;
        }
        return false;
    };
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check(i, j))
                ok[a[i][j]] = true;
        }
    }
    int ans = 0;
    for (auto x : st)
        ans += (ok[x] ? 2 : 1);
    if (ans != sz(st))
        ans -= 2;
    else
        ans -= 1;
    cout << ans << '\n';
}

C

首先一定要知道哪些情况是符合的，才好思考。。

我本来以为是只有 123 是可以的，，然后测了样例发现不对，它其实还有解释。那我们发现只需要首尾是1和3，中间2的数量无所谓。。那么就有点不好写。。

但是考虑DP就发现很简单，设\(dp_{0/1}\) 代表以 \(1\) 和 \(2\) 结尾的合法子序列的数量。那么只有遇到 \(3\) 时，答案就可以加上 \(dp_{i-1}\) 。

如果 \(a_i\) 是 \(1\) ，那么显然 \(dp_{i,0}=dp_{i-1}+1\) ，如果 \(a_i\) 是 \(2\) , \(dp_{i,1}=2dp_{i-1,1}+dp_{i-1,0}\) 。

void solve()
{
    int n;
    cin >> n;
    vi a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<vl> dp(n + 1, vl(3));
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        if (a[i] == 1)
            dp[i][0]++;
        else if (a[i] == 2) {
            dp[i][1] = (dp[i][1] + dp[i - 1][0] + dp[i][1]) % mod;
        } else
            ans += dp[i][1], ans %= mod;
        // if (a[i] == 3)
        // cerr << dp[i][0] << " " << dp[i][1] << '\n';
    }
    cout << ans << '\n';
}

这里好唐，想了很久才想明白。。。

然后就战斗结束了。D感觉确实很难不看题解写出来。

D

use binary search ，如果当前字符串首尾相同，那显然我们不需要进行任何操作。所以我们可以先把字符串转换成首尾不同的状态，然后我们二分检查的长度。由于首尾不同，那么肯定要么是从开头开始，要么是在末尾结束。

对于在末尾结束的情况，我们可以用反转后的字符串来计算，所以我们只用考虑第一种情况。用前缀和存一下，就可以检查是否能构成回文串了。

void solve()
{
    string s;
    cin >> s;
    int n = sz(s);
    for (int i = 0; i < n - i - 1; i++) {
        if (s[i] != s[n - i - 1]) {
            s = s.substr(i, n - i - 1 - i + 1);
            break;
        }
    }
    if (sz(s) == n && s.front() == s.back()) {
        cout << "0\n";
        return;
    }
    cerr << s << "\n";
    n = sz(s);
    s = " " + s;

    vector<vi> pre(n + 1, vi(26));
    auto check = [&](int len) {
        if (len < n / 2) {
            for (int i = len + 1; i <= n / 2; i++) {
                if (s[i] != s[n - i + 1])
                    return false;
            }
        }
        for (int i = 0; i < 26; i++) {
            if (len >= n / 2) {
                if (pre[len][i] < pre[n][i] - pre[len][i])
                    return false;
            } else {
                if (pre[len][i] > pre[n][i] - pre[len][i])
                    return false;
            }
        }
        return true;
    };
    int ans = n;
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1], pre[i][s[i] - 'a']++;
    int lo = 1, hi = n;

    while (lo < hi - 1) {
        int mid = (lo + hi) >> 1;
        if (check(mid))
            hi = mid;
        else
            lo = mid;
    }
    cmin(ans, hi);
    reverse(ALL(s));
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1], pre[i][s[i] - 'a']++;
    lo = 1, hi = n;

    while (lo < hi - 1) {
        int mid = (lo + hi) >> 1;
        if (check(mid))
            hi = mid;
        else
            lo = mid;
    }
    cmin(ans, hi);
    cout << ans << '\n';
}