在这里插入图片描述

这一场我没有打，是后面的时候补的，这一场难度感觉还好，其中CD乍一看会觉得比较难，但是仔细想一下就会觉得很简单的了

A-Was there an Array?(模拟)

给定一个数组b,从 b 2 b_2 b2​到 b n b_n bn​，和a数组对应,如果 b i b_i bi​=1那么 a i a_i ai​ 和它两边的数字都相等，反之就是两边肯定至少有一个数字和它不相等，现在给定一个b数组，问你是否存在合适a数组对应给定的b数组。

很简单，想一下就能知道，当且仅当 b i b_i bi​=0并且 b i − 1 b_{i-1} bi−1​=1, b i + 1 b_{i+1} bi+1​=1的时候没有合适的a数组对应，所以只要遍历一遍判断是否存在这种情况，如果存在就输出NO，反之输出YES就好了。

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD=1e9+7;
const int N=1000100;

void init() {
   

}

int a[N];
int pre[N];

void solve() {
   
    init();

    int n;
    cin>>n;
    for(int i=1;i<=n-2;i++) cin>>a[i];

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


signed main() {
   
     //ios::sync_with_stdio(false);
     //cin.tie(0);
     //cout.tie(0);

    int t=1;
    cin>>t;

    while(t--) {
   
        solve();
    }
    return 0;
}

B-Set of Stranger(模拟)

给定一个二维数组a, a i , j a_{i,j} ai,j​是第i行第j列的颜色，每次操作都可以将不相邻的同一个颜色的格子染色成同一个颜色，问你将整个二维数组染成同一个颜色最少需要多少步数

（吐槽：自从codeforces开始为了防止AI做题，题面就开始变得很绕，防AI是防住了，人也被防住了可还好)

简单分析，其实这道题很简单，因为它说不相邻，大可想想不相邻的情况下最贪心的操作是怎么样子的，就会发现按照对角的方式染色，那么整个二维数组只需要两次染色，但是他还要同一个颜色，所以说：首先设定所有颜色都变成某一个颜色，对于其他颜色而言，如果这个颜色没有相邻的格子就只需要一次操作，如果这个颜色有相同的颜色就需要两次操作。

得到了这个结论，那么我们就只需要记录所有颜色需要步数之和以及最大值，然后让步数之和减去最大值就行了,代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD=1e9+7;
const int N=1000100;
void init() {
   

}

int a[707][707];
int pre[N];

void solve() {
   
    init();

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
   
        for(int j=1;j<=m;j++) {
   
            cin>>a[i][j];
        }
    }

    map<int,int>mp;
    int res=0;
    for(int i=1;i<=n;i++) {
   
        for(int j=1;j<=m;j++) {
   
            if(!mp[a[i][j]]) {
   
                mp[a[i][j]]=1;
            }
            if(i>1 && (a[i][j]==a[i-1][j])) mp[a[i][j]]=2;
            else if(i<n && a[i][j]==a[i+1][j]) mp[a[i][j]]=2;
            else if(j>1 && a[i][j]==a[i][j-1]) mp[a[i][j]]=2;
            else if(j<n && a[i][j]==a[i][j+1]) mp[a[i][j]]=2;
        }
    }
    int maxvalue = 0;

    for(auto [x,y] : mp) {
   
        res += y;
        maxvalue = max(maxvalue,y);
    }
    cout<<res-maxvalue<<"\n";
}


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(DP)

给定一个数组，如果一个子序列长度至少为3除了第一个数之外每一个数都至少比前面一个数大，同时除去最后一个数每一个数都至少比后面的一个数小就是漂亮序列，问你有多少个序列。结果对998244353求余

这道题也很简单，乍一看确实挺难的，但是看一下题目条件1≤ a i a_i ai​≤3就能梳理出来这样一个结论：这个子序列肯定前面有且仅有一个1，后面有且仅有一个3，剩下的全为2。

知道了这个结论后就该计算这样的子序列有多少个了。这里其实是很经典的一种DP（刚开始我没想到真的是太蠢了），就是那种给定你一个数组要求你计算子序列是1 2 3 …这样子排列的个数，这种DP做法,dp[i]为以i为结尾的子序列个数，直接dp[i] = dp[i] + dp[i-1] 就可以了，但是这里要注意的是2可以不止一个，所以对于dp[2]而言，应该还要加上原本的dp[2]，就是dp[2] = (dp[2] + dp[2] + dp[1] ) % 998244353

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD=998244353;
const int N=1000100;

void init() {
   

}

int a[N];
int pre[N];

void solve() {
   
    init();

    //当选定好两端的时候，只要大于第一个数字并且小于最后一个数字就满足条件
    //1<ai<3
    //第一个数字肯定是1，最后一个数字肯定是3
    //找2的个数

    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
   
        cin>>a[i];
    }

    int num1=0;
    int num2=0;
    int num3=0;

    for(int i=1;i<=n;i++) {
   
        if(a[i]==1) num1++;
        else if(a[i]==2) num2 = (num1 + num2 + num2) % MOD;
        else {
   
            num3 = (num3 + num2) % MOD;
        }
        //cout<<i<<" "<<num1<<" "<<num2<<" "<<num3<<"\n";
    }
    cout<<num3<<"\n";
}


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(二分+模拟)

给定一个字符串s，你能对其进行一次操作，可以选定一个(l,r),能对[l,r]范围内的字符进行重组，问你选定的区间的最小长度。

众所周知，当问你最小，最大问题的时候，可以优先去考虑二分三分的做法，那么二分三分的条件是什么，就是要有一定的顺序关系，这里的长度是否满足一定的顺序关系，我们可以发现，当某个长度x满足条件的时候，那么x+1肯定满足条件，满足二分条件。

然后就要考虑二分之后如何check当前点是否满足条件，题目是已经给定s的长度为偶数的情况下，必定存在满足条件的x的。首先我们观察可以发现：再最开始的时候，如果两端的字符相等，那么可以不用管这两个字符，一直到两端不相等的时候，剩下的字符串肯定要从某一端开始。

所以我们可以从某一端开始检查长度为mid的情况，首先看这一段长度为mid的是否能和另一边对应的字符相等，然后检查剩余的字符是否能够一一对应即可，也就是要两边的字符个数相等。

代码如下：


#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD=998244353;
const int N=1000100;

void init() {
   

}

int a[N];
int b[N];

void solve() {
   
    init();

    string s;
    cin>>s;
    int n=s.length();

    int i=0;
    while(i < n && s[i] == s[n - i - 1]) i++;

    //cout<<i<<" "<<n<<"\n";
    if(i==n) {
   
        cout<<0<<"\n";
        return ;
    }
    n -= 2 * i;

    s = s.substr(i,n);

    //cout<<s<<"\n";

    int ans = n;

    for(int t=0;t<2;t++) {
   
        int l=0,r=n;

        while(l < r) {
   
            int mid = (l+r)>>1;
            vector<int> v(26,0);

            for( i=0;i<n;i++){
   
                v[s[i]-'a']++;
            }

            int sign=1;
            for( i=0;i<min(n/2,n-mid);i++) {
   
                char c = s[n-i-1];

                if(i < mid) {
   
                    sign &= (v[c-'a'] > 0);
                    v[c-'a']-=2;
                }

                else {
   
                    sign &= (s[i] == c);
                }
            }

            for(auto num : v) {
   
                sign &= (num % 2 ==0);
            }

            // cout<<mid << " " << sign<<"\n";
            if(sign) r=mid;
            else l = mid+1;
        }

        ans = min(ans,r);
        reverse(s.begin(),s.end());
    }
    cout<<ans<<"\n";
}


signed main() {
   
     //ios::sync_with_stdio(false);
     //cin.tie(0);
     //cout.tie(0);

    int t=1;
    cin>>t;

    while(t--) {
   
        solve();
    }
    return 0;
}