Educational Codeforces Round 168 (Rated for Div. 2)-7.30复盘

A. Strong Password

简单题，找到相同的两个相邻字母之间插一个跟他们不同的大写字母即可

inline void solve(){cin>>s;int id=0;char hh=' ';for(int i=1;i<s.size();i++){if(s[i-1]==s[i]){id=i;break;}} for(int i=0;i<26;i++){if(s[id]!='a'+i&&s[id+1]!='a'+i) hh='a'+i;}for(int i=0;i<s.size();i++){if(id==i) cout<<hh;cout<<s[i];}cout<<endl;
}

B. Make Three Regions

观察给的样例，只有两个箱子夹着，并且上一行或下一行往右或者往左没有箱子，那这个位置就是答案所在的位置，统计这种类型位置的数目即可

inline void solve(){cin>>n;int sum=0;for(int i=0;i<2;i++){for(int j=0;j<n;j++) cin>>g[i][j];}for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(j+2>=n) continue;if(g[i][j]=='x'&&g[i][j+1]=='.'&&g[i][j+2]=='x'){if(i==0&&g[i+1][j+2]=='.'&&g[i+1][j]=='.') sum++;else if(i==1&&g[i-1][j+2]=='.'&&g[i-1][j]=='.') sum++;}}}cout<<sum<<endl;
}

C. Even Positions

刚开始看以为是那种很恶心的括号的dp，没想到画了几个样例，发现贪心能做，每次枚举偶数位置，看是什么类型的括号，左括号就往右边找，右括号就往左边找，找最近且没被使用过的的位置即可

inline void solve(){cin>>n;int sum=0;for(int i=1;i<=n;i++) cin>>g[i];for(int i=1;i<=n;i++){i++;if(g[i]=='('){for(int j=1;j<=n-i;j++){if(j!=1) j++;if(!st[i+j]){st[i+j]=1;sum+=j;break;}}}else{for(int j=1;j<=i;j++){if(j!=1) j++;if(!st[i-j]){st[i-j]=1;sum+=j;break;}}}}cout<<sum<<endl;for(int i=1;i<=n;i++) st[i]=0;
}

D. Maximize the Root

用dfs搜索找出每个分支的最小值，最小值如果大于该分支定点的值，就更新该顶点的值为该顶点的值加上最小值的和除以2，否则用最小值更新该分支定点的值

ll dfs(ll x){if(!e[x].size()){if(x==1)  ans=a[x];return a[x];}ll mn=1e9+1;for(auto u:e[x]){mn=min(mn,dfs(u));}if(x==1) ans=a[x]+mn;if(a[x]>=mn) return mn;return (a[x]+mn)/2;
}void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=2;i<=n;i++){cin>>h;e[h].push_back(i);}ans=0;dfs(1);cout<<ans<<endl;for(int i=1;i<=n;i++) e[i].clear();
}