A. Strong Password
思路：想要最长的时间，那么肯定就是如果存在前后相同的字母的时候，在中间插入一个不同的字符 ，如果不存在前后相同的字符，直接在最后插入一个和原字符串最后一个字符不同的字符
#include <bits/stdc++.h>
using namespace std;
#define int long long int t;
string s; signed main() { cin >> t; while (t--) { cin >> s; if(s.size()==1){if(s =="z")cout<<"za"<<"\n";else{cout<<s+'z'<<"\n";}continue;}bool modified = false; for (int i = 1; i < s.size(); i++) { if (s[i] == s[i - 1]) { char charToInsert; if (s[i - 1] != 'z') { charToInsert = s[i - 1] + 1; } else { charToInsert = 'a'; } s.insert(s.begin() + i, charToInsert); modified = true; break; } } if(modified==false){if(s[s.size()-1]!='z')s+=s[s.size()-1]+1;else if(s[s.size()-1]=='z'){s+='a';}}cout << s << "\n"; } return 0;
}B. Make Three Regions
思路：最开始最多只有一个连通区域，我们只需要判断是否存在
x . x 或者 . . . 这种情况的数据，如果存在，则计数的cnt++，最后输出cnt即可
. . . x . x
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int a[3][200005];
char s;
signed main()
{cin>>t;while(t--){cin>>n;for(int i=1;i<=2;i++){for(int j=1;j<=n;j++){cin>>s;if(s=='.')a[i][j]=1;elsea[i][j]=0;}}int cnt=0;for(int j=1;j<=n-2;j++){if(a[1][j]==0&&a[1][j+1]==1&&a[1][j+2]==0&&a[2][j]==1&&a[2][j+1]==1&&a[2][j+2]==1)cnt++;else if(a[1][j]==1&&a[1][j+1]==1&&a[1][j+2]==1&&a[2][j]==0&&a[2][j+1]==1&&a[2][j+2]==0)cnt++;}cout<<cnt<<"\n";}return 0;} C. Even Positions
思路：贪心问题，我们用cnt来统计出现的左括号的次数，碰到左括号则cnt++，碰到右括号，则cnt--并且计算与上一个左括号的差值，如果碰到" _ "则需要判断cnt的次数，如果是0，则放置左括号，非0就是右括号
那么我们怎么去记录左括号的位置呢，可以用栈或者队列，我这边用的队列，每经历一个左括号，就将左括号的下标pb进队列里面，然后碰到右括号则计算与队尾的差值，并且将队列里的队尾元素弹出
#include<bits/stdc++.h>
using namespace std;
#define int long long signed main() { int t; cin >> t; while (t--) { string s; int n; cin >> n; cin >> s; int sum = 0; int cntl = 0; deque<int> q; for (int i = 0; i < n; i++) { if (s[i] == '_') { if (cntl > 0) { cntl--; sum += i - q.back(); q.pop_back(); } else { cntl++; q.push_back(i); } } else if (s[i] == '(') { cntl++; q.push_back(i); } else if (s[i] == ')') { if (cntl > 0) { cntl--; sum += i - q.back(); q.pop_back(); } } } cout << sum << "\n"; } return 0;
}D. Maximize the Root
思路：有趣的树上dp问题，我们只需要用一个minn来统计顶点v的最大转移值即可
面对每个子树，我们都有两种情况，如果说我这个顶点v的值要是大于子树的值，那么就不要转移了，否则值会更小，如果小于子树u的值，那么就要加起来除以2
#include<bits/stdc++.h>
using namespace std;
#define int long longint t;
int n;
int f[200005];
int v;
vector<int> G[200005];void dfs(int v)
{int minn=0x3f3f3f3f;//表示v的儿子结点的最大转移值 for(int u:G[v]){dfs(u);minn=min(minn,f[u]);}if(minn==0x3f3f3f3f){return ;}if(v==1){f[1]+=minn;return ;}if(f[v]<minn){f[v]=(f[v]+minn)/2;}else{f[v]=minn;}
}signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){cin>>f[i];G[i].clear();}for(int i=2;i<=n;i++){cin>>v;G[v].push_back(i);}dfs(1);cout<<f[1]<<"\n";}return 0;
}
