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();
}