每日一题~EC168 A+B+C+D

A
题意：
字符串
每一个字符的花费是2，如果ai-1 ==ai ,那么ai 的花费是1.
现在可以插入一个字符，得到最大花费。输出插入字符之后的字符串。
分析：只需要在相同的连续字符中间插入一个不同的字符就可以了。如果没有连续的相同字符，直接在末尾加一个和末尾字符不同的字母。
参考了别人的代码，十分美丽。


void solve()
{string s;cin>>s;for (int i=1;i<s.size();i++){if (s[i]==s[i-1]){cout<<s.substr(0,i)<<(s[i]=='a'?'b':'a')<<s.substr(i)<<"\n";return ;}}s+= s[s.size()-1]=='a'?'b':'a';cout<<s<<"\n";}

B
题意：
两行字符，最多一个联通块。’ . ‘代表联通，‘x’ 代表障碍。问有多少个’ .’ 变成障碍后，可以分出来3个连通块。
当时想复杂了，没有意识到只有两种情况。没有观察力啊

x.x        ...
...        x.x

意识到这两种情况，代码就是很好写了。通过和1异或，可以改变行。代码又美丽了~

void solve()
{int m;cin>>m;string s[2];cin>>s[0]>>s[1];int ans=0;for (int i=0;i<2;i++){for (int j=1;j<m-1;j++){if (s[i][j]=='.'&&s[i][j-1]=='.'&&s[i][j+1]=='.'&&s[i^1][j]=='.'&&s[i^1][j-1]=='x'&&s[i^1][j+1]=='x')ans++;}}cout<<ans<<"\n";
}

c
题意：
一个合法括号序列的权值定义为匹配括号的距离和。
有偶数长度的括号序列，但是奇数位置的括号丢失了。你需要找出所有可能的原序列中，权值最小的为多少。
奇妙贪心~~
没有必要用 set，用栈维护就行。当时写麻烦了。

void solve()
{int n;cin>>n;string s;cin>>s;s=' '+s;set<int>se;int ans=0;for (int i=1;i<=n;i++){if (s[i]=='_')se.insert(i);else if (s[i]=='('){ans++;i++;}else  {auto it= se.lower_bound(i);it--;ans+=(i-*it);se.erase(it);}}cout<<ans<<"\n";
}

D
题意：
给定一棵 n 个点的树，根为 1。第 i 个点有一个权值 ai。
你可以多次操作：选择一个点，让其子树所有点（不包括自己）权值减 1，自己权加1。权值不能为负。求最后根节点的最大权值。
分析：一个节点的最大值，取决于他子树权值最小的点。可以由从底到上的dp 来维护这个值。
在这里插入图片描述
至于根节点，直接加上mn的值就可以了。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+5;
vector<int>e[N];
vector<int>a;vector<int>b;
vector<int>fa;
void dfs(int x)
{int mn=1e9+5;for (int y:e[x]){if (y==fa[x])continue;dfs(y);mn=min(mn,b[y]);}// 叶子节点if (mn==1e9+5){b[x]=a[x];return ;}// 根节点if (x==1){a[x]+=mn;return ;}if (a[x]<mn)b[x]=(a[x]+mn)/2;else b[x]=mn;}
void solve()
{int n;cin>>n; a.resize(n+1);fa.resize(n+1);b.resize(n+1);for (int i=1;i<=n;i++){  cin>>a[i];e[i].clear();}int u;for (int i=2;i<=n;i++){cin>>u;e[i].push_back(u);e[u].push_back(i);fa[i]=u;}
dfs(1);
cout<<a[1]<<"\n";}
signed  main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;// t=1;cin>>t;while(t--){solve();}return 0;
}