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

A - 小红的好串#

关键词：签到

Code#

1
// Problem: 小红的好串
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136016/A
4
// Time: 2026-05-24 21:32:41
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
    string s;
29
    cin >> s;
30

31
    map<char, int> mp;
32
    for (auto c: s)
33
        mp[c]++;
34
    if (mp.size() == 2)
35
        cout << "Yes" << endl;
36
    else
37
        cout << "No" << endl;
38
}
39

40
int main()
41
{
42
    fastio();
43

44
    int T = 1;
45
    // cin >> T;
46

47
    while (T--)
48
        solve();
49

50
    return 0;
51
}

B - 小红的好串计数#

关键词：模拟

思路#

正难则反，考虑计算不好的串的贡献。注意到不好的串一定是连续的，计算坏串贡献的表达式与计算全部子串的表达式相同。

Code#

1
// Problem: 小红的好串计数
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136016/B
4
// Time: 2026-05-24 21:34:13
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 n;
29
    string s;
30
    cin >> n >> s;
31

32
    ll tot = (n + 1) * n / 2, res = 0;
33
    for (ll i = 0; i < n;)
34
    {
35
        ll j = i;
36
        while (j < n && s[j] == s[i])
37
            j++;
38
        res += (j - i + 1) * (j - i) / 2;
39
        i = j;
40
    }
41
    cout << tot - res << endl;
42
}
43

44
int main()
45
{
46
    fastio();
47

48
    int T = 1;
49
    // cin >> T;
50

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

54
    return 0;
55
}

C - 小红的染色平均数#

关键词：数学

思路#

注意到操作并不改变所有元素的和，根据平均数相等，且目标总和之和等于原数组总和 $sum$ ：有 $\frac{S_0'}{cnt_0} = \frac{S_1'}{cnt_1}$ 和 $S_0' + S_1' = sum$ ，将 $S_1' = sum - S_0'$ 代入第一个等式，有 $\frac{S_0'}{cnt_0} = \frac{sum - S_0'}{cnt_1}$ ，移项有 $S_0' (cnt_0 + cnt_1) = sum \cdot cnt_0$ ， $S_0' = \frac{sum \cdot cnt_0}{n}$ ，如果 (sum * cnt0) % n != 0，则判定无解。

Code#

1
// Problem: 小红的染色平均数
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136016/C
4
// Time: 2026-05-24 21:42:18
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<int> a(n);
32
    for (auto &x: a)
33
        cin >> x;
34

35
    ll sum = accumulate(all(a), 0LL);
36

37
    string s;
38
    cin >> s;
39

40
    ll sum0 = 0, sum1 = 0, cnt0 = 0, cnt1 = 0;
41

42
    for (int i = 0; i < n; i++)
43
    {
44
        if (s[i] == '0')
45
            sum0 += (ll) a[i], cnt0++;
46
        else
47
            sum1 += (ll) a[i], cnt1++;
48
    }
49

50
    if ((sum * cnt0) % n != 0)
51
    {
52
        cout << "-1" << endl;
53
        return;
54
    }
55

56
    cout << abs((cnt1 * sum0 - cnt0 * sum1) / (cnt0 + cnt1)) << endl;
57
}
58

59
int main()
60
{
61
    fastio();
62

63
    int T = 1;
64
    // cin >> T;
65

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

69
    return 0;
70
}

D - 小红的排列构造#

关键词：构造

思路#

相比于分配数字，我们考虑分配下标。

既然对于每个位置 $i$ ，都要满足 $b_i = a_i$ 或 $c_i = a_i$ ，这意味着每个下标 $i$ 都要“分配”给 $b$ 或者 $c$ 作为匹配位。我们要确保 $b$ 和 $c$ 各自分配到恰好 $\frac{n}{2}$ 个下标。

处理出现 2 次的数字：如果某个数字 $x$ 在下标 $i$ 和 $j$ 出现了两次。因为排列里不能有重复数字，所以 $b$ 只能在其中一个下标匹配 $x$ ， $c$ 在另一个下标匹配 $x$ 。

操作：将下标 $i$ 分配给 $b$ ，下标 $j$ 分配给 $c$ 。

处理出现 1 次的数字：对于只出现一次的数字，它可以分配给 $b$ ，也可以分配给 $c$ 。

操作：我们检查 $b$ 当前分配到的匹配位数量，如果还不满 $\frac{n}{2}$ ，就分配给 $b$ ；否则全部分配给 $c$ 。

填补空缺，构造完整排列：剩下的 $\frac{n}{2}$ 个空位，只要找出 $1 \sim n$ 中还没有被该数组使用的数字，依次填入空位即可。因为填入的是剩余未使用过的数字，所以能保证构成一个合法的排列。

Code#

1
// Problem: 小红的排列构造
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136016/D
4
// Time: 2026-05-24 21:58:45
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<int> a(n);
32
    vector<int> cnt(n + 1, 0);
33

34
    vector<vector<int>> pos(n + 1);
35

36
    for (int i = 0; i < n; i++)
37
    {
38
        cin >> a[i];
39
        cnt[a[i]]++;
40
        pos[a[i]].push_back(i);
41
    }
42

43
    for (int i = 1; i <= n; i++)
44
    {
45
        if (cnt[i] >= 3)
46
        {
47
            cout << -1 << endl;
48
            return;
49
        }
50
    }
51

52
    vector<int> b(n, 0), c(n, 0);
53
    vector<bool> stb(n + 1, false), stc(n + 1, false);
54
    int usedb = 0;
55

56
    for (int i = 1; i <= n; i++)
57
    {
58
        if (cnt[i] == 2)
59
        {
60
            int p1 = pos[i][0], p2 = pos[i][1];
61

62
            b[p1] = i, stb[i] = true, usedb++;
63

64
            c[p2] = i, stc[i] = true;
65
        }
66
    }
67

68
    for (int i = 1; i <= n; i++)
69
    {
70
        if (cnt[i] == 1)
71
        {
72
            int p = pos[i][0];
73
            if (usedb < n / 2)
74
                b[p] = i, stb[i] = true, usedb++;
75
            else
76
                c[p] = i, stc[i] = true;
77
        }
78
    }
79

80
    vector<int> left_b, left_c;
81
    for (int i = 1; i <= n; i++)
82
    {
83
        if (!stb[i])
84
            left_b.push_back(i);
85
        if (!stc[i])
86
            left_c.push_back(i);
87
    }
88

89
    int idxb = 0, idxc = 0;
90
    for (int i = 0; i < n; i++)
91
    {
92
        if (b[i] == 0)
93
            b[i] = left_b[idxb++];
94
        if (c[i] == 0)
95
            c[i] = left_c[idxc++];
96
    }
97

98
    for (auto i: b)
99
        cout << i << " ";
100
    cout << endl;
101
    for (auto i: c)
102
        cout << i << " ";
103
}
104

105
int main()
106
{
107
    fastio();
108

109
    int T = 1;
110
    // cin >> T;
111

112
    while (T--)
113
        solve();
114

115
    return 0;
116
}

E - 小红的染色生成树#

关键词：构造，Kruskal

思路#

由于需要恰好出现两次，分别对 $0, 1$ ， $0, 2$ ， $1, 2$ 做 $Kruskal$ 即可。

每个 $Kruskal$ 的过程需要扫两遍，第一遍强行挑出第一条颜色为 A 的边和第一条颜色为 B 的边加入并查集。这样就保证了如果能生成树，里面必定“恰好包含这两种颜色”；扫完第一遍后，假如一条 $a$ 或一条 $b$ 都找不到，就直接返回 false。第二遍正常扫，把树补全。最后检查并查集中所有点是否连通。

Code#

1
// Problem: 小红的染色生成树
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134981/E
4
// Time: 2026-05-25 19:13:36
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 = 2e5 + 10;
25

26
struct Edge
27
{
28
    int u, v, w;
29
} edges[N];
30

31
struct DSU
32
{
33
    vector<int> parent;
34
    vector<int> sz;
35
    int comp_cnt;
36

37
    DSU(int n)
38
    {
39
        parent.resize(n + 1);
40
        iota(parent.begin(), parent.end(), 0);
41
        sz.assign(n + 1, 1);
42
        comp_cnt = n;
43
    }
44

45
    int find(int i)
46
    {
47
        if (parent[i] == i)
48
            return i;
49
        return parent[i] = find(parent[i]);
50
    }
51

52
    bool unite(int i, int j)
53
    {
54
        int pi = find(i);
55
        int pj = find(j);
56
        if (pi != pj)
57
        {
58
            if (sz[pi] < sz[pj])
59
                swap(pi, pj);
60
            parent[pj] = pi;
61
            sz[pi] += sz[pj];
62
            comp_cnt--;
63
            return true;
64
        }
65
        return false;
66
    }
67
};
68

69
void solve()
70
{
71
    int n, m;
72
    cin >> n >> m;
73

74
    for (int i = 0; i < m; i++)
75
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
76

77
    auto Kruskal = [&](int a, int b) -> bool
78
    {
79
        DSU dsu(n);
80
        vector<pii> res;
81
        bool f1 = false, f2 = false;
82

83
        for (int i = 0; i < m; i++)
84
        {
85
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
86
            if (w == a && !f1)
87
            {
88
                dsu.unite(u, v);
89
                res.push_back({u, v});
90
                f1 = true;
91
            }
92
            else if (w == b && !f2)
93
            {
94
                dsu.unite(u, v);
95
                res.push_back({u, v});
96
                f2 = true;
97
            }
98
        }
99

100
        if (!f1 || !f2)
101
            return false;
102

103
        for (int i = 0; i < m; i++)
104
        {
105
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
106
            if (w != a && w != b)
107
                continue;
108

109
            if (dsu.unite(u, v))
110
                res.push_back({u, v});
111
        }
112

113
        if (dsu.comp_cnt == 1)
114
        {
115
            for (auto &[u, v]: res)
116
                cout << u << " " << v << endl;
117
            return true;
118
        }
119
        return false;
120
    };
121

122
    if (!Kruskal(0, 1) && !Kruskal(0, 2) && !Kruskal(1, 2))
123
        cout << -1 << endl;
124
}
125

126
int main()
127
{
128
    fastio();
129

130
    int T = 1;
131
    // cin >> T;
132

133
    while (T--)
134
        solve();
135

136
    return 0;
137
}

F - 小红的好串构造#

关键词：构造，数学

思路#

为了让 $k$ 的计算最简单，我们考虑一种构造方法：让夹在中间的字符隔断两边的计算。

$\underbrace{a \dots a}_{x \text{ 个}} + \mathbf{b} + \mathbf{a} + \underbrace{c \dots c}_{z \text{ 个}}$

在这个字符串中，一共只有三种字符 a, b, c。我们来统计它的好串数量：

含 a 和 b 的好串：必须包含 b。左端点可以在前面的 $x$ 个 a 或是 b 自己身上（共 $x+1$ 种选择），右端点可以是 b 自己或是后面紧跟的那个 a（共 2 种选择）。减去只有 b 自己的一种情况。总数为 $2(x+1) - 1 = \mathbf{2x + 1}$ 。
含 a 和 c 的好串：不能包含 b。所以左端点只能是中间那个被 b 和 c 夹着的孤独的 a（1 种选择）。右端点落在后面 $z$ 个 c 的任意位置。总数为 $\mathbf{z}$ 。
含 b 和 c 的好串：只要同时包含 b 和 c，就必定会跨过中间的那个 a，导致含有 3 种字符，全部不合法，总数为 $\mathbf{0}$ 。

将它们相加，总好串数量 $Sum = 2x + 1 + z$ 。又因为字符串总长度 $n = x + 1 + 1 + z \implies z = n - x - 2$ 。

代入得到： $Sum = 2x + 1 + (n - x - 2) = \mathbf{n + x - 1}$ 。根据已知条件， $Sum = k$ 。

且由于题目约束： $n-1 \le k \le 2n-4$ ，最小值 $k = n-1 \implies x = 0$ ，最大值 $k = 2n-4 \implies x = n-3 \implies z = 1$ ，因此 $x$ 和 $z$ 永远是合法的非负数。

Code#

1
// Problem: 小红的好串构造
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134981/F
4
// Time: 2026-05-25 20:10: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
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 n, k;
29
    cin >> n >> k;
30

31
    ll x = k - n + 1;
32
    ll z = n - 2 - x;
33

34
    // x 个 'a' + "ba" + z 个 'c'
35
    string res = string(x, 'a') + "ba" + string(z, 'c');
36

37
    cout << res << endl;
38
}
39

40
int main()
41
{
42
    fastio();
43

44
    int T = 1;
45
    cin >> T;
46

47
    while (T--)
48
        solve();
49

50
    return 0;
51
}