NOTE
比赛链接：牛客小白月赛 132
赛时四题。

A - 出题需要 rating#

关键词：签到

Code#

1
// Problem: 出题需要 rating
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134527/A
4
// Time: 2026-05-08 19:25:47
5

6
#include <bits/stdc++.h>
7
using namespace std;
8

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

15
using ll = long long;
16
using ull = unsigned long long;
17
using pii = pair<int, int>;
18
using pdd = pair<double, double>;
19
using pll = pair<long long, long long>;
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 m;
29
    cin >> m;
30

31
    int a[7] = {0};
32
    int n = 1000;
33

34
    while (m--)
35
    {
36
        int x;
37
        cin >> x;
38

39
        n += x;
40

41
        if (n <= 699)
42
            a[0]++;
43
        else if (n >= 700 && n <= 1099)
44
            a[1]++;
45
        else if (n >= 1100 && n <= 1499)
46
            a[2]++;
47
        else if (n >= 1500 && n <= 1999)
48
            a[3]++;
49
        else if (n >= 2000 && n <= 2399)
50
            a[4]++;
51
        else if (n >= 2400 && n <= 2799)
52
            a[5]++;
53
        else if (n >= 2800)
54
            a[6]++;
55
    }
56

57
    for (auto i: a)
58
        cout << i << " ";
59
}
60

61
int main()
62
{
63
    fastio();
64

65
    int T = 1;
66
    // cin >> T;
67

68
    while (T--)
69
        solve();
70

71
    return 0;
72
}

B - 出题需要语文#

关键词：模拟

思路#

我们需要维护三个信息：题目编号、题目难度、题目质量，可以使用结构体存储并重载小于号。

但赛时的思维有点混乱，选择了 map<char, vector<pii>>，赛后复盘时发现结构体更好一点。

Code#

1
// Problem: 出题需要语文
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134527/B
4
// Time: 2026-05-08 19:30:56
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

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

25
map<char, vector<pii>> mp;
26

27
bool cmp(pii &A, pii &B)
28
{
29
    return A.second > B.second;
30
}
31

32
void solve()
33
{
34
    int n;
35
    cin >> n;
36

37
    for (int i = 1; i <= n; i++)
38
    {
39
        char c;
40
        int q;
41
        cin >> c >> q;
42

43
        mp[c].push_back({i, q});
44
    }
45

46
    if (mp.size() < 6)
47
    {
48
        cout << -1 << endl;
49
        return;
50
    }
51

52
    vector<pii> res;
53

54
    for (auto &[c, vec]: mp)
55
    {
56
        sort(all(vec), cmp);
57
        res.push_back(vec[0]);
58
    }
59

60
    double ave = 0;
61
    for (auto i: res)
62
    {
63
        ave += i.second;
64
        if (i.second < 60)
65
        {
66
            cout << -1 << endl;
67
            return;
68
        }
69
    }
70

71
    ave = ave * 1.0 / 6;
72
    // cout << ave << endl;
73

74
    if (ave >= 70)
75
        for (auto i: res)
76
            cout << i.first << " ";
77
    else
78
        cout << -1 << endl;
79
}
80

81
int main()
82
{
83
    fastio();
84

85
    int T = 1;
86
    // cin >> T;
87

88
    while (T--)
89
        solve();
90

91
    return 0;
92
}

C - 出题需要加法#

关键词：位运算，二分

思路#

刚开始的时候想到一个思路：使用 bitset 来考察区间 [L, R] 上每个数的二进制表示，只有某个数的二进制表示中 1 的个数 $\le 2$ 才计入答案，但这样做在区间跨度很大的情况下会超时，并且没有特判 0 和 1 的情况。

正确的思路是，我们直接构造出所有符合条件的 w， $x$ 和 $y$ 的取值范围最大只有 $62$ （因为 $2^{62} + 2^{62} = 2^{63}$ ），我们可以使用两层循环嵌套枚举 $x$ 和 $y \in [0, 62]$ ，计算所有可能的 $w$ 。符合条件的数大约只有 2000 个，把这些数去重并排序，对于每一次查询，使用二分查找即可。

NOTE
distance(itl, itr)函数可以计算两个迭代器之间的距离，它支持所有合法迭代器，但不会检查非法性。
这道题注意使用 unsigned long long。

Code#

1
// Problem: 出题需要加法
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134527/C
4
// Time: 2026-05-08 19:43:51
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

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

25
vector<ull> nums;
26

27
void init()
28
{
29
    for (int i = 0; i < 63; i++)
30
        for (int j = 0; j < 63; j++)
31
        {
32
            ull tmp = (1ull << i) + (1ull << j);
33
            nums.push_back(tmp);
34
        }
35

36
    sort(all(nums));
37
    nums.erase(unique(all(nums)), nums.end());
38
}
39

40
void solve()
41
{
42
    ll l, r;
43
    cin >> l >> r;
44

45
    auto itL = lower_bound(all(nums), l);
46
    auto itR = upper_bound(all(nums), r);
47

48
    cout << distance(itL, itR) << endl;
49
}
50

51
int main()
52
{
53
    fastio();
54

55
    int T = 1;
56
    cin >> T;
57

58
    init();
59

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

63
    return 0;
64
}

D - 出题需要构造#

关键词：构造

思路#

NOTE
赛时竟然想出来了这题的思路，感觉自己进步了。下面抛开直觉，更严谨地考虑这个问题。

我们需要在 $n \times m$ 的矩阵中填入 $1 \sim n$ 的颜色，使得任意选出 $k$ 种颜色，矩阵的每一行和每一列都恰好有 2 个格子被点亮。

Step 1：确定 $k$ 的值#

单独看矩阵的某一列（长度为 $n$ ）。假设在这列中，颜色 $i$ 出现了 $c_i$ 次。题目要求：任意选 $k$ 种颜色，这 $k$ 种颜色出现的次数总和必定为 2。

即对于任意大小为 $k$ 的集合 $S$ ，都有 $\sum_{i \in S} c_i = 2$ 。既然对任意组合都成立，这就意味着所有颜色的出现次数必须完全相同。

设每个颜色在这一列出现 $c$ 次，那么就有： $k \times c = 2$ ，因为 $k$ 和 $c$ 都是正整数，满足这个等式的组合只有两种：

$k = 1, c = 2$
$k = 2, c = 1$

我们把这两种情况代入列的总长度（这一列共有 $n$ 个格子）：

如果 $k = 1, c = 2$ ：意味着 $n$ 种颜色，每种颜色在这列出现了 $2$ 次。那么这一列的总格子数应该是 $2n$ 。但这列的长度是 $n$ （ $n = 2n \implies n=0$ ），矛盾
如果 $k = 2, c = 1$ ：意味着每种颜色在这列恰好出现 $1$ 次。那么总格子数是 $n \times 1 = n$ 。完全合理！

结论 1： $k$ 必定等于 $2$ 。且每种颜色在每一列中恰好出现 1 次。

Step 2：确定 $n$ 和 $m$ 的关系#

我们用同样的逻辑去分析某一行（长度为 $m$ ）。

为了满足任意 2 种颜色在这一行恰好点亮 2 个格子，那么每种颜色在这一行中也必须恰好出现 1 次。

既然 $n$ 种颜色每种都在这一行出现 1 次，那么这一行的长度就必须是 $n$ 。

但这一行的长度是 $m$ ，所以： $n = m$

结论 2：如果 $n \neq m$ ，绝对不可能存在合法方案，直接输出 NO。

另外，因为需要选出 $k=2$ 种颜色，所以颜色总数 $n$ 必须 $\geqslant 2$ （如果 $n=1$ 也是 NO）。

Step3：构造方案#

现在问题转化成了：构造一个 $n \times n$ 的方阵，用 $1 \sim n$ 填满，使得每行每列的 $1 \sim n$ 都恰好出现一次。

直接循环移位即可。使用 rotate() 会方便一些。

Code#

1
// Problem: 出题需要构造
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134527/D
4
// Time: 2026-05-08 20:01:20
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

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

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

30
    if (n != m || n == 1)
31
    {
32
        cout << "NO" << endl;
33
        return;
34
    }
35
    else
36
    {
37
        cout << "YES" << endl << 2 << endl;
38
        vector<int> a(n);
39
        iota(all(a), 1);
40

41
        for (int i = 0; i < m; i++)
42
        {
43
            for (auto x: a)
44
                cout << x << " ";
45
            cout << endl;
46

47
            rotate(a.begin(), a.begin() + 1, a.end());
48
        }
49
    }
50
}
51

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

56
    int T = 1;
57
    cin >> T;
58

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

62
    return 0;
63
}

E - 出题需要魔法#

关键词：单调栈，补集计数

思路#

对于排列中的某一个元素 $p_x$ ，题目要求找包含 $x$ 的子区间 $[l, r]$ （即 $l \leqslant x \leqslant r$ ），使得 $p_x$ 是“可见的”。

“可见的”意味着满足以下两个条件之一：

左边可见：区间 $[l, x]$ 中， $p_x$ 是最大值。也就是说，不能有比 $p_x$ 大的数出现在 $x$ 左边。
右边可见：区间 $[x, r]$ 中， $p_x$ 是最大值。也就是说，不能有比 $p_x$ 大的数出现在 $x$ 右边。

为了快速判断，我们可以预处理出两个数组：

$L[x]$ ：表示在 $x$ 左边，第一个大于 $p_x$ 的元素的下标。如果不存在，则 $L[x] = 0$ 。
$R[x]$ ：表示在 $x$ 右边，第一个大于 $p_x$ 的元素的下标。如果不存在，则 $R[x] = n + 1$ 。

NOTE
这部分预处理使用单调栈，从两侧分别扫一遍即可。
单调栈的作用就是找左右的第一个大于或者小于的坐标，一定要记住。

接下来我们把条件转化为对区间端点 $l$ 和 $r$ 的限制条件：

满足“左边可见”的方案数 ( $W_1$ )：

要保证左边没有比 $p_x$ 大的数，左端点 $l$ 必须越过 $L[x]$ ，即 $l \in [L[x] + 1, x]$ 。右端点 $r$ 可以随便选，即 $r \in [x, n]$ 。

所以， $W_1 = (x - L[x]) \times (n - x + 1)$
满足“右边可见”的方案数 ( $W_2$ )：

要保证右边没有比 $p_x$ 大的数，右端点 $r$ 必须在 $R[x]$ 之前，即 $r \in [x, R[x] - 1]$ 。左端点 $l$ 可以随便选，即 $l \in [1, x]$ 。

所以， $W_2 = x \times (R[x] - x)$
同时满足“左边和右边都可见”的方案数 ( $W_{12}$ )：

取上面两个条件的交集，即 $l \in [L[x] + 1, x]$ 且 $r \in [x, R[x] - 1]$ 。

所以， $W_{12} = (x - L[x]) \times (R[x] - x)$

根据容斥原理，满足“至少一边可见”的总方案数就是： $Ans(x) = W_1 + W_2 - W_{12}$

Code#

1
// Problem: 出题需要魔法
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134527/E
4
// Time: 2026-05-08 20:37:27
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

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

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

30
    vector<int> a(n + 1);
31
    for (int i = 1; i <= n; i++)
32
        cin >> a[i];
33

34
    vector<int> L(n + 1, 0);
35
    vector<int> R(n + 1, n + 1);
36

37
    stack<int> st;
38
    for (int i = 1; i <= n; i++)
39
    {
40
        while (!st.empty() && a[st.top()] < a[i])
41
            st.pop();
42

43
        if (!st.empty())
44
            L[i] = st.top();
45

46
        st.push(i);
47
    }
48

49
    stack<int> st2;
50
    for (int i = n; i >= 1; i--)
51
    {
52
        while (!st2.empty() && a[st2.top()] < a[i])
53
            st2.pop();
54

55
        if (!st2.empty())
56
            R[i] = st2.top();
57

58
        st2.push(i);
59
    }
60

61
    for (int i = 1; i <= n; i++)
62
    {
63
        ll W1 = 1LL * (i - L[i]) * (n - i + 1);
64
        ll W2 = 1LL * i * (R[i] - i);
65
        ll W12 = 1LL * (i - L[i]) * (R[i] - i);
66

67
        ll res = W1 + W2 - W12;
68

69
        cout << res << " ";
70
    }
71
    cout << "\n";
72
}
73

74
int main()
75
{
76
    fastio();
77

78
    int T = 1;
79
    cin >> T;
80

81
    while (T--)
82
        solve();
83

84
    return 0;
85
}

F - 出题需要树论#

关键词：树形DP，前后缀最大值

思路#

Gemini 对话记录，这个题有点困难，现在还不能完全理解。

假设我们选择节点 $u$ 进行操作，将其子树内所有节点的点权 $w_v$ 变为 $w_v \oplus x$ 。考虑这个操作对树上从根节点到任意节点 $k$ 的路径和造成的影响。

我们考虑把所有节点分为两类：

$k$ 不在 $u$ 的子树内：

此时，从根节点 $1$ 到 $k$ 的路径完全不会经过 $u$ 的子树，所以路径和保持不变，依然是原本的权值和。
$k$ 在 $u$ 的子树内：

此时，从根节点 $1$ 到 $k$ 的路径被分成了两段：
- $1 \to parent(u)$ ：这一段不在 $u$ 的子树内，权值保持不变。
- $u \to k$ ：这一段全部在 $u$ 的子树内，所有的点权都被异或了 $x$ 。

为了快速计算，我们可以用 DFS 预处理出两个数组：

$A[i]$ ：表示原树中，从根 $1$ 到节点 $i$ 的原点权路径和。
$B[i]$ ：表示假如所有节点点权都被异或 $x$ （即 $w_v \oplus x$ ），从根 $1$ 到节点 $i$ 的新点权路径和。

如果选择了节点 $u$ 进行操作，那么对于子树内的任意节点 $k$ ，新的路径和可以表示为： $S_{new}(k) = A[parent(u)] + (B[k] - B[parent(u)])$

其中 $A[parent(u)] - B[parent(u)]$ 对于固定的 $u$ 是一个常数。因此，子树内的最大路径和为： $\max_{k \in subtree(u)} S_{new}(k) = A[parent(u)] - B[parent(u)] + \max_{k \in subtree(u)} B[k]$ 。

而对于子树外的节点，最大路径和就是： $\max_{k \notin subtree(u)} A[k]$

NOTE
如何快速求“子树内/外”的最大值？

子树内的 $B[k]$ 最大值可以通过一次后序遍历计算；

子树外的 $A[k]$ 最大值，我们可以利用 DFS 序将树压缩成一维数组。子树外就对应了数组里的一段前缀和一段后缀。我们可以预处理该数组的前缀最大值 (pref) 和后缀最大值 (suff)，做到 $O(1)$ 查询。

DFS 序可以将一棵树拉直成一个一维数组，并且保证任何一棵子树在这个数组里都是连续的一段。
通过维护一个时间戳 timer，我们记录进树时间 dfn[u] = timer，记录进一维数组 seq[timer] = u 后递归子树，递归完成后记录出树时间 out[u] = timer。
我们可以将 [进树时间，出树时间] 看作一个区间，去一维数组里找这个子树。

Code#

1
// Problem: 出题需要树论
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134527/F
4
// Time: 2026-05-08 22:45:58
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

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

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

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

35
    vector<vector<int>> adj(n + 1);
36
    for (int i = 1; i < n; i++)
37
    {
38
        int u, v;
39
        cin >> u >> v;
40
        adj[u].push_back(v), adj[v].push_back(u);
41
    }
42

43
    // A[i] 存储原权值路径和，B[i] 存储异或后权值路径和
44
    vector<ll> A(n + 1, 0), B(n + 1, 0);
45
    vector<int> dfn(n + 1), out(n + 1), seq(n + 1), par(n + 1, 0);
46
    vector<ll> maxB(n + 1, 0);
47
    int t = 0;
48

49
    auto dfs = [&](auto &self, int u, int p) -> void
50
    {
51
        par[u] = p;
52
        A[u] = A[p] + w[u];
53
        B[u] = B[p] + (w[u] ^ x);
54

55
        t++;
56
        dfn[u] = t;
57
        seq[t] = u;
58

59
        maxB[u] = B[u];
60

61
        for (int v: adj[u])
62
        {
63
            if (v != p)
64
            {
65
                self(self, v, u);
66
                maxB[u] = max(maxB[u], maxB[v]);
67
            }
68
        }
69
        out[u] = t;
70
    };
71

72
    dfs(dfs, 1, 0);
73

74
    vector<ll> prefA(n + 2, 0), suffA(n + 2, 0);
75
    for (int i = 1; i <= n; i++)
76
        prefA[i] = max(prefA[i - 1], A[seq[i]]);
77

78
    for (int i = n; i >= 1; i--)
79
        suffA[i] = max(suffA[i + 1], A[seq[i]]);
80

81
    ll res = inf;
82

83
    for (int u = 1; u <= n; u++)
84
    {
85
        int p = par[u];
86

87
        // 子树内部的最大路径和
88
        ll I = A[p] - B[p] + maxB[u];
89

90
        // 子树外部的最大路径和
91
        ll O = max(prefA[dfn[u] - 1], suffA[out[u] + 1]);
92

93
        ll tmp = max(I, O);
94
        res = min(res, tmp);
95
    }
96

97
    cout << res << "\n";
98
}
99

100
int main()
101
{
102
    fastio();
103

104
    int T = 1;
105
    cin >> T;
106

107
    while (T--)
108
        solve();
109

110
    return 0;
111
}

A - 出题需要 rating#

Code#

B - 出题需要语文#

思路#

Code#

C - 出题需要加法#

思路#

Code#

D - 出题需要构造#

思路#

Step 1：确定 kkk 的值#

Step 2：确定 nnn 和 mmm 的关系#

Step3：构造方案#

Code#

E - 出题需要魔法#

思路#

Code#

F - 出题需要树论#

思路#

Code#

Step 1：确定 $k$ 的值#

Step 2：确定 $n$ 和 $m$ 的关系#