https://codeforces.com/contest/1997

A

如果存在相同连续字符，则插入不同字符破坏，否则在末尾插入与末尾不相同的即可。

# include <bits/stdc++.h>
using namespace std;
# define int long long 
signed main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int k=-1;
for(int i=0;i<s.size()-1;i++)
{
if(s[i]==s[i+1])
{
k=i;
break;
}
}
for(int i=0;i<s.size();i++)
{
  cout<<s[i];
  if(i==k)
  {
    if(char(s[i]+1)>'z')
    cout<<'a';
    else cout<<char(s[i]+1);
  }  
}
if(k==-1)
{
    if(char(s[s.size()-1]+1)>'z')
    cout<<'a';
    else cout<<char(s[s.size()-1]+1);
}
cout<<endl;
}


}

B
根据样例特判即可

# include <bits/stdc++.h>
using namespace std;
# define int long long 
const int N=2e5+10;
signed main()
{
int T;
    cin>>T;
    while(T--)
    {
    int m;
    cin>>m;
    char a[3][N]={0};
    for(int i=1;i<=2;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    int sum=0;
    for(int i=1;i<=m-2;i++)
    {
    if(a[1][i]=='x'&&a[1][i+2]=='x'&&a[1][i+1]=='.'&&a[2][i]=='.'&&a[2][i+2]=='.'&&a[2][i+1]=='.')
    {
    sum++;
    }
    }
    for(int i=1;i<=m-2;i++)
    {
    if(a[2][i]=='x'&&a[2][i+2]=='x'&&a[2][i+1]=='.'&&a[1][i]=='.'&&a[1][i+2]=='.'&&a[1][i+1]=='.')
    {
    sum++;
    }
    }
    cout<<sum;
    cout<<endl;
    }
    return 0;
}

C
贪心的考虑我们需要让不同括号尽可能的近 需要动态的插入统计括号
用栈维护相邻括号距离

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
    int n;
    string s;
    cin >> n >> s;

    int no = 0;
    for (int i = 0; i < n; i ++) {
        if (i % 2 == 0) {
            if (!no) s[i] = '(', no ++;
            else s[i] = ')', no --;
        } else {
            if (s[i] == '(') no ++;
            else no --;
        }
    }
    stack<int> stk;
    int res = 0;
    for (int i = 0; i < n; i ++)
        if (s[i] == '(') stk.push(i);
        else res += i - stk.top(), stk.pop();
    cout << res << endl;
}

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

    int dt;

    cin >> dt;

    while (dt --)
        solve();

    return 0;
}

D
根最大值即为子图点最小值 答案二分考虑一种线性方法。我们要让每个点的值尽可能的相等且较大，对于每个点如果他比他子结点权值最小值都要大，那么他的最大值为应该为他子树上的最小值与他本身全值得一半；如果他得值要比他的子节点权值最小值还要小，那么不需要不变化。树上dfs即可

# include <bits/stdc++.h>
using namespace std;
# define int long long 
int n;
const int N=2e5+10;
int a[N],val[N];
vector<int>e[N];
int mn=1e18;
void dfs(int u)
{
    val[u]=a[u];
    int mn=1e18;
    for(int j:e[u])
    {
    dfs(j);
    mn=min(mn,val[j]);
    }
    if(mn!=1e18)
    {
    if(val[u]<=mn)
    val[u]=mn+val[u]>>1;
    else val[u]=mn;
    }
}
signed main()
{
int T;
cin>>T;
while(T--)
{
mn=1e18;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=2;i<=n;i++)
{
int x;
cin>>x;
e[x].push_back(i);
}
dfs(1);
int res=1e18;
for(auto x:e[1])
res=min(res,val[x]);
cout<<a[1]+res;
cout<<endl;
for(int i=1;i<=n;i++)
e[i].clear(),val[i]=0;
}
}