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\) 时会有冲突，其他的都可以成立。

C++

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次操作。

C++

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}\) 。

C++

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感觉确实很难不看题解写出来。