2025 YAC Round 6 题解

比赛大图来源：pixiv_id=105287025

A 哇，喜羊羊！

出题人：MarisaMagic

题意简述

给定一个字符串 SS，去除所有字符 33 输出新的字符串 S′S^{'}。

解题思路 （语法，字符串基础）

遍历每个字符，遇到 33 直接忽略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)

void marisa(){
    string s; cin >> s;
    for(const auto& ch : s) if(ch != '3') cout << ch;
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ) marisa();
    
    return 0;
}

B 咲夜的小学数学题

出题人：MarisaMagic

题意简述

无限个 22 和 33，询问正整数 xx 是否可以表示为 2×a+3×b2\times a + 3\times b。

解题思路 （数学）

结论：除 11 之外的正整数都可以表示为 2×a+3×b2\times a + 3\times b：

  • 当 x=1x = 1 时，我们无法表示为 2×a+3×b2\times a + 3\times b 的形式。
  • 当正整数 xx 为偶数时，我们一定可以表示为 2×x2+3×02 \times \frac{x}{2} + 3 \times 0。
  • 当正整数 xx 为大于 11 的奇数时，我们一定可以表示为 2×x−32+3×12 \times \frac{x - 3}{2} + 3 \times 1。

以上通过 构造 的方式得出结论，我们也可以采用 数学归纳法 进行证明：

显然，有基础结论：正整数 22 可以用一个 22 表示；正整数 33 可以用一个 33 表示。

假设 2≤x≤k2 \le x \le k 的所有正整数都可以被表示为 2×a+3×b2\times a + 3\times b，试证明 k+1k + 1 也可以表示为 2×a+3×b2\times a + 3\times b 的形式。

根据假设，k−1k - 1 表示为 2×a′+3×b′2\times a^{'} + 3\times b^{'}，那么 k+1k + 1 可以表示为 2×(a′+1)+3×b′2\times (a^{'} + 1) + 3\times b^{'}。故 k+1k + 1 也可以表示为 2×a+3×b2\times a + 3\times b 的形式得证。以此类推，任意大于等于 22 的正整数都可以被表示为 2×a+3×b2\times a + 3\times b 的形式。

拓展结论：对于两个 互质 的正整数 xx 和 yy，其最大的不能凑出的整数为 x×y−x−yx \times y - x - y。

此拓展结论是一个非常经典的结论，题目可见 P3951 [NOIP 2017 提高组] 小凯的疑惑。证明可参考 两个互质的正整数不能凑出的最大数的证明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)
using ll = long long;

int main(){
    fastio;

    int T = 1; cin >> T;
    while(T -- ){
        ll x; cin >> x;
        cout << (x == 1 ? "No" : "Yes") << "\n";    
    }
    
    return 0;
}

C 完美潇洒的女仆长

出题人：MarisaMagic

题意简述

给定一个 0101 字符串，求最少插入多少个字符使得相邻字符都不同。

解题思路 （双指针、贪心）

对于连续相同的一段 kk 个字符，只需要插入 k−1k - 1 个另一种字符即可使得相邻字符都不同。故双指针遍历字符串，维护连续相同一段的前后边界 [l,r)[l, r)，每一段对答案的贡献为 r−l−1r - l - 1，累加答案即可。时间复杂度 O(n)\mathcal{O}(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)

void marisa(){
    int n; cin >> n;
    string s; cin >> s;
    int l = 0, r, ans = 0;
    while(l < n){
        r = l + 1;
        while(r < n && s[r] == s[l]) r ++ ;
        ans += r - l - 1;
        l = r;
    }
    cout << ans << "\n";
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ) marisa();
    
    return 0;
}

D 冬天的遗忘之物

出题人：MarisaMagic

题意简述

有一个 n×mn\times m 的矩阵 AA，已知 Ai,jA_{i,j} 是 ii 和 jj 的公倍数，求：∀x∈[1,K]\forall x \in [1, K]，矩阵 AA 最多有多少元素可以是 xx。（各结果之间相互独立）

解题思路 （数学、调和级数）

由元素 Ai,jA_{i,j} 是 ii 和 jj 的公倍数，可知 ii 和 jj 都是 Ai,jA_{i,j} 的约数，即 Ai,j mod i=0A_{i,j} \bmod i = 0，Ai,j mod j=0A_{i,j} \bmod j = 0。

记矩阵 AA 中最多有多少元素可以是 xx 为 ansxans_x。我们计算行下标 1≤i≤n1 \le i \le n 中有多少数是 xx 的约数 和 列下标 1≤j≤m1 \le j \le m 中有多少数是 xx 的约数，分别记为 cntnxcntn_x 和 cntmxcntm_x。由乘法原理可知 ansxans_x 等于 cntnx×cntmxcntn_x \times cntm_x。

一种 O(KK)\mathcal{O}(K\sqrt{K}) 的 TLE\text{TLE} 做法是：O(K)\mathcal{O}(\sqrt{K})预处理出每个 xx （1≤x≤K1 \le x \le K）的所有约数，对于每个 xx 其约数存到一个数组中，然后对于每个 xx 分别二分找到约数序列中第一个大于 nn 和第一个大于 mm 的位置，即可求出 cntnxcntn_x 和 cntmxcntm_x。

考虑换一种思路统计每个 xx 的约数个数。我们可以枚举约数 ii，然后对于每个约数 ii 枚举其倍数 j=i,2×i,3×i,…...j = i, 2\times i, 3\times i, \ldots... 直到边界 KK，这些 jj 都有约数 ii。因此，我们可以从 1≤i≤n1 \le i \le n 枚举约数，再枚举其倍数 jj 更新其约数个数 cntjcnt_j，大致写法如下：

1
2
3
4
5
for(int i = 1; i <= n; i ++ ){
    for(int j = i; j <= K; j += i){
        cnt[j] ++ ;
    }
}

上述过程的时间复杂度为 ∑i=1nKi\sum_{i=1}^{n} \frac{K}{i}，即 K∑i=1n1iK\sum_{i=1}^{n}\frac{1}{i}。其中 ∑i=1n1i\sum_{i=1}^{n} \frac{1}{i} 的部分为 调和级数，调和级数 发散且其增长速度与 ln⁡n\ln n 同阶（证明可参考 调和级数既然是发散的，那么就是无穷大量了，它发散的快吗？什么级别的？）。因此，这种统计每个 xx 的约数个数的过程时间复杂度为 O(Kln⁡n)=O(Klog⁡n)\mathcal{O}(K\ln n) = \mathcal{O}(K \log n)。

故我们只需要用此方式分别更新并统计 cntncntn 和 cntmcntm，最后从 1≤x≤K1 \le x \le K 累加一下答案。时间复杂度为 O(Klog⁡n+Klog⁡m)\mathcal{O}(K\log n + K\log m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)
using ll = long long;

void marisa(){
    int n, m, K; cin >> n >> m >> K;
    vector<int> cntn(K + 1), cntm(K + 1);
    for(int i = 1; i <= n; i ++ ){ // 枚举行下标约数
        for(int j = i; j <= K; j += i){
            cntn[j] ++ ;
        }
    }
    for(int i = 1; i <= m; i ++ ){ // 枚举列下标约数
        for(int j = i; j <= K; j += i){
            cntm[j] ++ ;
        }
    }
    ll ans = 0;
    for(int x = 1; x <= K; x ++ ){
        ans += (ll)x * cntn[x] * cntm[x]; 
    }
    cout << ans << "\n";
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ) marisa();
    
    return 0;
}

E 猫头鹰与蝙蝠

出题人：MarisaMagic

题意简述

神子有一棵 nn 个节点的树，树上的边有开启和关闭两种状态。初始情况下，神子在 11 号节点，所有的边开启。

每轮的具体环节如下：

  1. 神子当前位于节点 uu。如果 uu 度数为 11，那么 神子获胜。否则，进入第 22 个环节；
  2. 蕾咪会关闭一条树上的边（被关闭的边不会再开启），然后进入第 33 个环节。如果没有剩余的边可以关闭，直接进入第 33 个环节；
  3. 神子选择一条连接 uu 的 开启 的边，移动到一个相邻的节点上。 如果没有这样的边，那么 蕾咪获胜。 否则，回到第 11 个环节进行下一轮。

神子和蕾咪都会以最优策略执行每一个环节。判断谁会获胜。

解题思路 （树的遍历，dfs）

自底向上考虑这个问题。从 11 向下遍历，假设当前走到节点 uu：

  • 如果节点 uu 是叶子节点（度数为 11），那么神子直接获胜，我们定义 uu 为 必胜节点（子树）；

  • 如果节点 uu 不是叶子节点，我们需要判断其有多少个儿子节点 vv 是 必胜节点（子树）：

    • 如果 uu 有 大于等于 22 个节点（子树）是 必胜节点（子树），那么蕾咪关闭任意一条连接了某一个必胜节点的边 (u,v)(u, v)，神子可以选择除这条边之外的其他邻接边到达另一个必胜节点（子树）。故此 uu 也为必胜节点（子树）；
    • 否则，蕾咪关闭仅存的一条到达必胜节点的边（或者本来就没有必胜节点可以到达），故此 uu 是必败节点（子树）。

我们可以通过 dfs 遍历整个树，如果当前遍历到的 uu 是叶子节点或者包含 大于等于 22 个必胜节点（子树），那么 uu 也是必胜节点（子树）。最终，若根节点 11 是必胜节点（子树），那么神子一定获胜；否则，蕾咪一定获胜。时间复杂度 O(n)\mathcal{O}(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)

void marisa(){
    int n; cin >> n;
    vector<vector<int>> e(n + 1);
    vector<int> d(n + 1);
    for(int i = 1, u, v; i < n; i ++ ){
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
        d[u] ++ , d[v] ++ ;
    }
    function<bool(int, int)> dfs = [&](int u, int fa){
        if(d[u] == 1) return true; // 叶子节点必胜
        int cnt = 0;
        for(const auto& v : e[u]){
            if(v == fa) continue;
            cnt += dfs(v, u); // 必胜的子树
        }
        return cnt >= 2; // 有大于等于2个必胜子树
    };
    cout << (dfs(1, 0) ? "You win, temporarily." : "Wasted.") << "\n";
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ) marisa();
    
    return 0;
}

F 香霖堂卖画框了

出题人：MarisaMagic

题意简述

两种画框 a,ba, b，每种有 nn 个，每个画框有 pp 和 hh 两个属性。第一排放 nn 个画框 aa，属性记为 pa,hapa, ha；第二排放 nn 个画框 bb，属性记为 pb,hbpb, hb，将这些画框进行重排要求满足：

  • 画框 aa 从左到右 pa1,pa2,…,panpa_1, pa_2, \ldots, pa_n 单调不减；
  • 画框 bb 从左到右 pb1,pb2,…,pbnpb_1, pb_2, \ldots, pb_n 单调不减；
  • ∀i∈[1,n]\forall i \in [1, n]，有 hai>hbiha_i > hb_i。

求一种方案输出第一排和第二排的编号排列 或 输出无解。

解题思路 （贪心，模拟）

考虑贪心。对于每一种画框，将价格 pp 相同的画框划分到一个集合 set 中，集合 set 中存储一对高度和编号 (hid,id)(h_{id}, id)。为了保证价格从低到高，我们可以将价格 pp 作为键，集合 set 作为值将每种画框存储到 map<int, set<pair<int, int>>> 的数据结构中。存储画框 aa 的数据结构记为 mpamp_a，存储画框 bb 的数据结构记为 mpbmp_b。

同时遍历 mpamp_a 和 mpbmp_b，从各自最低价格开始。记当前 mpamp_a 最低价的画框集合为 stast_a，当前 mpbmp_b 最低价的画框集合为 stbst_b。

  • 若 stast_a 中画框数量 大于等于 stbst_b 中画框数量：

    为了 让后续价格保持单调不减，并且 尽可能多地使得后续满足对应位置有 hai>hbiha_i > hb_i，我们需要为较小数量的 stbst_b 中的每个画框 (hbid,id)(hb_{id}, id) 在 stast_a 中找到一个 最小的严格大于 hbidhb_{id} 的画框。

    如果可以找到，将对应编号加入到答案中并删除 stast_a 中的画框；否则，直接输出无解。若每个 stbst_b 的画框都可以找到，mpbmp_b 转到下一个价格的画框 bb 继续进行遍历。特别的，如果 stast_a 和 stbst_b 相等时，stast_a 也都分配到一个画框 bb 上，mpamp_a 也需要转到下一个价格的画框 aa 继续进行遍历。

  • 若 stast_a 中画框数量 小于 stbst_b 中画框数量：

    此时需要为较小数量的 stast_a 中的每个画框 (haid,id)(ha_{id}, id) 在 stbst_b 中找到一个 最大的严格小于 haidha_{id} 的画框。

    如果可以找到，将对应编号放入答案并删除 stbst_b 中的画框；否则，直接输出无解。若每个 stast_a 的画框都可以找到，mpamp_a 转到下一个价格的画框 aa 继续进行遍历。

不断模拟上述过程，直到最后全部遍历完分别输出编号排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using pii = pair<int, int>;

void marisa(){
    int n; cin >> n;
    map<int, set<pii>> mpa, mpb;
    vector<int> pa(n + 1), ha(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> pa[i];
    for(int i = 1; i <= n; i ++ ) cin >> ha[i];
    for(int i = 1; i <= n; i ++ ){
        mpa[pa[i]].insert(pii{ha[i], i});
    }
    vector<int> pb(n + 1), hb(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> pb[i];
    for(int i = 1; i <= n; i ++ ) cin >> hb[i];
    for(int i = 1; i <= n; i ++ ){
        mpb[pb[i]].insert(pii{hb[i], i});
    }
    vector<int> ansa, ansb; // 答案编号排列
    auto ita = mpa.begin(), itb = mpb.begin();
    while(ita != mpa.end() && itb != mpb.end()){
        auto& [_a, sta] = *ita;
        auto& [_b, stb] = *itb;
        if(sta.size() >= stb.size()){
            bool flag = (sta.size() == stb.size());
            for(auto& [x, id] : stb){
                // 找到最小的严格大于 x 的画框 a
                auto it = sta.lower_bound(pii{x + 1, 0}); 
                if(it == sta.end()){
                    cout << "impossible" << "\n";
                    return;
                }
                ansa.emplace_back(it -> second); // 放入编号
                ansb.emplace_back(id);
                sta.erase(it);
            }
            itb ++ ; // 转到下一个价格的画框 b
            if(flag) ita ++ ; 
        }else{
            for(auto& [x, id] : sta){
                // 找到最大的严格小于 x 的画框 b
                auto it = stb.lower_bound(pii{x, 0}); 
                if(it == stb.begin()){
                    cout << "impossible" << "\n";
                    return;
                }
                it -- ;
                ansa.emplace_back(id); // 放入编号
                ansb.emplace_back(it -> second);
                stb.erase(it);
            }
            ita ++ ; // 转到下一个价格的画框 a
        }
    }
    // 输出答案排列
    for(const auto& x : ansa) cout << x << ' ';
    cout << "\n";
    for(const auto& x : ansb) cout << x << ' ';
    cout << "\n";
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}
咏唱光芒 > YAC 扬州大学算法练习赛
#C++ #算法 #算法竞赛 #Luogu #YAC
2025 YAC Round 6 题解
https://marisamagic.github.io/2025/03/23/2025_YAC_6/
作者
MarisaMagic
发布于
2025年3月23日
许可协议