A - Hell, World!#

不输出第 $X$ 位字符即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8

9
void solved() {
10
    int x;
11
    cin >> x;
12
    string s = "HelloWorld";
13
    for(int i = 0; i < (int)s.size(); i++){
14
        if(i != x - 1){
15
            cout << s[i];
16
        }
17
    }
18
}
19

20
int main() {
21
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
22
    int _ = 1;
23
    while(_--){
24
        solved();
25
    }
26
    return 0;
27
}

B - 459#

直接循环判断然后拼接对应的数字即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8

9
void solved() {
10
    int n;
11
    cin >> n;
12
    vector<string> s(n);
13
    for(auto& it : s){
14
        cin >> it;
15
    }
16
    string t = "";
17
    for(auto it : s){
18
        if(it[0] == 'a' || it[0] == 'b' || it[0] == 'c'){
19
            t += "2";
20
        }
21
        if(it[0] == 'd' || it[0] == 'e' || it[0] == 'f'){
22
            t += "3";
23
        }
24
        if(it[0] == 'g' || it[0] == 'h' || it[0] == 'i'){
25
            t += "4";
26
        }
27
        if(it[0] == 'j' || it[0] == 'k' || it[0] == 'l'){
28
            t += "5";
29
        }
30
        if(it[0] == 'm' || it[0] == 'n' || it[0] == 'o'){
31
            t += "6";
32
        }
33
        if(it[0] == 'p' || it[0] == 'q' || it[0] == 'r' || it[0] == 's'){
34
            t += "7";
35
        }
36
        if(it[0] == 't' || it[0] == 'u' || it[0] == 'v'){
37
            t += "8";
38
        }
39
        if(it[0] == 'w' || it[0] == 'x' || it[0] == 'y' || it[0] == 'z'){
40
            t += "9";
41
        }
42
    }
43
    cout << t << endl;
44
}
45

46
int main() {
47
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
48
    int _ = 1;
49
    while(_--){
50
        solved();
51
    }
52
    return 0;
53
}

C - Drop Blocks#

这题不能直接模拟，我们需要一步一步对遍历的步骤进行优化。
这里我们开个数组 $a$ 表示 $n$ 个格子。然后看到操作 $2$ 是输出至少有多少个格子有对应数量的积木，那我们就再开一个数组 $b[y]$ 记录满足对应至少满足这么多积木数量 $y$ 的格子的数量，然后在每次进行 $1$ 操作时对对应的 $a[y]$ (积木数量)加 $1$ 。(这样的 $b$ 数组里面存的是达到过这个积木数量的格子数量，也就是大于等于这个积木数量的格子数量，满足题目的”至少”的要求)而对于操作 $1$ 提到的所有格子都有的数量就会拿走，我们肯定不能遍历去减。这里的方法是用 $mi$ 记录下 $b[y] = n$ 对应的积木数量 $y$ (也就是所有格子都有的积木数量 $y$ )，然后在 $2$ 操作查询时输出 $b[y + mi]$ (也就是减去 $y$ 之后 $2$ 操作查询时需要满足的积木数量 $y + mi$ )即可。
$tips：$ 这里的 $y + mi$ 会超过 $3 \times 10^5$ ，我们要把数组开大一点。或者加个条件判断 $y + mi > q$ 就输出 $0$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8

9
int a[500010];
10
int b[500010];
11
int mi = 0;
12

13
void solved() {
14
    int n, q;
15
    cin >> n >> q;
16
    while(q--){
17
        int x, y;
18
        cin >> x >> y;
19
        if(x == 1){
20
            a[y]++; b[a[y]]++;
21
            if(b[a[y]] == n) mi = a[y];
22
        }
23
        else{
24
            cout << b[y + mi] << endl;
25
        }
26
    }
27
}
28

29
int main() {
30
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
31
    int _ = 1;
32
    while(_--){
33
        solved();
34
    }
35
    return 0;
36
}

D - Adjacent Distinct String#

我们先记录字符串中每个字符出现的频率。然后我们可以发现，我们将出现频率最大的字符(它的出现次数我记为 $ma$ )与其他字符通过间隔构造，使得构造的字符串能满足题目条件的一个关键条件是： $ma$ - $other$ (其他字符出现的总次数) > $1$ 。所以只要满足这个条件我们就 $yes$ ，否则就 $no$ 。如果 $yes$ 我们就通过构造输出其中满足条件的一个字符串。我这里的构造是每次都找到非末尾元素的出现次数最多的字符拼接到 $t$ 末尾，然后输出 $t$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8

9
map<char, int> mp;
10

11
void solved() {
12
    int t;
13
    cin >> t;
14
    while(t--){
15
        mp.clear();
16
        int ma = 0;
17
        string s; cin >> s;
18
        for(auto it : s) mp[it]++;
19
        for(auto it : mp){
20
            if(it.second > ma) ma = it.second;
21
        }
22
        int other = (int)s.size() - ma;
23
        if(ma - other > 1) cout << "No" << endl;
24
        else{
25
            cout << "Yes" << endl;
26
            string t = "";
27
            int cnt = (int)s.size();
28
            while(cnt--){
29
                int max_ = 0; char c ='0';
30
                for(auto it : mp){
31
                    if(it.second > max_ &&(t.empty() || it.first != t.back())){
32
                        max_ = it.second;
33
                        c = it.first;
34
                    }
35
                }
36
                t += c; mp[c]--;
37
            }
38
            cout << t << endl;
39
        }
40
    }
41
}
42

43
int main() {
44
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
45
    int _ = 1;
46
    while(_--){
47
        solved();
48
    }
49
    return 0;
50
}

E - Select from Subtrees#

这题没有想象中那么难，思路比较清晰。
我们的思路是从叶子节点不断向父节点遍历。我们可以这样思考，如果先让 $i$ 较小的松鼠在父节点取了一部分糖果，它取的糖果就可能是子树的任何部分，那我们在计算该父节点的子树取的糖果就会非常混乱。反之，如果我们先让对应的叶子节点的松鼠在叶子节点取，然后如果有取剩的就传递给父节点，这样倒序遍历的话，我们就可以保证每次父节点的子树都是被取过的。而对于每一个子树部分，松鼠可以随意取子树任何分支的糖果，这里其实就是一个组合数的问题，对于每一个松鼠取法就是 $C_{sum}^{d[x]}$ 种。（ $d[x]$ 是对应的松鼠 $x$ 需要的糖果数量， $sum$ 是当前整个子树中可供取的糖果数量）我们从叶子节点不断向上遍历，并在每一次节点计算该子树所有组合的总数然后加入 $ans$ 最终就可以得到结果。
$tips：$ 这里每次计算组合数时的除法取模运算要注意需要通过提前预处理逆元来快速进行模运算除法。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8

9
int n;
10
ll a[200010];
11
ll d[200010];
12
ll ans = 1;
13
vector<vector<int>> child;
14
vector<ll> inv;
15

16
ll dfs(int x, vector<ll>& inv){
17
    ll sum = a[x];
18
    for (int v : child[x]){
19
        sum += dfs(v, inv);
20
    }
21
    if(sum < d[x]) ans = 0;
22
    else {
23
        // 计算组合数C(d[k], sum)
24
        for (int i = 0; i < d[x];i++){
25
            ll num = (sum - i) % mod;
26
            if (num < 0) num += mod;
27
            ans = ans * num % mod;
28
            ans = ans * inv[i + 1] % mod;  //除法模运算：除以(i + 1)取模等价于乘逆元
29
        }
30
    }
31
    return sum - d[x];  //将未使用的糖果传递给父节点
32
}
33

34
void solved() {
35
    cin >> n;
36
    child.resize(n + 1);
37
    for(int i = 2; i <= n;i++){
38
        int x;
39
        cin >> x;
40
        child[x].push_back(i);
41
    }
42

43
    int maxd = 0;  //找出需要处理的最大逆元
44
    for (int i = 1; i <= n;i++) cin >> a[i];
45
    for (int i = 1; i <= n;i++){
46
        cin >> d[i];
47
        if(d[i] > maxd) maxd = d[i];
48
    }
49

50
    //线性预处理逆元，用于快速进行模除法
51
    inv.resize(maxd + 2);
52
    inv[1] = 1;
53
    for (int i = 2; i <= maxd;i++){
54
        inv[i] = mod - mod / i * inv[mod % i] % mod;
55
    }
56
    //从根节点开始
57
    dfs(1, inv);
58

59
    cout << ans % mod << endl;
60
}
61

62
int main() {
63
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
64
    int _ = 1;
65
    // cin >> _;
66
    while(_--){
67
        solved();
68
    }
69
    return 0;
70
}