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

A - 小红的字符串计数#

关键词：签到

Code#

1
// Problem: 小红的字符串计数
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136224/A
4
// Time: 2026-06-07 19:00:02
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

35
    int res = 0;
36
    for (auto [_, cnt]: mp)
37
        if (cnt == 1)
38
            res++;
39
    cout << res << endl;
40
}
41

42
int main()
43
{
44
    fastio();
45

46
    int T = 1;
47
    // cin >> T;
48

49
    while (T--)
50
        solve();
51

52
    return 0;
53
}

B - 小红打舞萌#

关键词：模拟

思路#

因为和别人一起玩的收益更好，我们尽可能选择和别人一起，所以最优的方案是：和朋友玩，自己玩，和朋友玩，自己玩，…

小红有 $x$ 枚游戏币，不管怎么选都要花 $5$ 个，所以可以将 $t = \lfloor \frac x 5 \rfloor$ 看作选择次数。

因此和朋友玩的次数最多是 $\lceil {\frac t 2} \rceil$ 。答案即为 $3x + \frac {x+1} 2$ 。

Code#

1
// Problem: 小红打舞萌
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136224/B
4
// Time: 2026-06-07 19:01:00
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 x;
29
    cin >> x;
30

31
    x /= 5;
32

33
    cout << 3 * x + (x + 1) / 2 << endl;
34
}
35

36
int main()
37
{
38
    fastio();
39

40
    int T = 1;
41
    // cin >> T;
42

43
    while (T--)
44
        solve();
45

46
    return 0;
47
}

C - 魔物76#

关键词：数学，差分

思路#

NOTE
注意题目的计算规则和 $abs$ 无关，赛时因为这个被卡了很久。

考虑使用类似差分的思想处理出 $b$ 数组，不难发现每次操作只会改变 $b$ 数组左右两侧的两个值，具体地，b[l]++, b[r + 1]--特别地， $l = 1$ 或 $r = n$ 时直接忽略操作。

Code#

1
// Problem: 魔物76
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136224/C
4
// Time: 2026-06-07 19:05:47
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, q;
29
    cin >> n >> q;
30

31
    vector<ll> a(n + 1), b(n + 2);
32
    for (int i = 1; i <= n; i++)
33
    {
34
        cin >> a[i];
35
        b[i] = a[i] - a[i - 1];
36
    }
37

38
    // for (int i = 1; i <= n; i++)
39
    // cout << b[i] << endl;
40

41
    ll sum = 0;
42
    for (int i = 2; i <= n; i++)
43
        sum += ((b[i] % 5 + 5) % 5);
44

45
    auto merge = [&](int idx, ll k) -> void
46
    {
47
        if (idx < 2 || idx > n)
48
            return;
49

50
        sum -= ((b[idx] % 5 + 5) % 5);
51

52
        b[idx] += k;
53

54
        sum += ((b[idx] % 5 + 5) % 5);
55
    };
56

57
    while (q--)
58
    {
59
        int l, r;
60
        cin >> l >> r;
61

62
        merge(l, 1);
63
        merge(r + 1, -1);
64

65
        cout << sum << endl;
66
    }
67
}
68

69
int main()
70
{
71
    fastio();
72

73
    int T = 1;
74
    // cin >> T;
75

76
    while (T--)
77
        solve();
78

79
    return 0;
80
}

D - 小红的子序列#

关键词：DP

思路#

暴力DP（50pts）#

设 $dp[i]$ 表示以第 $i$ 个数为结尾的最长合法子序列长度。

显然它会从所有能整除，并且整除后结果为质数的位置转移而来，需要注意的是，如果可以转移，我们需要标记每个位置的前驱来输出路径，并记录结尾位置。

关于质数，可以使用一个线性筛预处理出数组最大值以内所有的质数，这样的判断是 $O(1)$ 的。

但这样的时间复杂度是 $O(n^2)$ ，无法通过本题。

值域+反向枚举DP（100pts）#

对于当前位置 $i$ ，假设当前数为 $x=a_i$ ，如果某个前驱 $y$ 可以转移到 $x$ ，必须满足 $\frac x y = p$ ，其中 $p$ 是质数。

移项，得到 $y = \frac x p$ ，因此没有必要枚举前面所有位置 $j$ ，只需要枚举 $x$ 的所有不同质因数 $p$ ，合法前驱的数值一定是 $\frac x p$ 。

例如当前数为 $60$ ，质因数是 $2, 3, 5$ ，那么它只能接在 $30, 20, 12$ 后面，不需要检查其他数字。

我们还需要两个 $best$ 数组，定义：

1
best_len[x] = 已经扫描过的元素中，以数值 x 结尾的最长合法子序列长度
2
best_pos[x] = 对应子序列最后一个元素的下标

当扫描到 $a_i = x$ 时，枚举 $x$ 的不同质因数 $p$ ，寻找 $bestlen[x / p]$ 。

状态转移为：

$dp_i=\max\left(1,\max_{p\mid a_i,\ p\text{ 为质数}}\left(best\_len\left[\dfrac{a_i}{p}\right]+1\right)\right)$

计算完 $dp[i]$ 后，同步更新 $bestlen[a[i]]$ ， $bestpos[a[i]]$ 。

TIP
为什么只保存相同数值中的最优状态？
假设此前出现了多个值为 $6$ 的元素，后面出现一个 $18$ ，因为 $\frac {18} 6 = 3$ ，无论选择哪一个 $6$ ，都能够转移到 $18$ ，为了让最终序列最长，只需要保留此前所有值为 $6$ 的状态中，长度最大的那一个。

总结#

暴力的转移是：枚举此前的所有位置 $j$ ，并检查 $j$ 能否转移到 $i$ 。

优化后的转移是：根据 $a[i]$ 的数学性质，直接枚举可能成为前驱的数值，查询这些数值对应的历史最优状态。

Code#

暴力DP#

1
// Problem: 小红的子序列
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136224/D
4
// Time: 2026-06-07 19:34:40
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 = 1e6 + 10;
25

26
vector<int> primes;
27
int cnt;
28
bool st[N];
29

30
void get_primes(int n)
31
{
32
    for (int i = 2; i <= n; i++)
33
    {
34
        if (!st[i])
35
            primes.push_back(i), cnt++;
36

37
        for (int j = 0; j < cnt && primes[j] <= n / i; j++)
38
        {
39
            st[primes[j] * i] = true;
40

41
            if (i % primes[j] == 0)
42
                break;
43
        }
44
    }
45
}
46

47
void solve()
48
{
49
    int n;
50
    cin >> n;
51

52
    vector<int> a(n + 1, 1), b(n + 1, -1), path;
53
    for (int i = 1; i <= n; i++)
54
        cin >> a[i];
55

56
    get_primes(*max_element(all(a)));
57

58
    vector<int> dp(n + 1, 1);
59
    int res = 0, end = 0;
60
    for (int i = 1; i <= n; i++)
61
    {
62
        for (int j = 1; j < i; j++)
63
        {
64
            if (a[i] % a[j] != 0)
65
                continue;
66

67
            int t = a[i] / a[j];
68
            if (!st[t])
69
            {
70
                if (dp[j] + 1 > dp[i])
71
                {
72
                    dp[i] = dp[j] + 1;
73
                    b[i] = j;
74
                }
75
            }
76
        }
77
        if (dp[i] > res)
78
        {
79
            res = dp[i];
80
            end = i;
81
        }
82
    }
83

84
    for (int i = end; i != -1; i = b[i])
85
        path.push_back(a[i]);
86

87
    reverse(all(path));
88

89
    cout << res << endl;
90
    for (auto x: path)
91
        cout << x << " ";
92
}
93

94
int main()
95
{
96
    fastio();
97

98
    int T = 1;
99
    // cin >> T;
100

101
    while (T--)
102
        solve();
103

104
    return 0;
105
}

正解#

NOTE
注意：线性筛过程中每次构造出一个合数，都必须立刻记录。

1
// Problem: 小红的子序列
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136224/D
4
// Time: 2026-06-07 19:34:40
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 = 1e6 + 10;
25

26
vector<int> primes;
27
int cnt, minp[N];
28
bool st[N];
29

30
void get_primes(int n)
31
{
32
    for (int i = 2; i <= n; i++)
33
    {
34
        if (!st[i])
35
        {
36
            primes.push_back(i);
37
            cnt++;
38
            minp[i] = i;
39
        }
40

41
        for (int j = 0; j < cnt && primes[j] <= n / i; j++)
42
        {
43
            st[primes[j] * i] = true;
44

45
            minp[primes[j] * i] = primes[j];
46

47
            if (i % primes[j] == 0)
48
                break;
49
        }
50
    }
51
}
52

53
void solve()
54
{
55
    int n;
56
    cin >> n;
57

58
    vector<int> a(n + 1), path;
59
    for (int i = 1; i <= n; i++)
60
        cin >> a[i];
61

62
    int mx = *max_element(all(a));
63
    get_primes(mx);
64

65
    vector<int> dp(n + 1, 1), pre(n + 1, -1);
66
    vector<int> blen(mx + 1, 0), bpos(mx + 1, -1);
67

68
    int res = 0, end = 0;
69

70
    for (int i = 1; i <= n; i++)
71
    {
72
        int x = a[i];
73

74
        while (x > 1)
75
        {
76
            int p = minp[x];
77

78
            int idx = a[i] / p;
79

80
            if (blen[idx] + 1 > dp[i])
81
            {
82
                dp[i] = blen[idx] + 1;
83
                pre[i] = bpos[idx];
84
            }
85

86
            while (x % p == 0)
87
                x /= p;
88
        }
89

90
        if (dp[i] > blen[a[i]])
91
        {
92
            blen[a[i]] = dp[i];
93
            bpos[a[i]] = i;
94
        }
95

96
        if (dp[i] > res)
97
        {
98
            res = dp[i];
99
            end = i;
100
        }
101
    }
102

103
    for (int i = end; i != -1; i = pre[i])
104
        path.push_back(a[i]);
105

106
    reverse(all(path));
107

108
    cout << res << endl;
109

110
    for (auto x: path)
111
        cout << x << " ";
112
}
113

114
int main()
115
{
116
    fastio();
117

118
    int T = 1;
119
    // cin >> T;
120

121
    while (T--)
122
        solve();
123

124
    return 0;
125
}

E - 小红的受欢迎子串#

关键词：前后缀，预处理

之前做过的一道类似题目：牛客小白月赛 133 - C

和那道题不同的是，那题是修改字符，这题是插入字符。

思路#

首先明确一个性质：能够重复利用的字符一定是连续的。

考虑 $greet$ ，假设我们希望使用原字符串中的一部分字符，剩下的通过插入来补齐。如果原字符串是 $get$ ，由于它是 $greet$ 的子序列，因此是可行的。但如果原字符串是 $g \cdots x \cdots t$ ，就不能利用它，将它补成 $greet$ ，因为字符 $x$ 无法被删除或修改。

因此对于某个目标字符串，可以复用的原字符串部分必须是一个连续子串，并且该子串必须是目标字符串的子序列。

并且两个字符串 $great$ 和 $invite$ 无法拼接，因此两个目标子串一定互不重叠，且只有两种排列方式。

如果完全不复用原字符串中的字符，直接插入两个完整字符串，需要 $11$ 次操作，因此我们要求最多可复用的字符数。

问题转化为：从原字符串中选择两个互不重叠的连续片段，使其中一个是 $greet$ 的子序列，另一个是 $invite$ 的子序列，最大化两个片段的长度之和。

我们对两个目标字符串都预处理出前后缀的最大值：

1
pre[i] = 仅使用 s[0 ... i - 1] 时，最多可以复用多少个字符
2
suf[i] = 仅使用 s[i ... n - 1] 时，最多可以复用多少个字符

由于两个字符串的长度都比较短，直接在每个位置上双指针扫一遍即可。

枚举所有分界线，取两种拼接方式的最大值。

Code#

1
// Problem: 小红的受欢迎子串
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/136224/E
4
// Time: 2026-06-07 19:50:19
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
    string s;
30

31
    cin >> n >> s;
32

33
    auto calc = [&](string p)
34
    {
35
        int m = p.size();
36

37
        // st[i]：从位置 i 开始的合法片段最大长度
38
        // ed[i]：在位置 i 结束的合法片段最大长度
39
        // pre[i]：在前 i 个字符中，合法片段最大长度
40
        // suf[i]：在第 i 个字符到末尾，合法片段最大长度
41

42
        vector<int> st(n + 2), ed(n + 2), pre(n + 2), suf(n + 3);
43

44
        // 枚举复用片段的左端点
45
        for (int l = 0; l < n; l++)
46
        {
47
            int pos = 0;
48

49
            // 复用片段的长度不会超过目标串长度
50
            for (int r = l; r < n && r < l + m; r++)
51
            {
52
                // 在目标串 p 中寻找与 s[r] 匹配的位置
53
                while (pos < m && p[pos] != s[r])
54
                    pos++;
55

56
                // 当前字符无法匹配，直接break
57
                if (pos == m)
58
                    break;
59

60
                pos++;
61

62
                int len = r - l + 1;
63

64
                // 注意换下标，字符串下标从0开始，数组从1开始
65
                st[l + 1] = max(st[l + 1], len);
66
                ed[r + 1] = max(ed[r + 1], len);
67
            }
68
        }
69

70
        // 前缀最优值
71
        for (int i = 1; i <= n; ++i)
72
            pre[i] = max(pre[i - 1], ed[i]);
73

74
        // 后缀最优值
75
        for (int i = n; i >= 1; i--)
76
            suf[i] = max(suf[i + 1], st[i]);
77

78
        return make_pair(pre, suf);
79
    };
80

81
    string a = "greet", b = "invite";
82

83
    auto [pa, sa] = calc(a);
84
    auto [pb, sb] = calc(b);
85

86
    int mx = 0;
87

88
    // 枚举分割点，将字符串划分为 s[1 ... i] | s[i + 1 ... n]
89
    for (int i = 0; i <= n; i++)
90
    {
91
        mx = max(mx, pa[i] + sb[i + 1]);
92
        mx = max(mx, pb[i] + sa[i + 1]);
93
    }
94

95
    cout << a.size() + b.size() - mx << endl;
96
}
97

98
int main()
99
{
100
    fastio();
101

102
    int T = 1;
103
    // cin >> T;
104

105
    while (T--)
106
        solve();
107

108
    return 0;
109
}

A - 小红的字符串计数#

Code#

B - 小红打舞萌#

思路#

Code#

C - 魔物76#

思路#

Code#

D - 小红的子序列#

思路#

暴力DP（50pts）#

值域+反向枚举DP（100pts）#

总结#

Code#

暴力DP#

正解#

E - 小红的受欢迎子串#

思路#

Code#

评论