Educational Codeforces Round 168 (Rated for Div. 2)A——D题解
A. Strong Password
题意：给一个小写字符串密码，添加一个小写字母，使得密码更加复杂。
题解：有相同的相邻的字母，再其中间添加不同的字母；如果没有相同的相邻的字母，则最后添加一个字母。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
bool k=0;
string s;
cin>>s;
int l=s.length();
if(l==1)
{
if(s[0]=='a')
{
cout<<"b"<<s;
}
else
{
cout<<'a'<<s;
}
}
else
{
cout<<s[0];
for(int i=1;i<l;i++)
{
if(s[i]!='a'&&s[i]==s[i-1]&&!k)
{
cout<<'a';
k=1;
}
else
{
if(s[i]==s[i-1]&&!k)
{
cout<<'b';
k=1;
}
}
cout<<s[i];
}
if(!k){
if(s[l-1]!='a'){
cout<<"a";
}
else{
cout<<"b";
}
}
}
cout<<endl;
}
return 0;
}
B. Make Three Regions
题意：给一个
2
∗
n
2*n
2∗n的区域，求让多少空闲区域变成障碍物可以将这个
2
∗
n
2*n
2∗n的区域分成三个不连通的区域。
题解：
x.x . . .
. . . x.x
只有这两种情况合法。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,cnt=0;
string s[2];
cin>>n;
cin>>s[0]>>s[1];
for(int i=1;i<n-1;i++){
if(s[0][i]=='.'&&s[0][i-1]=='.'&&s[0][i+1]=='.'&&s[1][i]=='.'&&s[1][i+1]=='x'&&s[1][i-1]=='x')
{
cnt++;
}
if(s[1][i]=='.'&&s[1][i-1]=='.'&&s[1][i+1]=='.'&&s[0][i]=='.'&&s[0][i+1]=='x'&&s[0][i-1]=='x')
{
cnt++;
}
}
cout<<cnt<<endl;
}
return 0;
}
C. Even Positions
题解：填充括号，所有奇数位置的括号消失，需要填充括号，使得这些括号匹配且权值最小（相匹配括号的距离）。
题解：尽量先满足左括号，再满足右括号。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,sl=0,cnt=0;
string s;
cin>>n;
cin>>s;
for(int i=1;i<n;i+=2)
{
if(s[i]=='(')
{
cnt++;
}
if(s[i]==')')
{
cnt += i-sl;
sl=i+1;
}
}
cout<<cnt<<endl;
}
return 0;
}
D. Maximize the Root
题意：给一个 n n n个节点的树，第 i i i个节点的权值为 a i a_{i} ai，每次可以选取一个子树，使其所有除根节点之外的点减一，根节点加一，问最后的所有根节点的权值最大是几。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N = 200200;
const int INF = 0x3f3f3f3f;
int n,m,idx,h[N],a[N],mi[N];
int e[N],en[N];
void init()
{
idx = 0;
memset(h,-1,sizeof(h));
memset(mi,0x3f,sizeof(mi));
}
void add(int aa,int b)
{
e[idx] = b;
en[idx] = h[aa];
h[aa] = idx++;
}
int dfs(int u)
{
int minn = INF,maxn= -1;
//for(int i=1;i<=u;i++)//while
for(int i = h[u] ; i != -1 ; i = en[i])
{
int v = e[i];
int tmp = dfs(v);
maxn = max(maxn,tmp);
minn = min(minn,tmp);
}
//if(mie == INF)mie = 0;
if(u == 1)
{
return a[u] + minn;
}
if(minn == INF)
{
return a[u];
}
if(minn == 0)
{
return 0;
}
int mid = minn ;
if(a[u] < mid)
return (mid + a[u]) / 2;
else
return mid;
}
int solve()
{
init();
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=2;i<=n;i++)
{
int u;
cin>>u;
add(u,i);
}
int res = dfs(1);
cout<<res<<endl;
}
signed main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}