Educational Codeforces Round 174 (Rated for Div. 2)(部分题解)

wirepuller_king

已于 2025-02-22 20:37:45 修改

阅读量1.2k

点赞数 16

分类专栏： codeforces 文章标签：算法 c++

于 2025-02-22 20:35:52 首次发布

本文链接：https://blog.csdn.net/wirepuller_king/article/details/145759170

版权

codeforces 专栏收录该内容

12 篇文章

订阅专栏

补题链接

A. Was there an Array?

思路：大眼观察法加小猜一手，对问题有用的部分是当出现”101“即不能成立，因为出现此时不能找到能成立的数字串，这里的py代码比c++代码简单。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n, m, k;
    cin >> n;
    vi a(n-1);
    for (int i = 0; i<n-2; i++){
        cin >> a[i];
    }
    int flag = 0;
    for (int i = 2; i<n-2; i++){
        if (a[i] == 1 && a[i-2]==1 && a[i-1] == 0){
            flag = 1;
            break;
        }
    }
    if (flag == 1){
        cout << "NO" << endl;
    }
    else cout << "YES" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    
    return 0;
}

t = int(input())
for i in range(t):
    n = int(input())
    s = list(input().split())
    s = "".join(s)
    if "101" in s:
        print("NO")
    else:
        print("YES")

B. Set of Strangers

思路：这里需要观察出一种颜色最多只需两次就可以除去完，所以只需要区分完每种颜色需要一次还是两次就可以，需要两次的情况是相同颜色公用一条边。最后要去除需要最大次数的一种颜色，即判断是减去1还是2.

AC代码：

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(n)]
    hasColor = [0]*(n*m)
    hasBad = [0]*(n*m)
    for i in range(n):
        for j in range(m):
            hasColor[a[i][j]-1] = 1
            if i+1 < n and a[i][j] == a[i+1][j]:
                hasBad[a[i][j]-1] = 1
            if j+1 < m and a[i][j] == a[i][j+1]:
                hasBad[a[i][j]-1] = 1
    print(sum(hasColor)+sum(hasBad)-(2 if hasBad.count(1) != 0 else 1))

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>

void solve()
{
    int n, m, k;
    cin >> n >> m;
    vvi a(n, vi(m));
    vector<int> p(n*m+1);
    for (int i = 0; i<n; i++){
        for (int j = 0; j<m; j++){
            cin >> a[i][j];
            p[a[i][j]] |= 1;
            if (i && a[i-1][j] == a[i][j]) p[a[i][j]] |= 2;
            if (j && a[i][j-1] == a[i][j]) p[a[i][j]] |= 2;
        }
    }
    int o = std::count(p.begin(), p.end(), 1);
    int t = std::count(p.begin(), p.end(), 3);
    cout << o+t*2-(t?2:1) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    
    return 0;
}

两种代码有异曲同工之妙。

C. Beautiful Sequence

思路：这道题还是很需要思维变化的，其实是一道动态规划的变种题.

首先我们要通过题意分析得出要求即是一个串里面有多少种1222...2223这样的子序列，很像求一个串里面有多少种指定的字符串，只是这里中间的2的数量我们无法确定而已，但我们可以对其进行分析，并采用动态规划的思路来做。所以对 $a_{i}$ 为2时进行讨论分析：以1212112串为例，每当遇到2的时候结果我们可以分成三部分：1.上一个2的种类数，2.上个2种类后面都加上这个2的种类数，3.这个2单独与该2前面1的种类数。比如

遇到第一个2时：

这一种组合

遇到第二个2时（1212）：

（蓝色表示用到了这一个2）

遇到第三个2时（1212112）：

会有这12种组合

所以我们的代码就简单了：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;

void solve()
{
    int n, m, k;
    cin >> n;
    vector<int> dp(4,0);
    dp[0] = 1;
    for (int i = 1; i<=n; i++){
        int x;
        cin >> x;
        if (x == 2) dp[x] = (dp[x] + dp[x]) % mod;
        dp[x] = (dp[x] + dp[x-1]) % mod;
    }
    cout << dp[3] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    
    return 0;
}

D. Palindrome Shuffle

思路：首先我们通过题意知回文的话，从两边先开始往里找到不符合的一段，那结果必定是这一段的前缀或者后缀（这里我们对其进行反转一次就可以省去一些代码，从而求两次前缀），我们通过二分来求它的前缀，在这部分要讨论清楚：

下列代码m为前缀边界，当m<nn/2时，前m个里面应该包含后m个里的，而中间的应该前后对应

而m>nn/2时，前 $m^{1}$ 应该包含后 $m^{1 }$ ,而中间的应该为偶数才能促成回文。

我们的代码先统计了前m的字母，在巧妙地处理了就能够完成这样的操作，可以多看几遍代码加以理解。

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define endl '\n'
void solve()
{
    string s;
    cin >> s;
    int n = s.size(), num = 0;
    while (num<n/2 && s[num] == s[n-1-num]) num++;
    int nn = n - 2*num;
    s = s.substr(num, nn);
    int ans = nn;
    for (int z = 0; z<2; z++){
        int l = -1, r = nn+1;
        while (l + 1 < r){
            int m = (l+r)/2;
            vector<int> cnt(26);
            for (int i = 0; i<m; i++){
                cnt[s[i]-'a']++;
            }
            bool ok= true;
            for (int i = 0; i<min(nn/2, nn-m); i++){
                char c = s[nn-1-i];
                if (i < m){
                    ok &= cnt[c-'a'] > 0;   //确保后m1在前m1中出现过
                    cnt[c-'a']--;   // 减一操作，使得后面m<nn/2时求中间的字母出现为偶数个作准备
                }
                else{
                    ok &= (c == s[i]);     // 确保m<nn/2时，中间部分相等
                }
            }
            for (auto x : cnt){
                ok &= (x % 2 == 0);     // m>nn/2时，中间的字母出现为偶数次
            }
            if (ok) r = m;
            else l = m;
            
        }
        ans = min(ans, r);
        reverse(s.begin(), s.end());
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    
    return 0;
}