当前位置：首页 > article >正文

Educational Codeforces Round 174 (Rated for Div. 2)（ABCD）

article 2025/2/25 6:10:46

A. Was there an Array?

翻译：

        对于整数数组 $a_{1},a_{2},...,a_n$ ，我们将其相等特征定义为数组 $b_{2},b_{3},...,b_{n-1}$ ，其中，如果数组 a 的第 i 个元素等于其两个相邻元素，则 $b_{i}=1$ ；如果数组 a 的第 i 个元素不等于其至少一个相邻元素，则 $b_i=0$ 。

        例如，对于数组 [1,2,2,2,3,3,4,4,4]，相等特征为 [0,1,0,0,0,0,1,1]。

        给你数组 $b_{2},b_{3},...,b_{n-1}$ 。你的任务是确定是否存在这样一个数组 a具有相同特征。

思路：

如果b存在101则错误。

实现：

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

void solve(){
  int n;  
  cin>>n;
  vector<int>b(n-2);
  for (int i=0;i<n-2;i++) cin>>b[i];
  if (n<=4){
    cout<<"YES"<<endl;
  }else{
    for (int i=0;i<n-4;i++){
      if (b[i]==1 && b[i+1]==0 && b[i+2]==1){
        cout<<"NO"<<endl;
        return;
      }
    }
    cout<<"YES"<<endl;
  }
}

int main(){
    // 关闭输入输出流同步
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    ll t;cin>>t;
    while (t--) solve();
}

B. Set of Strangers

翻译：

  给你一张 n 行 m 列的表格。最初，第 i 行第 j 列的单元格的颜色为 $a_{i,j}$ 。

        如果两个单元格不共用一条边，那么这两个单元格就是陌生人。陌生人可以用角接触。

        如果单元格集合中的所有单元格对都是陌生人，我们就说这个单元格集合是陌生人集合。根据定义，不超过一个单元格的集合就是陌生人集合。

        在一个步骤中，你可以选择任意一个陌生人集合，使其中的所有单元格都具有相同的颜色，然后给所有单元格涂上其他颜色。你可以选择得到的颜色。

        要使整个表格的颜色相同，最少需要多少步？

思路：

对于所有相同颜色的块，如果存在相邻的块，则要2次操作使所有块变为同一颜色，否则只用1次操作。

得到所有颜色的变换操作数，再减去所有颜色转换操作数中的最大值。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int>> direct = {{0,1},{0,-1},{1,0},{-1,0}};
void solve(){
  int n,m;  
  cin>>n>>m;
  vector<int> cnts(n*m+1,0);
  vector<vector<int>> graph(n+2,vector<int>(m+2,0));
  for (int i=1;i<=n;i++){
    for (int j=1;j<=m;j++){
        cin>>graph[i][j];
    }
  }
  int mx = 0,summ = 0;
  for (int i=1;i<=n;i++){
    for (int j=1;j<=m;j++){
        int f = 0;
        for (auto d:direct){
            if (graph[i][j]==graph[i+d[0]][j+d[1]]){
                f = 1;
                break;
            }
        }
        cnts[graph[i][j]] = max(1+f,cnts[graph[i][j]]);
    }
  }
  for (int i=1;i<=n*m;i++){
    summ+=cnts[i];
    mx = max(mx,cnts[i]);
  }
  cout<<summ-mx<<endl;
}

int main(){
    // 关闭输入输出流同步
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    ll t;cin>>t;
    while (t--) solve();
}

C. Beautiful Sequence

翻译：

如果下列条件成立，我们就称一个整数序列为优美序列：

它的长度至少为 3；
除第一个元素外，每个元素的左边都有一个比它小的元素；
除最后一个元素外，每个元素的右边都有一个比它大的元素；

        例如，[1,4,2,4,7] 和 [1,2,4,8] 很美，但 [1,2]、[2,2,4] 和 [1,3,5,3] 却不美。

        回想一下，子序列是指在不改变其余元素顺序的情况下，通过删除某些元素可以从另一个序列得到的序列。

        给你一个大小为 n 的整数数组 a，其中每个元素都是从 1 到 3。你的任务是计算数组 a 的优美子序列的个数。

思路：

按照条件优美序列为122...23。求满足条件的序列数量。使用dp状态机。

        dfs( i , k ) 为[ : i ]中以k为结尾的序列数量。

递推公式：

dfs( i , k) = dfs( i-1 , k);

        当k==3时，如果a[i]==3，则当前3与前面的2结尾数字匹配 dfs(i , k)+=dfs(i-1 , 2)

        当k==2时，如果a[i]==2，则当前2与前面的1或2结尾数字匹配 dfs(i , k) += dfs(i-1 , 1)

当k==1时，如果a[i]==1，1开头的数量+1 dfs( i , k )++；

边界条件：

if (i<0) return 0;

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
void solve(){
  ll n;  
  cin>>n;
  vector<ll> a(n);
  for (ll i=0;i<n;i++) cin>>a[i];
  vector<vector<ll>> memo(n,vector<ll>(4,-1));
  // dp状态机：[:i] 中以 k 结尾的 子串数量
  auto dfs = [&](auto&& dfs,ll i,ll k)->ll{
    if (i<0) return 0;
    ll &res = memo[i][k];
    if (res!=-1) return res;
    res = dfs(dfs,i-1,k);
    if (k==3 && a[i]==3){
      res = (res+dfs(dfs,i-1,2))%mod;
    }else if (k==2 && a[i]==2){
      res = (res+dfs(dfs,i-1,2)+dfs(dfs,i-1,1))%mod;
    }else if (k==1 && a[i]==1){
      res += 1;
    }
    return res;
  };
  cout<<dfs(dfs,n-1,3)<<endl;
}

int main(){
    // 关闭输入输出流同步
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    ll t;cin>>t;
    while (t--) solve();
}

D. Palindrome Shuffle

翻译：

给你一个由小写拉丁字母组成的字符串 s。

        您可以对字符串 s 执行以下操作：选择 s 的一个连续子串（可能为空），然后将其洗码（按您的意愿重新排列子串中的字符）。

        回顾一下，回文字符串是指从第一个字符到最后一个字符以及从最后一个字符到第一个字符的读法相同的字符串。例如，字符串 a、bab、acca、bcabcbacb 是回文字符串，但字符串 ab、abbbaa、ccbb 不是回文字符串。

        您的任务是确定子串的最小可能长度，必须在该子串上执行上述操作才能将给定的字符串 s 转换成一个回文字符串。

思路：

向左右指针去除左右边界相同的字符，剩余的部分 s 为由左端点开始重排或从右端点开始重排。对 s 进行中心扩展得到其最大的回文，如果回文的左剩余与右剩余部分进行重排后相同则，则对这些剩余部分进行重排即可。否则要重拍的部分必定在一半s以上，记录 s 的每种字符的位置，比较每种字符要重排的最大位置。

实现：

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

int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    string s;
    cin >> s;
    int n = s.size();
    int l = 0, r = n-1;
    while (l < r && s[l] == s[r]) {
      l++;
      r--;
    }
    if (l > r) {
      cout << "0\n";
      continue;
    }
    s = s.substr(l, r-l+1);
    n = s.size();
    l = n/2-1, r = n/2;
    while (l >= 0 && s[l] == s[r]) {
      l--;
      r++;
    }
    string L = s.substr(0, l+1);
    string R = s.substr(r);
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());
    if (L == R) {
      cout << l+1 << '\n';
      continue;
    }

    int ans = n;
    for (int _ = 0; _ < 2; _++) {
      vector<vector<int>> pos(26);
      int res = 0;
      for (int i = 0; i < n; i++) {
        pos[s[i]-'a'].push_back(i);
      }
      for (vector<int>& v: pos) {
        if (v.empty()) continue;
        res = max(res, v[(int)v.size()/2-1]+1);
      }
      ans = min(ans, res);
      reverse(s.begin(), s.end());
    }
    cout << ans << '\n';
  }
}