NOTE
比赛链接：牛客小白月赛 133

A - 愿望魔镜：真名的倒影#

关键词：签到

Code#

1
// Problem: 愿望魔镜：真名的倒影
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/135365/A
4
// Time: 2026-05-29 19:14: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
    string s;
29
    cin >> s;
30

31
    if (s == "awdec")
32
    {
33
        cout << "Fantasy_Blue" << endl;
34
        return;
35
    }
36
    if (s == "Fantasy_Blue")
37
    {
38
        cout << "awdec" << endl;
39
        return;
40
    }
41
    cout << "other" << 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
}

B - 桃夭：花树的高度博弈#

关键词：思维

思路#

先手希望最后排列的最长上升子序列长度尽可能大，后手希望尽可能小，考虑他们的最优策略是什么。

先手的最优策略：每次选择当前最靠左的空位置，放当前最小的剩余高度，他至少能保证结果为 $\lfloor n / 2 \rfloor + 1$ ；

后手的最优策略：每次选择当前最靠左的空位置，放当前最大的剩余高度，因为他放的是最大剩余高度，所以之后所有树的高度都更小。如果一个排列可以被划分成 $k$ 个下降子序列，那么它的 LIS 长度最多是 $k$ 。

可以发现上下界均为 $\lfloor n / 2 \rfloor + 1$ ，即为答案。

Code#

1
// Problem: 桃夭：花树的高度博弈
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/135365/B
4
// Time: 2026-05-29 19:16:33
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
    if (n % 2)
32
        cout << (n + 1) / 2 << endl;
33
    else
34
        cout << n / 2 + 1 << endl;
35
}
36

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

41
    int T = 1;
42
    cin >> T;
43

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

47
    return 0;
48
}

C - 魔法少女：愿望卷轴与真名刻印#

关键词：模拟，预处理

思路#

两个目标子串在原串中必须相互独立，互不重叠。我们可以考虑预处理出对于每个索引 $i$ ，在 $i$ 位置处生成 Fantasy_Blue 和 awdec 需要多少代价。

然后我们需要找两个不重叠的起点 $i, j$ 来计算答案。如果直接双重循环找两个不重叠的起点 $i$ 和 $j$ ，时间复杂度是 $O(N^2)$ ，对于 $N \le 10^5$ 会超时。

我们需要找的是无交集的两段。有两种情况：

Fantasy_Blue 在前，awdec 在后。
awdec 在前，Fantasy_Blue 在后。

我们可以维护一个后缀最小值。比如第一种情况：当我们遍历 awdec 的起点 $j$ 时，Fantasy_Blue 的合法起点 $i$ 必须满足 $i + 11 < j$ 。我们只需要在遍历 $j$ 的过程中，动态记录当前所有合法的 $i$ 中， $cost1[i]$ 的最小值即可。将这个最小值加上 $cost2[j]$ ，就是当前划分下的最小总代价。两种情况取最小值，最后判断是否 $\le k$ 即可。

Code#

1
// Problem: 魔法少女：愿望卷轴与真名刻印
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/135365/C
4
// Time: 2026-05-29 19:20:54
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 debug(auto &f, auto &a)
27
{
28
    for (auto &x: f)
29
        cout << x << " ";
30
    cout << endl;
31

32
    for (auto &x: a)
33
        cout << x << " ";
34
    cout << endl;
35

36
    cout << endl;
37
}
38

39
void solve()
40
{
41
    int n, k;
42
    cin >> n >> k;
43

44
    string s1 = "Fantasy_Blue", s2 = "awdec", s;
45
    cin >> s;
46

47
    int l1 = s1.size(), l2 = s2.size();
48

49
    if (l1 + l2 > n)
50
    {
51
        cout << "No" << endl;
52
        return;
53
    }
54

55
    vector<int> f(n + 5, inf), a(n + 5, inf);
56

57
    for (int i = 0; i <= n - l1; i++)
58
    {
59
        int res = 0;
60
        for (int j = 0; j < l1; j++)
61
        {
62
            if (s[i + j] != s1[j])
63
                res++;
64
        }
65
        f[i] = res;
66
    }
67

68
    for (int i = 0; i <= n - l2; i++)
69
    {
70
        int res = 0;
71
        for (int j = 0; j < l2; j++)
72
        {
73
            if (s[i + j] != s2[j])
74
                res++;
75
        }
76
        a[i] = res;
77
    }
78

79
    vector<int> suff(n + 5, inf), sufa(n + 5, inf);
80
    for (int i = n - l1; i >= 0; i--)
81
        suff[i] = min(suff[i + 1], f[i]);
82
    for (int i = n - l2; i >= 0; i--)
83
        sufa[i] = min(sufa[i + 1], a[i]);
84

85
    int res = inf;
86
    for (int i = 0; i <= n - l1; i++)
87
        if (i + l1 <= n)
88
            res = min(res, f[i] + sufa[i + l1]);
89

90
    for (int i = 0; i <= n - l2; i++)
91
        if (i + l2 <= n)
92
            res = min(res, a[i] + suff[i + l2]);
93

94
    cout << (res <= k ? "Yes" : "No") << endl;
95
}
96

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

101
    int T = 1;
102
    cin >> T;
103

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

107
    return 0;
108
}

D - 魔力共鸣：最小公倍数的融合#

关键词：数学

思路#

一次操作会把两个数变成它们的最小公倍数。最终每个元素其实都是原数组某个子集的 $\operatorname{lcm}$ ，目标是让最终所有元素的 $\gcd\neq 1$ 。

这意味着：最终所有元素都至少有一个共同质因子 $p$ 。

假设某个质因子 $p$ 在原数组中出现于 $cnt_p$ 个数里面，也就是说，有 $cnt_p$ 个数能被 $p$ 整除，那么最终最多可以保留 $cnt_p$ 个元素。因为每个最终元素都必须含有质因子 $p$ ，而一个最终元素的 $\operatorname{lcm}$ 想含有 $p$ ，它对应的原始集合里必须至少有一个数能被 $p$ 整除。

所以最终最多元素的个数等于所有 $cnt_p$ 可能取值的最大值，最少操作次数为 $n-maxcnt$ 。

如果所有数都是 $1$ ，没有质因子，答案就是 $-1$ 。

Code#

1
// Problem: 魔力共鸣：最小公倍数的融合
2
// Contest: NowCoder
3
// URL: https://ac.nowcoder.com/acm/contest/135365/D
4
// Time: 2026-05-29 19:49: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
bool is_prime(int x)
27
{
28
    for (int i = 2; i * i <= x; i++)
29
        if (x % i == 0)
30
            return false;
31
    return true;
32
}
33

34
void solve()
35
{
36
    int n;
37
    cin >> n;
38

39
    map<int, int> mp;
40

41
    auto divide = [&](int x) -> void
42
    {
43
        for (int i = 2; i * i <= x; i++)
44
        {
45
            if (x % i == 0)
46
                mp[i]++;
47
            while (x % i == 0)
48
                x /= i;
49
        }
50
        if (x > 1)
51
            mp[x]++;
52
    };
53

54
    int res = 0;
55
    for (int i = 0, x; i < n; i++)
56
    {
57
        cin >> x;
58
        divide(x);
59
    }
60
    for (auto &[_, cnt]: mp)
61
        res = max(res, cnt);
62

63
    cout << (res == 0 ? -1 : n - res) << endl;
64
}
65

66
int main()
67
{
68
    fastio();
69

70
    int T = 1;
71
    cin >> T;
72

73
    while (T--)
74
        solve();
75

76
    return 0;
77
}