https://ac.nowcoder.com/acm/contest/127703#question周赛131链接

C题：题意为给定a,b数组，且保证a数组大小≥b数组大小，然后给出俩种操作，目标是要判断数组A能否通过无限次操作构建出数组B。

1.删除a数组内的一个元素，后让后面的元素向前移动
2.选择a的任意一个元素-1.
因为操作次数为无限次，即通过无限次操作2可让ai取到(0,ai]范围内的任意一个数
此时假定拿出bj这个数字，a数组中下标<j的位置的数进行操作2不会对bj的构成产生影响
那么我们需要在a数组中下标>=j的位置找到第一个>=bj的数才能构成bj，至于为什么要找第一个，因为如果你往后找就意味着你要删除更多的元素，这样就有可能让b数组后面的元素更难构成。
这样我们从b数组的第一位开始不断在a数组中寻找从上一个位置开始，第一个≥bj的数的位置即可，具体代码如下 
       int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] >= b[j]) {
            i++;
            j++;
        } else {
            i++;
        }
    }
    if (j == m) cout << "YES\n";
    else cout << "NO\n";

D题：DP板子题，找到给出a数组中最长的特点序列

首先序列要求相邻两个元素的差的绝对值恰好为1
此时我们假定当前dp数据为ai，那么ai只有可能在ai-1和ai+1的基础上更新
此时只要保证ai-1和ai+1的下标不越界即可，注意ai本身也可以算一个子序列，故初始长度为1
代码如下： 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e15;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> dp(n + 2, 0); 
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        int x = a[i];
        int cur = 1; 
        if (x - 1 >= 1) cur = max(cur, dp[x - 1] + 1);
        if (x + 1 <= n) cur = max(cur, dp[x + 1] + 1);
        dp[x] = max(dp[x], cur); 
        ans = max(ans, cur);
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
}

E题：题意为可以用相邻俩个糖果盒中的各1颗糖换取一次在任意糖果盒+1颗糖的机会，要求最大化最多盒子中的糖果数量

对于每个糖果盒ai，如果要以ai作为最后剩下的糖果盒的话
因为ai糖果盒的糖果要尽力保留，故不取出，因此，ai能够获得的糖果可以由a1到ai-1和ai+1到an俩个区域提供
然后我们可以预处理出每个左区域和右区域能够提供的糖果数量
再枚举i作为最后的糖果盒，每次更新ans即可，时间复杂度O(n)

那么该怎么预处理左右区域呢？

因为每次只可以选相邻的俩个盒子取糖果，我们就可以用cur变量表示出之前那个糖果盒还剩下的糖果数量
又因为最多拿的次数是取决于这俩个盒子中糖果较少的那个，就可以每次取最小值更新，然后不断累加即可
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e15;
void solve(){
    int n;cin>>n;
    vector<int> a(n+1),pre1(n+2),pre2(n+2);
    for(int i=1;i<=n;i++)cin>>a[i];
    int cur=0,sum=0;
    for(int i=1;i<=n;i++){
        int mi=min(cur,a[i]);
        sum+=mi;
        cur=a[i]-mi;
        pre1[i]=sum;
    }
    cur=0,sum=0;
    for(int i=n;i>=1;i--){
        int mi=min(cur,a[i]);
        sum+=mi;
        cur=a[i]-mi;
        pre2[i]=sum;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int bb=a[i]+pre1[i-1]+pre2[i+1];
        ans=max(ans,bb);
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
}

F题：给出一个合法括号序列，给出染色规则，求出最大不同染色方案数

染色规则：
1.每对匹配的括号染上相同的颜色
2.序列中相邻位置括号如果为不同对，则要颜色不同
我们将每一对匹配的括号看作一个节点，而相邻的括号可以用边相连，来保证满足条件2，
通过分析，我们可以发现，每个连通分量之间是不会互相影响的，而每个连通分量内部，由于规则2，导致每个连通分量只有2种方案数，因此最终就是连通分量数量个2相乘，即2的连通分量次方，具体用并查集实现
代码如下： 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e15;
const int mod=998244353;
const int N=2e5+5;
int fa[N];
int pq(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void unit(int a,int b){
    int x=find(a),y=find(b);
    if(x==y)return;
    fa[x]=y;
}
void solve(){
    int n;cin>>n;
    int m=n/2;
    for(int i=1;i<=m;i++)fa[i]=i;
    string s;cin>>s;
    stack<int> st;
    vector<int> id(n);
    int idx=1;
    for(int i=0;i<n;i++){
        if(s[i]=='('){
            id[i]=idx++;
            st.push(i);
        }else{
            id[i]=id[st.top()];
            st.pop();
        }
    }
    for(int i=0;i<n-1;i++){
        if(s[i]==s[i+1]){
            unit(id[i],id[i+1]);
        }
    }
    int cnt=0;
    for(int i=1;i<=m;i++){
        if(find(i)==i)cnt++;
    }
    cout<<pq(2,cnt)<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
}