NOTE
比赛链接：牛客周赛 Round 144

A - 我是谁？#

关键词：签到

思路#

统计四个字母出现次数，判断是否一致即可。

Code#

1
// Problem: 我是谁？
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134957/A
4
// Time: 2026-05-17 19:00:06
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
int a, b, cc, d;
27

28
void solve()
29
{
30
    int n;
31
    string s;
32
    cin >> n >> s;
33

34
    for (auto c: s)
35
    {
36
        if (c == 'A')
37
            a++;
38
        else if (c == 'B')
39
            b++;
40
        else if (c == 'C')
41
            cc++;
42
        else
43
            d++;
44
    }
45

46
    int ave = (a + b + cc + d) / 4;
47
    if (a == ave && b == ave && cc == ave && d == ave)
48
        cout << "Yes" << endl;
49
    else
50
        cout << "No" << endl;
51
}
52

53
int main()
54
{
55
    fastio();
56

57
    int T = 1;
58
    // cin >> T;
59

60
    while (T--)
61
        solve();
62

63
    return 0;
64
}

B - 我是清楚姐姐#

关键词：构造

思路#

显然只有 $1, 2, 3$ 可以构造出来合法的矩阵。

Code#

1
// Problem: 我是清楚姐姐
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134957/B
4
// Time: 2026-05-17 19:03:22
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    if (n == 2)
32
    {
33
        cout << 1 << " " << 2 << endl;
34
        cout << 3 << " " << 4 << endl;
35
        return;
36
    }
37

38
    if (n == 1)
39
    {
40
        cout << 1 << endl;
41
        return;
42
    }
43

44
    if (n == 3)
45
    {
46
        cout << 1 << " " << 2 << " " << 3 << endl;
47
        cout << 5 << " " << 4 << " " << 6 << endl;
48
        cout << 7 << " " << 8 << " " << 9 << endl;
49
        return;
50
    }
51

52
    cout << -1 << endl;
53
}
54

55
int main()
56
{
57
    fastio();
58

59
    int T = 1;
60
    // cin >> T;
61

62
    while (T--)
63
        solve();
64

65
    return 0;
66
}

C - 其实我是小苯#

关键词：构造

思路#

由于给定长度过大，我们考虑直接构造字符串。

当 $n = m$ 时（两数长度相同）

最小值：因为长度相同，我们完全可以让 $a = b$ ，这样 $|a - b|$ 的最小值为 0。
最大值：我们要让其中一个数尽可能大，另一个尽可能小。
- 最大数是 $n$ 个 9：99...99
- 最小数是 1 后面跟 $n-1$ 个 0：10...00
- 两者相减： $99\dots9 - 10\dots0 = \mathbf{89\dots9}$ （即 1 个 8 后面跟着 $n-1$ 个 9）。

当 $n > m$ 时（两数长度不同）

此时必然有 $a > b$ ，所以 $|a - b| = a - b$ 。

最小值：我们要让 $a$ $a$ 尽可能小， $b$ $b$ 尽可能大。
- 最小的 $a = 10^{n-1}$ （1 后面 $n-1$ 个 0）
- 最大的 $b = 10^m - 1$ （ $m$ 个 9）
- 两者相减： $10^{n-1} - 10^m + 1$ 。
- 如何化为字符串？
  - 如果 $n = m + 1$ （例如 $n=3, m=2$ ）， $100 - 99 = \mathbf{1}$ 。
  - 如果 $n > m + 1$ （例如 $n=5, m=2$ ）， $10000 - 99 = \mathbf{9901}$ 。
  - 规律：连续 $n - m - 1$ 个 9，然后 $m - 1$ 个 0，最后 1。
最大值：我们要让 $a$ $a$ 尽可能大， $b$ $b$ 尽可能小。
- 最大的 $a = 10^n - 1$ （ $n$ 个 9）
- 最小的 $b = 10^{m-1}$ （1 后面 $m-1$ 个 0）
- 两者相减： $10^n - 10^{m-1} - 1$ 。
- 例如 $n=4, m=2$ 时： $9999 - 10 = \mathbf{9989}$ 。
- 规律： $n - m$ 个 9，然后 1 个 8，最后 $m - 1$ 个 9。

Code#

1
// Problem: 其实我是小苯
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134957/C
4
// Time: 2026-05-17 19:09:59
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n, m;
29
    cin >> n >> m;
30

31
    if (n > m)
32
        swap(n, m);
33

34
    string mn = "";
35

36
    if (n == m)
37
        mn = "0";
38
    else if (m == n + 1)
39
        mn = "1";
40
    else
41
        mn = string(m - n - 1, '9') + string(n - 1, '0') + "1";
42

43
    string mx = string(m - n, '9') + "8" + string(n - 1, '9');
44

45
    cout << mn << " " << mx << endl;
46
}
47

48
int main()
49
{
50
    fastio();
51

52
    int T = 1;
53
    // cin >> T;
54

55
    while (T--)
56
        solve();
57

58
    return 0;
59
}

D - 骗你的，我是小红#

关键词：位运算，组合数学

思路#

题目要求找满足 $i \operatorname{xor} j$ 是 $k$ 的倍数的数对 $(i, j)$ 。如果一个数 $X$ 是 $k$ 的倍数，意味着在二进制表示下， $X$ 的最低 $p$ 位必须全是 0。

而一个数的最低 $p$ 位，在数学上是这个数对 $2^p$ 取模的余数（也就是对 $k$ 取模的余数）。

TIP
要理解这个概念，可以从十进制来理解。
一个数的最低两位（个位和十位），其实就是这个数除以 $10^2=100$ 的余数。
推广到一般进制，对于一个用基数 $b$ 表示的数 $N$ ，它的最低 $p$ 位，就是 $N$ 除以 $b^p$ 的余数。

原问题就可以转化为：在区间 $[l, r]$ 内，有多少对 $(i, j)$ 满足它们除以 $k$ 的余数相同？

也就是说，我们需要统计区间 $[l, r]$ 内，模 $k$ 余数为 $0, 1, 2, \dots, k-1$ 的数字分别有多少个。假设余数为 $m$ 的数字有 $C_m$ 个，那么从这些数字中任选 2 个组成对的方案数就是 $\frac{C_m \times (C_m - 1)}{2}$ 。把所有余数的方案数加起来就是最终答案。

我们可以用整除分块的思想直接 $O(1)$ 算出来：

区间 $[l, r]$ 的总长度是 $len = r - l + 1$ 。
每连续的 $k$ 个数，必然完美地覆盖了模 $k$ 的所有余数（ $0$ 到 $k-1$ 各出现一次）。
整个区间可以分为 len / k 个完整的块，以及末尾剩下的一小截，长度为 len % k。
这意味着：
- 有 len % k 种余数，它们多出现了一次，总共出现了 len / k + 1 次。
- 剩下的 k - len % k 种余数，出现了 len / k 次。

Code#

1
// Problem: 骗你的，其实我是小红
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134957/D
4
// Time: 2026-05-17 19:24:28
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    ll l, r, k;
29
    cin >> l >> r >> k;
30

31
    ll len = r - l + 1;
32
    ll cnt = len / k;
33
    ll rem = len % k;
34

35
    cout << (k - rem) * (cnt * (cnt - 1) / 2) + rem * (cnt * (cnt + 1) / 2) << endl;
36
}
37

38
int main()
39
{
40
    fastio();
41

42
    int T = 1;
43
    // cin >> T;
44

45
    while (T--)
46
        solve();
47

48
    return 0;
49
}

E - 好吧，我是Bingbong#

关键词：DFS

思路#

注水的过程本质上是一个由管道高度决定的 DFS 顺序，对于同一个瓶子的所有子树，管道位置越低，越先被完全灌满。一个节点 $u$ 的瓶子达到满水时， $u$ 的整棵子树也已经全部注满。

$Ans[i] = \text{sum\_subtree}[i] + \text{dist}[i]$

$\text{sum\_subtree}[i]$ ：表示以 $i$ 为根的整棵子树，全部注满水所需要的总水量。
$\text{dist}[i]$ ：表示为了让水能够刚好流到节点 $i$ 的“入水口”，它的所有祖先节点以及旁支子树所截留的总历史耗水。

对于 dist[i]，可以这样理解：因为水必须填满这个节点的父亲节点，才可能流下来到子节点，因此这些被提前消耗的水对于节点 $i$ 来说就是外部的。

Code#

1
// Problem: 好吧，我是Bingbong
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134957/E
4
// Time: 2026-05-17 20:35:50
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    vector<ll> h(n + 1), f(n + 1), w(n + 1);
32
    for (int i = 1; i <= n; i++)
33
        cin >> h[i];
34

35
    for (int i = 2; i <= n; i++)
36
        cin >> f[i];
37

38
    vector<vector<pll>> g(n + 1);
39

40
    for (int i = 2; i <= n; i++)
41
    {
42
        cin >> w[i];
43
        g[f[i]].push_back({w[i], i}); // 管道高度-子节点编号
44
    }
45

46
    vector<ll> sum(n + 1), pre(n + 1), res(n + 1);
47

48
    // 计算节点u及其整棵子树，如果全部注满水需要多少水量
49
    auto dfs1 = [&](auto &&self, int u) -> void
50
    {
51
        sum[u] = h[u];
52
        for (auto [ht, v]: g[u])
53
        {
54
            self(self, v);
55
            sum[u] += sum[v];
56
        }
57
    };
58

59
    dfs1(dfs1, 1);
60

61
    // 代表水位上升，水一定会先流进位置低的管道
62
    for (int i = 1; i <= n; i++)
63
        sort(all(g[i]));
64

65
    auto dfs2 = [&](auto &&self, int u) -> void
66
    {
67
        res[u] = pre[u] + sum[u];
68

69
        ll cur = 0;
70
        // cur表示当前水位下，所有旁支子树的总容量
71
        for (auto [ht, v]: g[u])
72
        {
73
            // 算 v 的截留代价 = 祖先截留(pre[u]) + 自身高度(ht) + 比它低的旁支容量(cur)
74
            pre[v] = pre[u] + ht + cur;
75

76
            // 算完v以后需要把v的整棵子树容量加入cur，因为对于下一个更高的管子来说，v必须要被填满
77
            cur += sum[v];
78
            self(self, v);
79
        }
80
    };
81

82
    dfs2(dfs2, 1);
83

84
    for (int i = 1; i <= n; i++)
85
        cout << res[i] << " ";
86
}
87

88
int main()
89
{
90
    fastio();
91

92
    int T = 1;
93
    // cin >> T;
94

95
    while (T--)
96
        solve();
97

98
    return 0;
99
}