比赛链接:https://codeforces.com/contest/1997
solve:ABCD
开头:
终于能上青名了,本来以为还得打个两三场,看来这暑假必须上蓝名了,不过这一场说实话感觉运气成分大一点,先稳住青名,最近感觉有点懒惰了,欠了好几场补题,牛客多校还有好多场qwq,得努力了
A. Strong Password
思路:
签到题,只要有两个相同的字母挨在一起,就把他们分开,如果没有就把在结尾添加,这里代码写复杂了.
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
std::string s;
std::cin>>s;
std::string t="";
t+=s[0];
int u=0;
for(int i=1;i<s.size();i++){
if(s[i]==s[i-1]&&u==0){
for(int j='a';j<='z';j++){
if(j!=s[i]){
t+=j;
break;
}
}
u=1;
}
t+=s[i];
}
if(u==0){
for(int j='a';j<='z';j++){
if(j!=s[s.size()-1]){
t+=j;
break;
}
}
}
std::cout<<t<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
int tt;
std::cin>>tt;
while(tt--){
solve();
}
}
B. Make Three Regions
思路:
这个题的题意确实不好懂,我换了好几个翻译才搞懂,其实就是找到有几个点堵上可以使连通块变成3个,开始的时候最多有一个连通块,看样例就能看出只有下面这种结构才能分成三个,然后找就可以了
... x.x
x.x ...
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
int n;
std::cin>>n;
std::vector<std::string> a(2);
for(int i=0;i<2;i++){
std::cin>>a[i];
}
int t=-1;
int res=0;
for(int i=0;i<n;i++){
if(a[0][i]=='x'){
if(t==-1){
t=i;
}
else{
if(i-t==2){
int u=(i+t)/2;
if(a[1][u-1]=='.'&&a[1][u+1]=='.'){
res++;
}
}
t=i;
}
}
}
for(int i=0;i<n;i++){
if(a[1][i]=='x'){
if(t==-1){
t=i;
}
else{
if(i-t==2){
int u=(i+t)/2;
if(a[0][u-1]=='.'&&a[0][u+1]=='.'){
res++;
}
}
t=i;
}
}
}
std::cout<<res<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
int tt;
std::cin>>tt;
while(tt--){
solve();
}
}
C. Even Positions
思路:
这道题我有点猜,因为想要最小,那当遇到)时前面是可以是(,这样就+1,然后就是遇到(时,我观察了一下样例,然后自己还构造了一下,发现遇见(就+3.
还有更好的解法详解https://www.cnblogs.com/zsc985246/p/18333684这位大佬的
证明过程有点乱可以忽略
证明的话,可能有点不太严谨,如有不对的地方还望指出,首先"("和")"的数量一定分别有n/2个,然后这个字符串的结尾一定是),所以显示的位置最多有n/2-1个"(",然后我们对一个字符串进行操作,例如字符串是
_(_(_)
)()(()
| |
step1:)((())
| |
step2:(()())
我们把每个括号前边改成他的反括号,这时我们发现这并不符合标准,我们就得交换括号,我们知道最后一个括号一定是),所以他的前面一定是(,我们想要(能闭合,他的后面必须有),而)却在(前面一格,所以我们进行交换,要想结果尽可能小,我们从倒序进行操作,同时让每个操作移动距离尽可能小,我们交换图上那两个位置的括号,请看step1,这样就减少了一个不规范的括号,同时结果增加了3,我们继续操作,请看step2,这样就得出了结果.
我们从末尾开始遇到了不规范的括号就把他与他后面的进行交换,这一交换结果就增加了3,由于交换,我们当前位置往后都使符合规范,所以每次交换都是交换相邻最近的.
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
int n;
std::cin>>n;
std::string s;
std::cin>>s;
int res=0;
for(int i=0;i<n;i++){
if(s[i]=='('){
res+=3;
}
else if(s[i]==')'){
res++;
}
}
std::cout<<res<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
int tt;
std::cin>>tt;
while(tt--){
solve();
}
}
D. Maximize the Root
思路:
第一眼看到是树我是绝望的,树的题我就没做过几道,然后就抱着试试的心态做了做,在wa了两发后没想到就成了
这个题要想根节点最大,我们就得求下面所有的子树能减去的最大值是多少,由于根节点的子树之间没有联系,所以我们就是求根节点的每个子树所能减去的值中的最小,这样才能保证不会小于0,然后我们就看每个子树,这里就得求每个子树它最多能让他的值减去多少,让他减去多少,他下面每个节点也得减去多少,所以我就得让子树变得平均一些,这里的平均不是简单的平均,我们不能让子节点出现负值,那么我们就得看子树的每个节点,从下往上看,因为最底层的值只能减小不能增加,如果子叶节点大于他的父节点,那么他就可以把他的值传给他的父节点一些,传多少呢,两个数加起来除2向下取整,因为它后面还得减,如果传多了,子叶节点就会小于0,如果子叶节点值小于父节点的值,父节点就只能减去子节点的值,所以父节点就变为了子节点的值,那么如果他的父节点还有其他子节点呢,这时我们就得取最小,就是求父节点的每个子节点中的最小值,然后与父节点进行操作,这样操作后我们就可把这一小部分看作为一个整体,然后继续往上求,直到根节点.
语言能力不太强,解释的不好,如果还有不懂得可以看看https://www.cnblogs.com/zsc985246/p/18333684,还是那位大佬的,方法和我的差不多.
代码:
#include<bits/stdc++.h>
using i64=long long;
i64 fun(i64 x,std::vector<std::vector<i64>>& h,std::vector<i64>& a){
if(h[x].size()==0){
return a[x];
}
i64 k=0x3f3f3f3f3f3f3f3f;
for(i64 i=0;i<h[x].size();i++){
k=std::min(k,fun(h[x][i],h,a));
}
if(x==1){
return a[x]+k;
}
else{
if(k>a[x]){
return (a[x]+k)/2;
}
else{
return k;
}
}
}
void solve(){
i64 n;
std::cin>>n;
std::vector<i64> a(n+1),p(n+1);
std::vector<std::vector<i64>> h(n+1);
i64 t=0x3f3f3f3f3f3f3f3f;
for(i64 i=1;i<=n;i++){
std::cin>>a[i];
if(i>1){
t=std::min(t,a[i]);
}
}
a[1]+=t;
for(i64 i=2;i<=n;i++){
a[i]-=t;
}
for(i64 i=2;i<=n;i++){
std::cin>>p[i];
h[p[i]].push_back(i);
}
std::cout<<fun(1,h,a)<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
int tt;
std::cin>>tt;
while(tt--){
solve();
}
}