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();
}
标签:Educational,Rated,int,void,mn,7.30,dfs,&&,sum
From: https://blog.csdn.net/jia_jia_LL/article/details/140854898