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

A - 小苯的ovo 3.0#

关键词：签到

Code#

1
// Problem: 小苯的ovo3.0
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/133790/A
4
// Time: 2026-05-03 19:00:02
5

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

9
#define endl '\n'
10

11
typedef long long ll;
12
typedef unsigned long long ull;
13
typedef pair<int, int> pii;
14
typedef pair<double, double> pdd;
15
typedef pair<long long, long long> pll;
16

17
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
18
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
19
const int inf = 0x3f3f3f3f;
20
const int N = 0;
21

22
int main()
23
{
24
    string s;
25
    cin >> s;
26

27
    if (s[0] == 'o' || s[0] == 'O')
28
    {
29
        if (s[1] == 'v' || s[1] == 'V')
30
        {
31
            if (s[2] == 'o' || s[2] == 'O')
32
            {
33
                cout << "YES" << endl;
34
                return 0;
35
            }
36
        }
37
    }
38

39
    cout << "NO" << endl;
40
    return 0;
41
}

B - 小苯的双端队列#

关键词：签到，模拟

思路#

用两个指针来模拟，左指针指向开头，右指针指向尾部，每次操作都必须让左右指针其中的一个可以移动，否则序列不合法。

Code#

1
// Problem: 小苯的双端队列
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/133790/B
4
// Time: 2026-05-03 19:02:27
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20

21
void solve()
22
{
23
    int n;
24
    cin >> n;
25

26
    vector<int> b(n);
27
    for (int i = 0; i < n; i++)
28
        cin >> b[i];
29

30
    int l = 1, r = n;
31

32
    bool flag = true;
33

34
    for (int i = 0; i < n; i++)
35
    {
36
        if (b[i] == l)
37
            l++;
38
        else if (b[i] == r)
39
            r--;
40
        else
41
        {
42
            flag = false;
43
            break;
44
        }
45
    }
46

47
    if (flag)
48
        cout << "YES" << endl;
49
    else
50
        cout << "NO" << endl;
51
}
52

53
int main()
54
{
55
    int T;
56
    cin >> T;
57

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

61
    return 0;
62
}

C - 小苯的整除序列#

关键词：模拟

思路#

由于子序列不要求连续，我们只需要模拟这个整除的过程即可。

具体来说，在遍历数组的同时，我们不断尝试能否整除 idx，遍历结束后记得将 idx 减掉 1。

Code#

1
// Problem: 小苯的整除序列
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/133790/C
4
// Time: 2026-05-03 19:18:49
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20

21
void solve()
22
{
23
    int n;
24
    cin >> n;
25

26
    vector<int> a(n);
27
    for (int i = 0; i < n; i++)
28
        cin >> a[i];
29

30
    int idx = 1;
31
    for (int i = 0; i < n; i++)
32
    {
33
        if (a[i] % idx == 0)
34
            idx++;
35
    }
36

37
    cout << idx - 1 << endl;
38
}
39

40
int main()
41
{
42
    int T;
43
    cin >> T;
44

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

48
    return 0;
49
}

D - 小苯的幼儿园#

关键词：数学

思路#

由于要求最终每个人的糖果数量一样，所以有 sum % n == 0，首先过滤掉一部分数据。

设目标糖果数为 $k$ ，假设第 $i$ 个小朋友给他右边的第 $i+1$ 个小朋友的糖果数为 $x_i$ ，根据题意， $x_i$ 的取值只能是 0 或 1。

第 $i$ 个小朋友最终的糖果数，等于他原本的糖果数 $a_i$ ，减去他给出去的 $x_i$ ，加上他收到的 $x_{i-1}$ ： $a_i - x_i + x_{i-1} = k$ 。

将方程变形，有 $a_i - x_i + x_{i-1} = k$ ，这是一个递推式，意味着我们只要确定了第0个小朋友给出的糖果数量 $x_0$ ，后面的 $x_1, x_2, \dots, x_{n-1}$ 就全部唯一确定了。

我们只需要在算完平均数 $k$ 后，写一个 check 函数。分别假设 $x_n = 0$ 和 $x_n = 1$ ，然后顺着递推式验证一遍：如果途中没有任何 $x_i$ 越界（即不是 0 也不是 1），且最终首尾能闭合，就是合法的。

NOTE
总结：遇到这种“同时传递”的环形问题，考虑设未知数并列出传递方程。

Code#

1
// Problem: 小苯的幼儿园
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/133790/D
4
// Time: 2026-05-03 19:22:20
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20

21
void solve()
22
{
23
    int n;
24
    cin >> n;
25

26
    ll sum = 0;
27

28
    vector<ll> a(n), b(n);
29
    for (int i = 0; i < n; i++)
30
    {
31
        cin >> a[i];
32
        sum += a[i];
33
    }
34

35
    if (sum % n != 0)
36
    {
37
        cout << "NO" << endl;
38
        return;
39
    }
40

41
    ll tg = sum / n;
42

43
    auto check = [&](int t) -> bool
44
    {
45
        int x = t;
46
        for (int i = 0; i < n; i++)
47
        {
48
            x = x + a[i] - tg;
49
            if (x < 0 || x > 1)
50
                return false;
51
        }
52
        return (x == t);
53
    };
54

55
    if (check(0) || check(1))
56
        cout << "YES" << endl;
57
    else
58
        cout << "NO" << endl;
59
}
60

61
int main()
62
{
63
    int T;
64
    cin >> T;
65

66
    while (T--)
67
        solve();
68

69
    return 0;
70
}

E - 小苯的区间操作#

关键词：思维

思路#

我们可以用一种形象的方式来思考：把原数组想象成一个由方块堆成的山（柱状图）。我们翻译一下题目的要求：

区间长度 $\ge 2$ ：你手里有一把宽度至少为 2 的铲子。
$a_L = a_R$ 且内部 $a_i \ge a_L$ ：你这把铲子必须平着铲（两端高度一样），并且铲子中间的部分不能悬空（区间内的地形不能有低于铲子底部的“坑”）。
区间内全部减 1：每次你可以把这一层、宽度至少为 2 的方块给水平“削”掉一层。

我们的目标是把整座山用铲子削成全为 0。

既然铲子的最小宽度为 2，显然我们无论如何也削不掉宽度仅为 1 的孤峰，也就是说，只要数组中存在任何一个严格大于左右相邻元素的点，我们就无法将数组清零。如果不存在这样的“孤峰”，我们总是可以从最高处找到宽度 $\geq 2$ 的平顶山脉，一层层削平。

考虑特判开头和结尾的状况，只要把数组长度开成 n + 2，把原来的数放在位置 1 ~ n，在前后补上 0 即可。实际上整个山的物理边界之外，就是海拔为 0 的平地。

例如 [5, 3] 实际上应该是 [0, 5, 3, 0]。

因此我们可以在 $O(n)$ 的时间下解决这个问题。

Code#

1
// Problem: 小苯的区间操作
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/133790/E
4
// Time: 2026-05-03 19:43:34
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20

21
void solve()
22
{
23
    int n;
24
    cin >> n;
25

26
    vector<int> a(n + 2, 0);
27
    for (int i = 1; i <= n; i++)
28
        cin >> a[i];
29

30
    bool flag = true;
31
    for (int i = 1; i <= n + 1; i++)
32
    {
33
        if (a[i] > a[i - 1] && a[i] > a[i + 1])
34
        {
35
            flag = false;
36
            break;
37
        }
38
    }
39

40
    if (flag)
41
        cout << "Yes" << endl;
42
    else
43
        cout << "No" << endl;
44
}
45

46
int main()
47
{
48
    int T;
49
    cin >> T;
50

51
    while (T--)
52
        solve();
53

54
    return 0;
55
}

F - 小苯的DFS#

思路：树上DFS，组合数学，概率计数

思路#

题目要求我们在 DFS 时，第一次到达节点就把它的权值加进序列 $b$ 中。也就是树的前序遍历。

既然要求整个前序遍历序列单调不降，这意味着我们在遍历树的过程中，得到的值必须越来越大。

我们考虑遍历过程中的限制因素：

父亲与子树的限制：对于任意节点 $u$ ，它的权值 $w_u$ 必须小于等于它整个子树里所有节点的权值；
兄弟子树的限制：假设 $u$ 决定按照 $c_1, c_2, \dots, c_k$ 的顺序访问它的子节点。那么我们肯定是先把 $c_1$ 这棵子树全部遍历完，再进入 $c_2$ 。为了保证单调不降， $c_1$ 子树里的最大值，必须小于等于 $c_2$ 子树里的最小值。

根据上面的推导，我们发现我们不需要关心子树内部的具体结构，只需要知道每棵子树的最小值和最大值即可。

我们考虑把每棵子树压缩成一个区间来表示。

设以 $v$ 为根的子树，节点权值的最小值为 $mn[v]$ ，最大值为 $mx[v]$ 。对于 $u$ 的所有子节点 $c_i$ ，我们相当于得到了一个个区间 $[mn[c_i], mx[c_i]]$ 。

为了满足“前一棵子树的最大值 $\le$ 后一棵子树的最小值”，我们要将这些区间进行排序。显然，只有按 $mn[v]$ 从小到大升序排序，才“有可能”满足条件。

排序后，我们只需要检查一遍相邻区间：如果存在某个 $mx[c_i] > mn[c_{i+1}]$ ，说明这棵树排不出合法的顺序，合法概率为 0。

我们考虑如何计算概率。

假设在节点 $u$ 处有 $k$ 个子节点，那么一共有 $k!$ 种打乱方式，合法排列并不唯一。如果存在完全相同的“单点区间”（比如 $[X, X]$ 和 $[X, X]$ ），这两棵子树的顺序不影响单调不降的性质，假设有 $C$ 个一模一样的区间，它们之间就有 $C!$ 种合法的排列组合。所以节点 $u$ 的局部合法概率为 $\frac{\prod (C_X!)}{k!}$ ，把所有节点的概率相乘即为正确答案。

NOTE
总结：从单调不降的性质入手，这道题的关键在于将每个子树压缩成一个 [min, max] 区间来处理，在统计合法方案时要用到组合数学知识。

Code#

1
// Problem: 小苯的DFS
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/133790/F
4
// Time: 2026-05-03 19:55:54
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 2e5 + 10;
20
const ll mod = 998244353;
21

22
vector<int> adj[N];
23
ll w[N], mn[N], mx[N];
24
ll fact[N], infact[N];
25
bool flag;
26
ll res;
27

28
ll qmi(ll a, ll k)
29
{
30
    ll res = 1;
31
    while (k)
32
    {
33
        if (k & 1)
34
            res = (ll) res * a % mod;
35

36
        a = (ll) a * a % mod;
37
        k >>= 1;
38
    }
39
    return res;
40
}
41

42
void init()
43
{
44
    fact[0] = 1, infact[0] = 1;
45
    for (int i = 1; i < N; i++)
46
        fact[i] = fact[i - 1] * i % mod;
47

48
    infact[N - 1] = qmi(fact[N - 1], mod - 2);
49

50
    for (int i = N - 2; i >= 1; i--)
51
        infact[i] = infact[i + 1] * (i + 1) % mod;
52
}
53

54
void dfs(int u, int p)
55
{
56
    mn[u] = w[u], mx[u] = w[u];
57

58
    vector<pll> segs; // 将子树压缩成区间
59
    int cnt = 0; // 子节点个数
60

61
    for (int v: adj[u])
62
    {
63
        if (v == p)
64
            continue;
65

66
        dfs(v, u);
67

68
        if (!flag)
69
            return; // 可行性剪枝
70

71
        mn[u] = min(mn[u], mn[v]);
72
        mx[u] = max(mx[u], mx[v]);
73

74
        segs.push_back({mn[v], mx[v]});
75
        cnt++;
76
    }
77

78
    // 父节点不能大于子树中的最小值
79
    if (w[u] > mn[u])
80
    {
81
        flag = false;
82
        return;
83
    }
84

85
    if (cnt > 0)
86
    {
87
        sort(segs.begin(), segs.end());
88

89
        // 前一个子树的最大值必须小于等于后一个子树的最小值
90
        for (int i = 0; i < cnt - 1; i++)
91
            if (segs[i].second > segs[i + 1].first)
92
            {
93
                flag = false;
94
                return;
95
            }
96

97
        ll valid = 1;
98
        for (int i = 0; i < cnt;)
99
        {
100
            int j = i;
101
            while (j < cnt && segs[j] == segs[i])
102
                j++;
103

104
            valid = valid * fact[j - i] % mod;
105
            i = j;
106
        }
107

108
        res = ((res * valid) % mod) * infact[cnt] % mod;
109
    }
110
}
111

112
void solve()
113
{
114
    int n;
115
    cin >> n;
116

117
    for (int i = 1; i <= n; i++)
118
    {
119
        cin >> w[i];
120
        adj[i].clear();
121
    }
122

123
    for (int i = 0; i < n - 1; i++)
124
    {
125
        int u, v;
126
        cin >> u >> v;
127
        adj[u].push_back(v), adj[v].push_back(u);
128
    }
129

130
    flag = true;
131
    res = 1;
132

133
    dfs(1, 0);
134

135
    if (!flag)
136
        cout << 0 << endl;
137
    else
138
        cout << res << endl;
139
}
140

141
int main()
142
{
143
    ios::sync_with_stdio(false);
144
    cin.tie(0);
145

146
    init();
147

148
    int T;
149
    cin >> T;
150

151
    while (T--)
152
        solve();
153

154
    return 0;
155
}