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

A - 小红的区间构造#

关键词：签到

Code#

1
// Problem: 小红的区间构造
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134529/A
4
// Time: 2026-05-10 19:00:07
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
using i128 = __int128;
21

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

27
void solve()
28
{
29
    ll n;
30
    cin >> n;
31
    cout << 1 << " " << n << endl;
32
}
33

34
int main()
35
{
36
    fastio();
37

38
    int T = 1;
39
    // cin >> T;
40

41
    while (T--)
42
        solve();
43

44
    return 0;
45
}

B - 小红的冷门副本#

关键词：思维

思路#

由于 $m$ 的范围太大，如果开数组一定会超空间，假如开 map 正着遍历又会超时间。

我们考虑反着做，统计 $>x$ 的所有副本，用总数减掉即可。

Code#

1
// Problem: 小红的冷门副本
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134529/B
4
// Time: 2026-05-10 19:01:08
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, m, x;
29
    cin >> n >> m >> x;
30

31
    map<ll, int> mp;
32

33
    for (int i = 1; i <= n; i++)
34
    {
35
        int k;
36
        cin >> k;
37
        mp[k]++;
38
    }
39

40
    ll cnt = 0;
41
    for (auto &[k, v]: mp)
42
        if (v > x)
43
            cnt++;
44

45
    cout << m - cnt << 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
}

C - 小红的因子幂和#

关键词：数学

思路#

考虑如何获取所有正因子，实际上直接暴力枚举所有因子，并插入 set 里就可以，set 同时自动去重并排序。

后面乘的过程同理，但注意快速幂开始一定要将底数 a 对 mod 取模，否则会溢出。

Code#

1
// Problem: 小红的因子幂和
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134529/C
4
// Time: 2026-05-10 19:15:54
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
using i128 = __int128;
21

22
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
23
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
24
const int inf = 0x3f3f3f3f;
25
const int N = 0;
26
const ll mod = 1e9 + 7;
27

28
map<ll, int> mp;
29

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

39
        a = (a * a) % mod;
40
        k >>= 1;
41
    }
42
    return res % mod;
43
}
44

45
void solve()
46
{
47
    ll x, y;
48
    cin >> x >> y;
49

50
    set<ll> s1, s2;
51

52
    for (ll i = 1; i <= x / i; i++)
53
    {
54
        if (x % i != 0)
55
            continue;
56

57
        s1.insert(i);
58
        s1.insert(x / i);
59
    }
60

61
    // cout << s1.size() << endl;
62

63
    for (ll i = 1; i <= y / i; i++)
64
    {
65
        if (y % i != 0)
66
            continue;
67

68
        s2.insert(i);
69
        s2.insert(y / i);
70
    }
71

72
    set<ll> f;
73
    for (auto t1: s1)
74
        for (auto t2: s2)
75
            f.insert(t1 * t2);
76

77
    ll res = 0;
78
    for (auto i: f)
79
        res = (res + qmi(i, i)) % mod;
80

81
    cout << res << endl;
82
}
83

84
int main()
85
{
86
    fastio();
87

88
    int T = 1;
89
    // cin >> T;
90

91
    while (T--)
92
        solve();
93

94
    return 0;
95
}

D - 小红的最佳区间#

关键词：思维，差分

思路#

我们需要做一步转化，需要将“给定区间与滑动区间相交”这个条件，转化成计算 L 的合法取值范围。

假设我们选择的区间是 $[L, L+k]$ ，给定的第 $i$ 个区间是 $[l_i, r_i]$ 。两个闭区间相交的充要条件是：它们的最大左端点，必须小于等于最小右端点，即 $\max(l_i, L) \le \min(r_i, L+k)$ 。

把这个不等式拆开，有 $L \le r_i$ ， $l_i \le L+k \implies L \ge l_i - k$ 。

综上，L满足的范围是 $l_i - k \le L \le r_i$ 。

现在问题转化为了：已知 $n$ 个新的区间 $[l_i - k, r_i]$ ，求坐标轴上的哪一个点（即 $L$ 的取值）被覆盖的次数最多。

使用 map 对原数组离散化，并作差分即可。

Code#

1
// Problem: 小红的最佳区间
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134529/D
4
// Time: 2026-05-10 19:59:49
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, k;
29
    cin >> n >> k;
30

31
    map<ll, int> mp;
32

33
    for (int i = 1; i <= n; i++)
34
    {
35
        ll l, r;
36
        cin >> l >> r;
37

38
        mp[l - k]++;
39
        mp[r + 1]--;
40
    }
41

42
    ll res = -1, tmp = 0;
43

44
    for (auto &[k, val]: mp)
45
    {
46
        tmp += val;
47
        if (tmp > res)
48
            res = tmp;
49
    }
50

51
    cout << res << endl;
52
}
53

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

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

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

64
    return 0;
65
}

E - 小红的好矩阵#

关键词：分类讨论，构造

思路#

首先考虑不可能修改到合法的情况：当 $2 \times n$ 不能被 $3$ 整除时，怎样修改都不合法。

要让一个 $2 \times n$ 的 01 矩阵合法（即所有 0 连通块和 1 连通块的大小都恰好为 3），我们可以从图形拼接的角度来推导其所有合法的形态。实际上可以枚举出 $6$ 种基本的图形块。

L型结构：

$S_0$ $S_{0}$ 组（左侧为0，右侧为1）：
- A1: 第一行 001，第二行 011
- B1: 第一行 011，第二行 001
$S_1$ $S_{1}$ 组（左侧为1，右侧为0）：
- A2: 第一行 110，第二行 100
- B2: 第一行 100，第二行 110

横条结构：

C1: 第一行 000，第二行 111
C2: 第一行 111，第二行 000

NOTE
赛时想到了分类讨论，但没有想到按左右侧分0和1讨论，还是思路不够清晰，实际上正常的讨论方式就是这样。

为了让相邻的 $2 \times 3$ 块拼在一起时，边界的连通块不会意外合并导致大小超过 3，只有以下四种相互独立的拼接模式是合法的：

模式 1：任意拼接 A1 和 B1：

由于 A1 和 B1 的左边界都是 0/0，右边界都是 1/1。它们拼接时必定是 1/1 贴着 0/0，0 和 1 不会合并。因此，整个序列的每一个 $2 \times 3$ 块都可以自由且独立地在 A1 和 B1 中二选一。

模式 2：任意拼接 A2 和 B2：

同理，左边界 1/1，右边界 0/0，每一个块都能在 A2 和 B2 中二选一。

模式 3：交替拼接 C1, C2, C1, C2...

因为 C1 会在右侧留下 0/1 的缺口，如果紧接 C1，就会导致 0 连通块合并为 6。因此它必须且只能接上 C2（左侧为 1/0）。

模式 4：交替拼接 C2, C1, C2, C1...

将原矩阵按 $2 \times 3$ 划分为 $k = n/3$ 个子块。对于第 $i$ 个子块，统计它变成 A1, B1, A2, B2, C1, C2 各需要修改多少次字符（即汉明距离）。然后分别计算将整个矩阵变为以上 4 个模式所需的最小总修改次数，取其中的最小值即为答案。

NOTE
关键在于拼接的时候，每个联通块不能互相干扰，否则就不满足题目的限制条件。
这样其实更好做了。

Code#

1
// Problem: 小红的好矩阵
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/134529/E
4
// Time: 2026-05-10 20:04:12
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
    string s[2];
32
    cin >> s[0] >> s[1];
33

34
    if (n % 3 != 0)
35
    {
36
        cout << "-1" << endl;
37
        return;
38
    }
39

40
    // 定义六种基本构成单位
41
    string A1[2] = {"001", "011"};
42
    string B1[2] = {"011", "001"};
43

44
    string A2[2] = {"110", "100"};
45
    string B2[2] = {"100", "110"};
46

47
    string C1[2] = {"000", "111"};
48
    string C2[2] = {"111", "000"};
49

50
    ll k1 = 0, k2 = 0, k3 = 0, k4 = 0;
51

52
    for (int i = 0; i < n / 3; i++)
53
    {
54
        int a1 = 0, b1 = 0, a2 = 0, b2 = 0, c1 = 0, c2 = 0;
55

56
        // 计算当前 2x3 的块变成 6 种基本块分别需要修改多少字符
57
        for (int r = 0; r < 2; r++)
58
            for (int c = 0; c < 3; c++)
59
            {
60
                char ch = s[r][i * 3 + c];
61
                if (ch != A1[r][c])
62
                    a1++;
63
                if (ch != B1[r][c])
64
                    b1++;
65
                if (ch != A2[r][c])
66
                    a2++;
67
                if (ch != B2[r][c])
68
                    b2++;
69
                if (ch != C1[r][c])
70
                    c1++;
71
                if (ch != C2[r][c])
72
                    c2++;
73
            }
74

75
        // 模式1和模式2是内部独立的，取最优即可
76
        k1 += min(a1, b1);
77
        k2 += min(a2, b2);
78

79
        // 长条块必须交替拼接
80
        if (i % 2 == 0)
81
            k3 += c1, k4 += c2;
82
        else
83
            k3 += c2, k4 += c1;
84
    }
85

86
    ll res = min({k1, k2, k3, k4});
87
    cout << res << endl;
88
}
89

90
int main()
91
{
92
    fastio();
93

94
    int T = 1;
95
    // cin >> T;
96

97
    while (T--)
98
        solve();
99

100
    return 0;
101
}