情况

时间：2024年7月30日22:35
ABC

题解

A

题意

密码连续输两个相同的耗时少。给出字符串增加一个字符让密码耗时长。

思路

找两个相同的之间加一下。

代码

me

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
{
    string s;
    cin >> s;
    bool flag = true;
    for (int i = 0;i<s.size()-1 ;i++){
        cout << s[i];
        if(s[i] == s[i+1] && flag){
                flag = false;
                if (s[i] != 'z')
                    cout << (char)(s[i] + 1);
                else cout << 'a';
        }
    }
    cout << s[s.size() - 1];
    if (flag == true)
    {
        if (s[s.size()-1] != 'z')
            cout << (char)(s[s.size()-1] + 1);
        else cout << 'a';
    }
    cout << endl;
}

jiangly

用substr(0,i)，substr(i).还有活用字符串加法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve()
{
    std::string s;
    std::cin >> s;

    for (int i = 1; i < s.size(); i++)
    {
        if (s[i] == s[i - 1])
        {
            std::cout << s.substr(0, i) << (s[i] == 'a' ? 'b' : 'a') << s.substr(i) << "\n";
            return;
        }
    }
    s += s.back() == 'a' ? 'b' : 'a';
    std::cout << s << "\n";
}

B

题意

给出一个有两行，有一个联通区域的矩阵。要求找出只放一个，能变成3个联通区域的格子数量。

思路

每一竖行一种状态：通，上面堵，下面堵。找中间通，左右两边不通且相等的格子。

代码

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
void solve()
{

    int n;
    cin >> n;
    string s1, s2;
    vector<int> state(n);
    cin >> s1 >> s2;

    for (int i = 0; i < n; i++)
    {
        if (s1[i] == '.' && s2[i] == '.')
            state[i] = 0;
        else if (s1[i] == 'x' && s2[i] == '.')
            state[i] = 1;
        else if (s1[i] == '.' && s2[i] == 'x')
            state[i] = 2;
    }
    int ans = 0;
    for (int i = 0; i < n - 2; i++)
    {
        if (state[i] == state[i + 2] && state[i + 1] == 0 && state[i] != 0)
        {
            ans++;
        }
    }
    cout << ans << endl;
}

C

题意

给出匹配括号字符串。
扣掉奇数个数位上的括号情况，怎么填，让每对括号距离和最小。
给出最小值。

思路

贪心填括号，最开始第一个肯定左，后面：有偶数位上的左，下一位就右匹配。
有偶数位上的右，如果未匹配的左括号在2或2以上，下一位也用右。否则下一位重新开始一个左括号。

代码

me

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
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
const int N = 100000;
int calculate_bracket_match_length(const std::string &s)
{
    std::stack<int> stack; // 用于存储左括号的位置
    int match_length = 0;  // 用于存储总匹配长度

    for (int i = 0; i < s.length(); ++i)
    {
        if (s[i] == '(')
        {
            stack.push(i); // 将左括号的位置压入栈
        }
        else if (s[i] == ')' && !stack.empty())
        {
            int left_index = stack.top();   // 获取栈顶的左括号位置
            stack.pop();                    // 弹出左括号的位置
            match_length += i - left_index; // 计算匹配长度并累加
        }
    }

    return match_length;
}
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cntl = 0;
    int cntr = 0;

    // for (int i = 1; i < n;i+=2){
    //     if(s[i]=='('){
    //         cntl++;
    //     }else {
    //         cntr++;
    //     }
    // }
    int tl = 1;
    s[0] = '(';
    for (int i = 1; i <n-1; i += 2)
    {

        if (s[i] == '(')
        {
            s[i + 1] = ')';
        } else {
            if (tl > 1){
                s[i + 1] = ')';
                tl -= 2;
            }
               else {
                   tl--;
                   s[i + 1] = '(';
               }
            
        }
    }
    int ans = calculate_bracket_match_length(s);
    cout << ans << endl;
    // std::cout << s << endl;
}

jiangly

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
void solve()
{
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    int pre = 0;
    i64 ans = 0;
    for (int i = 0; i < n; i += 2)
    {
        if (pre > 0)
        {
            pre--;//有未匹配括号
        }
        else
        {
            pre++; //增加一个左
        }
        ans += pre;
        pre += (s[i + 1] == '(' ? 1 : -1);//后面还是左,否则就匹配。
        ans += pre;
    }
    std::cout << ans << "\n";
}

问题

贪心策略要想好。浪费太多时间。还有模拟之后的字符串太麻烦，题目也没问这个。

D

题意


你会得到一个有根树，由 n 顶点组成。树中的顶点从 1编号到n，根是顶点。值 ai写在第 i个顶点处。
您可以执行以下操作任意次数（可能为零）：选择至少有一个子节点的顶点 v ;将 av 增加;并将 au 减少，所有顶点 u 都在 v 的子树中（除了 v 本身）。但是，在每次操作之后，所有顶点上的值都应该是非负的。

您的任务是使用上述操作计算在根处写入的最大可能值。

思路

【Educational Codeforces Round 168 (Rated for Div. 2)（A ~ E 题讲解）】 https://www.bilibili.com/video/BV1BnvUejEP9/?share_source=copy_web&vd_source=f7a53b8de055733cb21cb53554bc98b7
讲的好，REN也是ON做法

代码

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
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
const int N = 200010;
vector<int> son[N]; // 二维的
int a[N];

void dfs(int u)
{
    if (son[u].size() == 0)
    { // 叶子
        return;
    }
    int z = 1e10;
    for (auto i : son[u])
    {
        dfs(i);
        z = min(z, a[i]); // 子树里结点最小值。
    }
    if (u == 1) // 当前是根节点，不和了
        return;
    if (z < a[u])
    {             // 如最小值小于当前值
        a[u] = z; // 最小值直接附上，减不了了
        return;
    } // 如最小值大于当前值
    a[u] = z + a[u] >> 1; // 除以2下取整尽量让两数相等。
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        son[i].clear();
    }
    int x = 0;
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        son[x].push_back(i);
    }
    dfs(1);
    int ans = 1e10;
    for (auto i : son[1])
    {
        ans = min(a[i], ans); // 子节点最小值
    }
    a[1] += ans;
    cout << a[1] << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();

    /*code by achen_Karma*/
}