NOTE
比赛链接： https://ac.nowcoder.com/acm/contest/134059

TIP
难度预估表 by Liang_SYEA：

D - 铁银银铜金铜银银铁#

题目关键词：签到、STL

思路#

自己赛时唯一做出来的一道题，八分钟签到，然后后面四小时五十二分钟一道题都不会，唉唉…

和今年蓝桥杯的题面一样，任意一个子串都是回文串，当且仅当所有字符都相同。

所以我们遍历给定字符串，统计所有字母出现的次数，用总长度减去这个出现最多的字母即可。

Code#

1
// Problem: 铁银银铜金铜银银铁
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134059/D
4
// Time: 2026-04-26 16:36:10
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
    string s;
25

26
    map<char, int> mp;
27

28
    cin >> n >> s;
29

30
    for (auto c: s)
31
        mp[c]++;
32

33
    int mx = -1;
34
    for (auto &[ch, val]: mp)
35
        mx = max(val, mx);
36

37
    cout << (int) s.size() - mx << endl;
38
}
39

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

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

48
    return 0;
49
}

E - 树树菌的星形共振#

题目关键词：思维，贪心，DFS

思路#

赛时并没有开这道题，其实这道题也不是特别难，但是在那种环境下别说考虑异或了，连五芒星都想不到，还是缺乏开题策略了。

Step1 - 转化题意#

类五芒星#

将剩下的 $k$ 个节点排成环，且 $i$ 与 $(i+2) \bmod k$ 连边，最终必须是一个连通块。

按步长 $2$ 在大小为 $k$ 的环上跳跃，要能遍历所有节点（即形成单一连通块），其充要条件是 $\gcd(2, k) = 1$ ，这意味着 $k$ 必须是一个奇数

因此，最终保留的节点数 $k$ 必须是奇数。

共振频率#

假设经过若干次合并，我们最终把树划分成了 $k$ 个连通块（每个块缩成一个新节点），且每个新节点的发光频率（即该块内原节点的异或和）都等于同一个值 $X$ 。

根据异或运算的性质，这 $k$ 个节点的总异或和，必然等于原树所有 $n$ 个节点的总异或和 $S$ 。
所以有： $S = X \oplus X \oplus \dots \oplus X$ （共 $k$ 个 $X$ ）。
由于 $k$ 是奇数，奇数个 $X$ 异或的结果就是 $X$ 本身！
所以有以下结论：同频共振的目标频率 $X$ ，永远严格等于整棵树初始的全局异或和 $S$

Step2 - 贪心 DFS#

我们要把树切分成尽可能多的子树，使得每棵子树的异或和都等于 $S$ 。（因为切的块数 $k$ 越多，合并操作数 $n - k$ 就越少）。

我们可以从叶子节点往上做后序遍历：

用 cur 记录当前子树的异或和。
一旦发现 cur == S，我们就贪心地将这棵子树“剪下”，计数器 cnt++，然后向父节点返回 0（表示这部分已经被切走，对上方的异或和不再有影响）。

Step3 - 分类讨论结果#

情况 A： $S \neq 0$
- 如果全局异或和不为 $0$ ，根据数学逻辑，此时通过上述 DFS 切出来的块数 cnt 必定是奇数！（证明：总和是 $S$ ，所有切下来的块和也是 $S$ 。如果切了偶数块，它们的总和会变成 $0$ ，导致根节点剩余必然是 $S$ 从而再切一块，因此必定是奇数块）。
- 直接满足要求，最少操作数 = $n - cnt$ 。
情况 B： $S = 0$
- 如果全局异或和是 $0$ ，说明我们要找的共振频率就是 $0$ 。
- DFS 切出的 cnt 可能是偶数也可能是奇数。
- 如果 cnt 是奇数，满足条件，答案是 $n - cnt$ 。
- 如果 cnt 是偶数，因为我们必须保留奇数个节点，只需随便挑两个相邻的 $0$ 节点合并一下（ $0 \oplus 0 = 0$ ），节点数就变成了 $cnt - 1$ （奇数）。所以答案是 $n - (cnt - 1)$ 。

Code#

1
// Problem: 树树菌的星形共振
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134059/E
4
// Time: 2026-04-26 22:54:07
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 + 1);
27
    int S = 0; // 全局异或和
28
    for (int i = 1; i <= n; i++)
29
    {
30
        cin >> a[i];
31
        S ^= a[i];
32
    }
33

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

43
    int cnt = 0;
44

45
    auto dfs = [&](auto &self, int u, int p) -> int
46
    {
47
        int cur = a[u];
48
        for (auto v: adj[u])
49
        {
50
            if (v == p)
51
                continue;
52
            cur ^= self(self, v, u);
53
        }
54

55
        if (cur == S)
56
        {
57
            cnt++;
58
            return 0;
59
        }
60

61
        return cur;
62
    };
63

64
    dfs(dfs, 1, 0);
65

66
    if (S != 0)
67
        cout << n - cnt << endl;
68
    else
69
    {
70
        int k = (cnt % 2 == 1) ? cnt : (cnt - 1);
71
        cout << n - k << endl;
72
    }
73
}
74

75
int main()
76
{
77
    int T;
78
    cin >> T;
79
    while (T--)
80
        solve();
81
    return 0;
82
}

G - 不协和音程#

题目关键词：思维，STL，数据结构

思路#

赛时思路是对每次询问做 bfs，然后发现在空间的时候就被卡了…，而且 bfs 的复杂度绝对过不去… 哎，还是缺乏注意力了。

Step1 - 转化题目要求#

我们注意到题目要求：从 (1, 1) 走到 (n, m)，每次只能向下或向右移动。这意味着在任意合法的路径上，经过的坐标 $(x_1, y_1), (x_2, y_2), \dots$ 不管是横坐标还是纵坐标，都必须是单调不降的。

因此，对于一条路径上的任意两个点，不会出现一个点在另一个点的左下角的情况。

设整个矩阵中所有音高为 v 的点构成一个集合 $S_v$ ，如果我们把集合中所有点的坐标按 x 递增地排序，那么排序后的 y 坐标也必须是单调不降的。也就是说，假设 $x_{a} \ge x_{b}$ ，但 $y_{a} < y_{b}$ ，这两个点一定不能被同一条合法路径同时经过。

Step2 - 动态维护集合#

显然不能在每次查询时都重新遍历集合。

根据上面的推导，有以下的结论：如果在一个有序集合中，存在任意一对点破坏了纵坐标单调不降的规则，那么必然至少存在一对“相邻”的点破坏了规则。

上述结论的思考可以用反证法，假设所有相邻的点对都满足规则，显然整体一定是单调不降的。

因此，我们需要为每一种音高值 v 维护两个东西：

一个 set<pair<int, int>>，用来存储所有音高为 v 的坐标（自动按 $x$ 优先、 $y$ 其次排序）。
一个计数器 bad_count[v]，用来记录在 v 的集合中，有多少对相邻的元素构成了“前一个的 $y$ 大于后一个的 $y$ ”的非法情况。

那么两种操作的思路如下：

查询：只要 bad_count[x] == 0，就说明没有任何非法相邻对，直接输出 YES；否则输出 NO。
修改：将点从旧音高集合中删除，并加入新音高集合。在此过程中，只有插入/删除位置的前驱节点和后继节点的相邻关系会被打破或重建。我们只需在 $O(\log K)$ 的时间内局部更新 bad_count 即可。

TIP
注意：直接开定长数组会爆空间，要用 vector<vector<int>>

Code#

1
// Problem: 不协和音程
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134059/G
4
// Time: 2026-04-26 17:24:00
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 + 5;
20

21
set<pii> s[N];
22
int bad_count[N];
23

24
// 从音高v的集合中移除一个点(x, y)
25
void remove(int v, int x, int y)
26
{
27
    auto it = s[v].find({x, y});
28
    if (it == s[v].end())
29
        return;
30

31
    auto prev_it = it, next_it = it;
32
    bool has_prev = (it != s[v].begin());
33
    if (has_prev)
34
        prev_it--;
35

36
    next_it++;
37
    bool has_next = (next_it != s[v].end());
38

39
    // 如果和前驱构成了非法对，移除当前点后非法计数减少
40
    if (has_prev && prev_it->second > it->second)
41
        bad_count[v]--;
42

43
    // 如果和后继构成了非法对，移除当前点后非法计数减少
44
    if (has_next && it->second > next_it->second)
45
        bad_count[v]--;
46

47
    // 移除当前点后，前驱和后继变成了相邻关系，检查是否构成新的非法对
48
    if (has_prev && has_next && prev_it->second > next_it->second)
49
        bad_count[v]++;
50

51
    s[v].erase(it);
52
}
53

54
// 向音高v的集合中加入一个点(x, y)
55
void add(int v, int x, int y)
56
{
57
    auto result = s[v].insert({x, y});
58
    // 注意insert函数的返回值为std::pair<iterator, bool>
59

60
    auto it = result.first;
61
    auto prev_it = it, next_it = it;
62

63
    bool has_prev = (it != s[v].begin()); // 找前驱
64
    if (has_prev)
65
        prev_it--;
66

67
    next_it++;
68
    bool has_next = (next_it != s[v].end()); // 找后继
69

70
    // 加入当前点前，前驱和后继是相邻关系
71
    // 被当前点隔开后，如果之前的非法，就撤销之前的检查结果
72
    if (has_prev && has_next && prev_it->second > next_it->second)
73
        bad_count[v]--;
74

75
    // 检查插入新元素后，新元素和前驱是否非法
76
    if (has_prev && prev_it->second > it->second)
77
        bad_count[v]++;
78

79
    // 检查插入新元素后，新元素和后继是否非法
80
    if (has_next && it->second > next_it->second)
81
        bad_count[v]++;
82
}
83

84
int main()
85
{
86
    int n, m;
87
    cin >> n >> m;
88

89
    vector<vector<int>> g(n + 1, vector<int>(m + 1));
90

91
    for (int i = 1; i <= n; i++)
92
    {
93
        for (int j = 1; j <= m; j++)
94
        {
95
            int v;
96
            cin >> v;
97
            g[i][j] = v;
98
            add(v, i, j);
99
        }
100
    }
101

102
    int q;
103
    cin >> q;
104

105
    while (q--)
106
    {
107
        int op;
108
        cin >> op;
109

110
        if (op == 1)
111
        {
112
            int x, y, v;
113
            cin >> x >> y >> v;
114

115
            int prev_v = g[x][y];
116
            if (prev_v != v)
117
            {
118
                remove(prev_v, x, y);
119
                add(v, x, y);
120
                g[x][y] = v;
121
            }
122
        }
123
        else
124
        {
125
            int x;
126
            cin >> x;
127
            if (bad_count[x] == 0)
128
                cout << "YES" << endl;
129
            else
130
                cout << "NO" << endl;
131
        }
132
    }
133
}

I - Yet Another Patchouli’s Magical Problem#

题目关键词：思维，构造

思路#

赛时思路非常混乱，我考虑的是蛇形填进来，但是怎么调都不对，想了两个多小时无果 qwq

注意：样例有一定的迷惑性，务必自行判断！

在把二维网格变成一维序列的过程中，当我们放完某几个节点后，序列可以看作被切成两半：已放置的节点集合 $S$ 和未放置的节点集合 $V \setminus S$ 。所谓的“间隔负载”，就是计算此时此刻，有多少条边连接着 $S$ 和 $V \setminus S$ 。

我们考虑按照朴素的按行遍历来排列节点来计算负载：

假设已经放完了第 $i-1$ 行，现在正在放第 $i$ 行，且恰好放到了第 $j$ 列的节点 $(i, j)$ 。

考虑跨越当前这个间隔的边，有三种情况：

向下的纵向边：从第 $i$ 行已放置的节点 $(i, 1) \dots (i, j)$ 连向它们正下方的第 $i+1$ 行。这里有 $j$ 条边。
上一行剩余的向下的纵向边：从第 $i-1$ 行尚未被覆盖下方节点的位置连向第 $i$ 行。也就是列数从 $j+1$ 到 $m$ 的位置。这里有 $m-j$ 条边。
向右的横向边：当前刚放下的节点 $(i, j)$ 连向下一个即将放置的节点 $(i, j+1)$ 。这里有 $1$ 条边。

TIP
将三种情况相加，有 $j + (m - j) + 1 = m + 1$ ，也就是说，在逐行放置的过程中，只要处于网格的内部，任何一个间隔的负载恰好等于 $m + 1$

题目要求最大负载 $C \le \min(n,m)+1$ 。

根据刚才的推导：

如果我们逐行放置，最大负载是 $m + 1$ 。当 $m \le n$ 时，满足要求
如果我们逐列放置，最大负载就是 $n + 1$ 。当 $n < m$ 时，满足要求

Code#

1
// Problem: Yet Another Patchouli's Magical Problem
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134059/I
4
// Time: 2026-04-26 16:37:26
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
int n, m;
22

23
int main()
24
{
25
    cin >> n >> m;
26

27
    if (m <= n)
28
    {
29
        for (int i = 1; i <= n; i++)
30
            for (int j = 1; j <= m; j++)
31
                cout << i << " " << j << endl;
32
    }
33
    else
34
    {
35
        for (int j = 1; j <= m; j++)
36
            for (int i = 1; i <= n; i++)
37
                cout << i << " " << j << endl;
38
    }
39
    return 0;
40
}

J - The Eschatology of 0 and 1#

题目关键词：贪心，线性 DP

思路#

赛时只是有感觉这可能是个 DP，不过也没开就是了…

Step1 - 转化题意#

假设当前我们确定的目标字符是 T，对于原串当中的每一个字符，它要么是正确的（已经等于 T），要么是错误的，在这个想法上，我们做题目中的两种操作：

操作 1 (单点修改)：翻转一个字符的代价是 a。
操作 2 (区间修改)：翻转一个长度为 L 的区间的代价是 k * L + b。这相当于进行一次区间翻转需要固定花费 b，然后区间内每一个字符都要花费代价 k。

现在我们考虑，假设原串中有两个错误字符构成的块，中间隔着一段正确的字符（比如 错错对对错错）。我们有两个选择：

不合并（执行两次独立的操作 2）：分别翻转两端的错误块，中间的正确字符不受影响。代价是两次的 b，加上错误字符数量乘以 k。
合并（执行一次很大的操作 2，然后再修正中间的正确字符）：用一次操作 2 把整个区间全翻了，省下了一次 b。但这会导致中间的正确字符被翻成了错误字符。我们考虑如何将这些错误字符再翻回来：
- 如果用操作 1 翻回来，每个字符的代价是 a。那么这些中间字符被这次大操作覆盖的总代价是：k (被操作 2 覆盖) + a (被操作 1 修正) = k + a。
- 如果用操作 2 翻回来，相当于在内部嵌套了一个新的区间翻转。因为 k >= 0，嵌套区间操作的额外代价（增加的 k * L 和新的 b）永远大于或等于直接把大区间断开成两个小区间。

根据上面的推导，对于任何一个字符，只有三种最优命运：

它是正确的，且不在操作 2 的区间内。代价：0。
它是错误的，且在操作 2 的区间内被顺手翻正。代价：k。
它被操作 1 单独翻转。代价：a。
- 如果一个正确的字符被包含在了一个大区间内（为了省 b 而强行合并区间），它必须由操作 1 翻回来，它的总代价就是 k + a。

Step2 - DP#

我们只需要从左到右遍历字符串，每一个字符只面临一个选择：它是否被包含在一个连续的“操作 2 区间”内部？

状态表示：

我们可以定义两个状态，代表到达第 i 个字符时的最小代价：

dp0: 当前字符不在操作 2 区间内。
dp1: 当前字符在操作 2 区间内。

状态转移：

假设当前考虑的目标字符是 T。

当前字符的验证结果为 correct = (s[i] == T)。

如果在区间外 (dp0)：
- 所需代价 cost_out：如果 correct，不需要翻转，代价为 0；如果错误，必须用操作 1 翻转，代价为 a。
- 它可以从上一个不在区间内的状态 (dp0) 继续保持，也可以从上一个区间内的状态 (dp1) 结束区间转移过来。转移方程： $new\_dp0 = \min(dp0, dp1) + cost\_out$
如果在区间内 (dp1)：
- 所需代价 cost_in：如果错误，被区间顺手翻正，代价为 k；如果 correct，被区间搞坏了必须用操作 1 补救，代价为 k + a。
- 它可以从上一个区间内的状态 (dp1) 延续过来，也可以从上一个不在区间内的状态 (dp0) 新开启一个区间转移过来（新开启需要额外支付固定代价 b）。转移方程： $new\_dp1 = \min(dp0 + b, dp1) + cost\_in$

因为目标是将整个二进制串变为全 0 或全 1，我们分别计算两种情况的代价并取 min。

Code#

1
// Problem: The Eschatology of 0 and 1
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134059/J
4
// Time: 2026-04-26 18:41:45
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 ll inf = 2e18;
19
const int N = 0;
20

21
ll sol(string &s, char target_char, ll a, ll b, ll k)
22
{
23
    ll dp0 = 0, dp1 = inf;
24

25
    for (char c: s)
26
    {
27
        bool correct = (c == target_char);
28

29
        ll cost_out = correct ? 0 : a;
30
        ll cost_in = correct ? (k + a) : k;
31

32
        // 状态转移
33
        ll next_dp0 = min(dp0, dp1);
34
        if (next_dp0 != inf)
35
            next_dp0 += cost_out;
36

37
        ll next_dp1 = min(dp0 != inf ? dp0 + b : inf, dp1);
38
        if (next_dp1 != inf)
39
            next_dp1 += cost_in;
40

41
        dp0 = next_dp0;
42
        dp1 = next_dp1;
43
    }
44

45
    // 字符串遍历结束，无论是区间刚好结束(dp0)还是刚好切断(dp1)，取两者最优即可
46
    return min(dp0, dp1);
47
}
48

49
void solve()
50
{
51
    ll n, a, b, k;
52
    cin >> n >> a >> b >> k;
53

54
    string s;
55
    cin >> s;
56

57
    ll res0 = sol(s, '0', a, b, k);
58
    ll res1 = sol(s, '1', a, b, k);
59

60
    cout << min(res0, res1) << endl;
61
}
62

63
int main()
64
{
65
    int T;
66
    cin >> T;
67

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

71
    return 0;
72
}