Educational Codeforces Round 168 (Rated for Div. 2)

A. Strong Password

题意

给你一个只含有小写字母的字符串S， 它的价值为：

  • 第一个字母的价值为2。
  • 之后每个字母，如果和上一个字母相同，价值为1，否则价值为2。

你现在需要向S中插入一个任意字符，使得插入后的字符的代价尽可能大。输出插入字符后的字符串。

思路

如果存在两个相邻相同字母， 那么我们就在他们中间插入一个不同的字母，会使得总的代价加三。

如果上述条件不成立， 我们就在最后一个字符的后面加上一个不同的字母，使得总的代价加二。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    string str;
    cin>>str;
    rep(i,1,str.size()-1){
        if(str[i] ==str[i-1]){
            char ch = 'b';
            if(str[i] == 'b') ch = 'a';
            rep(j,0,i-1) cout<<str[j];
            cout<<ch;
            rep(j,i,str.size()-1) cout<<str[j];
            puts("");
            return ;  
        }
    }
    cout<<str;
    if(str.back() == 'a') cout<<'b';
    else cout<<'a';
    cout<<endl;
    return ;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B. Make Three Regions

题意

有一个2行n列的表格， 其中一些部分被涂为黑色，剩余白色部分是连通的。

img

img

如上图中将第一行第三列的格子染为黑色后 ，白色连通块被分为了三部分（红色、绿色、蓝色区域）

问有多少个白色格子满足：如果将该白色格子填为黑色，那么剩下的白色格子会组成三个连通块。

思路

当且仅当 “某一行的白块的两边都是黑块，并且在另一行对应位置为连续三个白块”时，会满足条件。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    a = '.' + a + '.';
    b = '.' + b + '.';
    int ans = 0;
    rep(i,1,n){
        if(a[i] == '.' && a[i-1] == 'x' && a[i+1]=='x' && b[i] == '.' && b[i-1] == '.' && b[i+1] == '.'){
            ans ++;
        }
        if(b[i] == '.' && b[i-1] == 'x' && b[i+1]=='x' && a[i] == '.'  && a[i-1] == '.' && a[i+1] == '.'){
            ans ++;
        }
    }
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C. Even Positions

题意

给你一个字符串，只包含( , ) ,_ 三种字符，请你将_ 都填为(或)， 使得字符串为“正则括号序列”（即互相匹配的括号对）

定义一个“正则括号序列”的代价为，所有互相匹配的括号对的距离的总和。如(())()之中， (__)__ 代价为$4-1 = 3$，_()___ 和____() 的代价均为1， 总字符串的代价为3+1+1 = 5

你需要使得构造的正则括号序列的代价尽可能小，输出可能的最小代价。

保证在字符串的长度为偶数，并且在奇数位为(或) ， 在偶数位均为 _ 。

思路

按照正常方法（即栈的方法）进行括号匹配，在遇到_ 时，我们考虑，如果前面还有没有配对的左括号，那么我们应该在此处填写右括号，使它尽早配对，尽可能减少产生的代价。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n;cin>>n;
    string str;
    cin>>str;
    stack<int> st;
    st.push(0);
    int ans = 0;
    for(int i = 1;i<str.size();i++){
        if(str[i] == '_'){
            if(st.size() == 0) {
                st.push(i);
                continue;
            }else{
                ans += i - st.top();
                st.pop();
            }
        }else if(str[i] == '('){
            st.push(i);
        }else{
            ans += i - st.top();
            st.pop();
        }
    }
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D. Maximize the Root

题意

给你一棵树，每个节点都有一个初始值，然后你需要进行任意次如下操作：

  1. 选择一个非叶子节点$u$（并且保证该节点的所有子孙节点的值都大于0）
  2. 将节点$u$的所有子孙节点（即以该节点为子树的所有非根节点）的值减去1
  3. 令节点$u$ 的值加一

问在你进行一定次数操作后，根节点的值最大为多少

思路

考虑树形DP，我们对一个节点操作时，只关心在子孙节点中的最小值是多少。那么设$dp[i]$ 表示在进行一定次数操作后，以$i$ 号节点为根的子树，最小值最大是多少。

如果一个节点是叶子节点，由于无法进行任何操作，那么他的权值是自己的值本身。

对于一个非叶子节点$u$，我们对他的所有子节点$v_1,v_2,…,v_k$的dp值取min，得到以$u$为根的所有子孙节点的最小值$t_u$ (不包括$u$) , 于是我们考虑最大化$min(t_u,a_u)$，我们将$t_u$和$u$本身的权值$a_u$进行比较 ， 如果 $t_u <= a_u$ 那么对u进行操作只会使得最小值$min(t_u,a_u)$变得更小， 相反如果$t_u > a_u$ 那么我们便可以进行$\frac{t_u - a_u}{2}$ 次操作，来最大化$min(t_u,a_u)$ 。

总的dp传递式为$dp[u] = MAX(tu,\frac{t_u+a[u]}{2}) ,其中t_u = MIN{v \in son(u)}dp[v]$

于是我们进行搜索，并维护dp数组， 最终得到了每一个节点的以该节点为根的子树中，所有节点的最小值的最大情况 ， 我们只关心根节点的孩子节点（即高度为1的节点）的dp值， 对他们取min后，即为最终能在根节点进行的操作数， 于是最终的答案为$a[root] + MIN_{v \in son(root)} dp[v]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int a[200005];
vector<int> sons[200005];
void dfs(int x){
    int mn = INF;
    if(sons[x].empty()) return ;
    for(auto v : sons[x]){
        dfs(v);
        mn = min(mn,a[v]);
    }
    if(a[x] > mn){
        a[x] = mn;
        return ;
    }
    int ope = (mn - a[x])/2;
    a[x] += ope;
    return ;
}
void solve(){
    int n;
    cin>>n;
    rep(i,1,n){
        a[i] = 0;sons[i].clear();
    }
    rep(i,1,n) cin>>a[i];
    rep(i,2,n){
        int fa;cin>>fa;
        sons[fa].push_back(i);
    }
    for(auto v : sons[1]){
        dfs(v);
    }
    int mn = INF;
    for(auto v : sons[1]){
        mn = min(mn,a[v]);
    }
    cout<<a[1]+mn<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}