2025 YAC Round 1 题解

A 東方 Project 人気投票

出题人：MarisaMagic

题意简述

有 $n$ 个角色，次序编号从 $1 \sim n$ 。共 $m$ 个人参与投票，每个人投票情况用长度为 $n$ 的 ox 字符串表示，对于字符串第 k 个字符，若为 o 表示给第 k 个角色投了 $1$ 票，x 表示未投。按照角色获得票数从大到小排序（若票数相同，按角色次序编号从小到大排序）。

解题思路（结构体排序）

定义一个结构体，存储每个角色的名称 $name$ 、获得的票数 $score$ 以及次序编号 $id$ 。遍历每个人的投票情况，更新每个角色的票数，最后根据题意排序输出结果即可。

#include <bits/stdc++.h>
using namespace std;

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

struct node{
    string name; // 名称
    int score, id; // 票数、编号
};

void marisa(){
    int n; cin >> n;
    vector<node> a(n + 1);
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i].name, a[i].id = i;
    }

    int m; cin >> m;
    for(int i = 1; i <= m; i ++ ){
        string t; cin >> t;
        for(int j = 0; j < n; j ++ ) // 统计票数
            a[j + 1].score += (t[j] == 'o');
    } 
    // 先按照票数降序排序，若票数相同，按照编号升序排序
    sort(begin(a) + 1, end(a), [](node& x, node& y){
        if(x.score != y.score) return x.score > y.score;
        return x.id < y.id;
    });

    for(int i = 1; i <= n; i ++ ){
        cout << a[i].name << ' ' << a[i].score << "\n";
    }
}

int main(){
    ios;

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

    return 0;
}

B 恋色宝石

出题人：MarisaMagic

题意简述

给定一个长度为 $n$ 的序列 $a$ ，求 $\max_{1 \le i \le j \le n} \{ a_j - a_i \}$ 。

解题思路（动态规划，前缀最小值）

暴力的思路即从 $1 \le j \le n$ 枚举 $a_j$ ，对于当前的 $a_j$ 再枚举其前面所有位置的 $a_i$ （ $1 \le i \le j$ ）。对于每个 $a_j$ 枚举得到 $\max_{1 \le i \le j} \{ a_j - a_i \}$ ，最后求得这 $n$ 个 $\max_{1 \le i \le j} \{ a_j - a_i \}$ 最大值即为答案。

可以发现，对于每个 $a_j$ 来说， $\max_{1 \le i \le j} \{ a_j - a_i \}$ 的最优解 只会在前面最小的 $a_i$ 上取到，即 $\min_{1 \le i \le j}a_i$ 。

故我们不用在枚举 $a_j$ 之后再枚举 $a_i$ 。只需要在枚举 $a_j$ 时，边更新 前缀最小值，边更新答案。时间复杂度为 $\mathcal{O}(n)$ 。

#include <bits/stdc++.h>
using namespace std;

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

void marisa(){
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    int ans = 0, mn = 1e9; // 答案，前缀最小值
    for(int j = 1; j <= n; j ++ ){
        mn = min(mn, a[j]); // 更新前缀最小值
        ans = max(ans, a[j] - mn); // 更新答案
    }
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

C 上海？蓬莱？歌利亚！

出题人：MarisaMagic

题意简述

给定两个字符串 $p$ 和 $q$ ，取出 $p$ 的一个非空前缀和 $q$ 的一个非空后缀并前后连接得到一个字符串。按这种方式共可以得到 多少种 不同的字符串。

解题思路（字符串，模拟，乘法原理）

假设 $p$ 的长度为 $n$ ， $q$ 的长度为 $m$ 。取 $p$ 的非空前缀共有 $n$ 种方式，取 $q$ 的非空后缀共有 $m$ 种方式，显然，不考虑重复情况下可以构成 $n \times m$ 个字符串。接下来考虑去重。

假设有两个字符串分别为 “abc” 和 “dbc”，取前缀 “ab” 和后缀 “c” 与前缀 “a” 和后缀 “bc” 的所构成的字符串一样，均为 “abc”。假设有一个字符 $ch$ 同时在 $p$ 和 $q$ 中出现， $p$ 中 $ch$ 之前的非空前缀为 $p_{pre}$ ， $q$ 中 $ch$ 的非空后缀为 $q_{suf}$ 。可以发现取前缀 $p_{pre} + ch$ 和后缀 $q_{suf}$ 、前缀 $p_{pre}$ 和后缀 $ch + q_{suf}$ 两种情况重复了。

因此，我们需要统计每个字符分别在 $p$ 和 $q$ 中出现的次数，根据乘法原理，假设一个字符 $ch$ 在 $p$ 中出现了 $cnt_p$ 次，在 $q$ 中出现了 $cnt_q$ 次，那么这个字符 $ch$ 会造成的重复次数为 $cnt_p \times cnt_q$ 。

故只需要统计 $26$ 个字符分别在 $p$ 和 $q$ 中出现的次数，最后减去每个字符造成的重复次数即可。

需要注意的是，我们所取前缀和后缀必须是非空的。因此在统计 $p$ 中每个字符出现次数时，需要忽略第一个位置的字符；在统计 $q$ 中每个字符出现次数时，需要忽略最后一个位置的字符。

时间复杂度为 $\mathcal{O}(n + m)$ 。注意数据范围，需要开 long long。

#include <bits/stdc++.h>
using namespace std;

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

void marisa(){
    string p, q; cin >> p >> q;
    int n = p.size(), m = q.size();
    vector<int> cntp(26), cntq(26); // p 和 q 中每个字符出现次数
    for(int i = 1; i < n; i ++ ) cntp[p[i] - 'a'] ++ ;
    for(int i = 0; i < m - 1; i ++ ) cntq[q[i] - 'a'] ++ ; 
    ll ans = (ll)n * m;
    for(int i = 0; i < 26; i ++ ){
        ans -= (ll)cntp[i] * cntq[i]; // 减去重复次数
    }
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

D 弥林的防御布局

出题人：South_Orange

题意简述

判断一个点与已知三角形的位置关系。

解题思路（计算几何）

当给定点与三角形某个端点相同时，点在端点上

给定点 $p$ 在三角形的边上时，要求 $p$ 和线段 $v$ 的一个端点连边，和 $v$ 本身的夹角为 0，即 $p$ 在直线 $v$ 上，且 $p$ 和两端点形成平角，也就是说 $p$ 在两端点之间，点与线段的夹角可通过叉积判断。

给定点在三角形内部时，该点应在三角形的三个点形成的三个向量的同一侧，点与向量的位置关系可通过叉积判断。

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>

using ll = long long;

namespace Geo { ... } // 详情见附录
using namespace Geo;

int x[5], y[5];
Point<int> p[5];

void solve()
{
	char ch;
	for (int i = 1;i <= 4;i++)
	{
		cin >> ch >> x[i] >> ch >> y[i] >> ch;
		p[i] = { x[i],y[i] };
	}
	if (p[4] == p[1] || p[4] == p[2] || p[4] == p[3])
	{
		cout << 4 << '\n';
		return;
	}
	Line<int> l1(p[1], p[2]), l2(p[2], p[3]), l3(p[3], p[1]);
	
	//判断点与线的位置关系
	int f1 = point_line_relation(p[4], l1);
	int f2 = point_line_relation(p[4], l2);
	int f3 = point_line_relation(p[4], l3);
	//判断点是否在线段上
	int ff1 = point_segment_relation(p[4], l1);
	int ff2 = point_segment_relation(p[4], l2);
	int ff3 = point_segment_relation(p[4], l3);
	
	if (ff1 == 1 || ff2 == 1 || ff3 == 1) cout << 3 << '\n';
	else if (f1 == f2 && f2 == f3) cout << 1 << '\n'; // 若点在三个向量的同一侧则在三角形内
	else cout << 2 << '\n';
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

附录见 Geo.cpp，可作为基础二维计算几何模板进行参考学习。

其他做法可见 P1355 神秘大三角题解，主要采用海伦公式。

E 姆Q的魔导书

出题人：MarisaMagic

题意简述

给定一个可变序列 $a_1, a_2, \ldots, a_n$ ，有 $q$ 次操作，分为两种：

1 l r x：询问区间 $[l, r]$ 内数字 $x$ 的数量；
2 x：将 $1$ 个 $x$ 加入到序列的末尾。

解题思路（离散化，二分）

主席树（可持久化线段树）可以解决区间数字个数询问的问题，但是本题无需使用主席树。

初始序列长度和操作次数加起来最多 $3 \times 10^5$ ，故序列中数字种类数不超过 $3 \times 10^5$ 。考虑离散化存储每个数字出现的所有下标，可以通过 unordered_map<int, vector<int>> 来实现，其中 unordered_map 的键为数字，值为可变长数组，存储的是每个数字出现的下标。

对于操作 1 l r x：

由于存储的下标是递增的，故我们可以通过二分来查找范围。对于当前询问的数字 $x$ ，我们可以借助 lower_bound 找到 $x$ 所有下标中 第一个大于等于 $l$ 的下标位置 $p_l$ ，借助 upper_bound 找到 $x$ 所有下标中 最后一个大于 $r$ 的下标位置 $p_r$ 。最终 $[l, r]$ 区间内 $x$ 的个数即 $p_r - p_l$ 。
对于操作 2 x：

记录插入末尾下标 $idx$ ，每次插入将 $idx$ 插入到对应数字下标数组中。插入完成后 $idx += 1$ 。

#include <bits/stdc++.h>
using namespace std;

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

void marisa(){
    int n, q; cin >> n >> q;
    unordered_map<int, vector<int>> mp; // 存储每个数字下标
    for(int i = 1, x; i <= n; i ++ ){
        cin >> x;
        mp[x].push_back(i);
    }

    int idx = n;
    for(int i = 1, op, l, r, x; i <= q; i ++ ){
        cin >> op;
        if(op == 1){
            cin >> l >> r >> x;
            const auto& v = mp[x]; // 加引用，避免过多的拷贝导致超时
            int pl = lower_bound(begin(v), end(v), l) - begin(v);
            int pr = upper_bound(begin(v), end(v), r) - begin(v);
            cout << pr - pl << "\n";
        }else{
            cin >> x;
            mp[x].push_back( ++ idx);
        }
    }
}

int main(){
    ios;

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

    return 0;
}

F 橙

出题人：MarisaMagic

题意简述

给定一颗 $n$ 个节点的无向树，通过一条边需要 $1$ 单位时间，有 $m$ 个节点设有传送门， $m$ 个节点之间可瞬间互相传送。有 $q$ 次询问，每次询问两点通过所需最短时间。

解题思路（最近公共祖先 LCA，多源bfs）

如果 $m$ 为 $0$ ，可以先用倍增算法求最近公共祖先 LCA。预处理求得根节点到其他点距离 $d$ ，树上两点 $x, y$ 最短距离即 $d_x + d_y - 2 \times d_{anc}$ ，其中 $anc$ 为 $x, y$ 的最近公共祖先。

如果 $m$ 不为 $0$ ，那么可以选择从 $x$ 花费一段时间走到距离其最近的传送门 $trans_x$ ，瞬间传送到距离 $y$ 最近的传送门 $trans_y$ ，最后再花费一段时间从 $trans_y$ 走到 $y$ ，即 $x \rightarrow trans_x \rightarrow trans_y \rightarrow y$ 。此方案的答案即 $x$ 到最近传送门 $trans_x$ 的距离 + $y$ 到最近传送门 $trans_y$ 的距离

边都是双向的，只需要 多源01bfs 预处理每个传送门到达其他节点的最短距离 $dist$ 。最终每次询问 $x, y$ 的答案即 $\min{ (d_x + d_y - 2 \times d_{anc}， dist_x + dist_y) }$ 。

预处理 LCA 时间复杂度为 $\mathcal{O}(n\log{n})$ ，每次询问复杂度为 $\mathcal{O}(\log{n})$ 。总时间复杂度为 $\mathcal{O}((n + q)\log{n})$ 。

#include <bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int n, m, q;
vector<int> e[N];

// 倍增 lca 预处理点到点最短距离
int d[N], f[N][22];

void bfs(int src){
    queue<int> q;
    q.emplace(src);
    d[src] = 1;
    while(q.size()){
        int u = q.front();
        q.pop();
        for(const auto& v : e[u]){
            if(d[v]) continue;
            q.emplace(v);
            d[v] = d[u] + 1, f[v][0] = u;
            for(int k = 1; k <= 20; k ++ )
                f[v][k] = f[f[v][k - 1]][k - 1];
        }
    }
}

inline int lca(int a, int b){
    if(d[a] < d[b]) swap(a, b);
    for(int k = 20; ~k; k -- )
        if(d[f[a][k]] >= d[b]) a = f[a][k];
    if(a == b) return a;
    for(int k = 20; ~k; k -- )
        if(f[a][k] != f[b][k]) a = f[a][k], b = f[b][k];
    return f[a][0];
}

inline int get_d(int x, int y){
    return d[x] + d[y] - 2 * d[lca(x, y)];
}

// 多源 01 bfs 预处理最近传送门距离
int dist[N];
vector<int> trans;

void bfs01(){
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    for(const auto& x : trans){
        q.emplace(x);
        dist[x] = 0;
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        for(const auto& v : e[u]){
            if(dist[v] != inf) continue;
            q.emplace(v);
            dist[v] = dist[u] + 1;
        }
    }
}

void marisa(){
    cin >> n >> m >> q;
    for(int i = 1, u, v; i < n; i ++ ){
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    trans.resize(m);
    for(auto& x : trans) cin >> x; 

    bfs(1);
    bfs01();

    for(int i = 1, x, y; i <= q; i ++ ){
        cin >> x >> y;
        cout << min(get_d(x, y), dist[x] + dist[y]) << "\n";
    }
}

int main(){
    ios;

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

    return 0;
}

G 东方 × 地铁

出题人：MarisaMagic

题意简述

给定一个 $n \times m$ 的网格图，行从 $1 \sim n$ 编号，列从 $1 \sim m$ 编号，每个点可用所在行编号 $x$ 与所在列编号 $y$ 表示为 $(x, y)$ 。

点 $(i, j)$ 与 $(i, j + 1)$ 间连有一条权值为 $a_i$ 的边，其中 $1 \le i \le n, 1 \le j < m$ 。

点 $(i, j)$ 与 $(i + 1, j)$ 间连有一条权值为 $b_j$ 的边，其中 $1 \le i < n, 1 \le j \le m$ 。

求这个网格图的最小生成树。

解题思路（贪心，kruskal 算法思想）

如果强行建边用 kruskal 求最小生成树，边的数量达到 $O(n \times m)$ 级别，显然不可取。

但是，一行或一列中边的长度一样，不同长度的边最多 $n + m$ 种。我们可以仿照 $\text{kruskal}$ 求最小生成树的贪心思想，先分别对所有行边权 $a$ 和列边权 $b$ 进行从小到大排序，然后 贪心地选取边，并 维护生成树中不出现环。

我们可以先选取 所有行边权中最小的边权 $a_1$ ，然后全部加入到最小生成树；然后选取 所有列边权中最小的边权 $b_1$ ，也可以全部加入到最小生成树，并不会出现环。这一步加入到最小生成树的总长度为 $(m - 1) \times a_1 + (n - 1) \times b_1$ 。

对于接下来选取的行边权和列边权，我们每次对比当前的最小行边权与最小列边权的大小，谁更小先选谁。同时还要统计此前选取的行边权的个数 $cnt_r$ 和列边权的个数 $cnt_c$ 。

若当前最小行边权 $<$ 最小列边权：

可以发现这一行中已经有 $cnt_c$ 个点已经加入到最小生成树中。由于当前边权最小，我们需要尽可能多地选取这一行的边且保证不出现环。我们可以选择在 $cnt_c$ 个点中的每两个相邻点之间断开一条边，这样可以保证不会出现环。故我们当前这一行连的边条数为 $(m - cnt_c)$ 。

由于选择了一个行边权，因此还需要更新 $cnt_r += 1$ 。
若当前最小行边权 $\ge$ 最小列边权：

与上面同理，这一列有 $cnt_r$ 个点已经加入到最小生成树中。为了最小生成树总长度尽量小且保证不出现环，我们当前这一列连的边条数为 $(n - cnt_r)$ 即可。

同理，还需要更新 $cnt_c += 1$ 。

最后当总边数 $cnt = n \times m - 1$ 时退出循环。总时间复杂度为 $\mathcal{O}((n + m)\log{(n + m)})$ 。

#include <bits/stdc++.h>
using namespace std;

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

void marisa(){
    int n, m; cin >> n >> m;
    vector<ll> a(n + 1), b(m + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= m; i ++ ) cin >> b[i];
    sort(begin(a) + 1, end(a)); // 排序
    sort(begin(b) + 1, end(b));

    ll ans = a[1] * (m - 1) + b[1] * (n - 1); // 先选最小长度的行列边 
    ll cnt = n + m - 2, cnt_r = 1, cnt_c = 1; // 边总数，行边数，列边数 
    for(int i = 2, j = 2; cnt < (ll)n * m - 1; ){
        if(a[i] < b[j]){
            ans += a[i ++ ] * (m - cnt_c);
            cnt += m - cnt_c;
            cnt_r ++ ;
        }else{
            ans += b[j ++ ] * (n - cnt_r);
            cnt += n - cnt_r;
            cnt_c ++ ;
        }
    }
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

咏唱光芒 > YAC 扬州大学算法练习赛

#C++ #算法 #算法竞赛 #Luogu #YAC

2025 YAC Round 1 题解

https://marisamagic.github.io/2025/01/13/2025_YAC_1/

作者

MarisaMagic

发布于

2025年1月13日

许可协议

2025 YAC Round 2 题解上一篇

「C++ 多线程」信号量 counting_semaphore 与 binary_semaphore 下一篇

2025 YAC Round 1 题解

A 東方 Project 人気投票

题意简述

解题思路 （结构体排序）

B 恋色宝石

题意简述

解题思路 （动态规划，前缀最小值）

C 上海？蓬莱？歌利亚！

题意简述

解题思路 （字符串，模拟，乘法原理）

D 弥林的防御布局

题意简述

解题思路 （计算几何）

E 姆Q的魔导书

题意简述

解题思路 （离散化，二分）

F 橙

题意简述

解题思路 （最近公共祖先 LCA，多源bfs）

G 东方 × 地铁

题意简述

解题思路 （贪心，kruskal 算法思想）

解题思路（结构体排序）

解题思路（动态规划，前缀最小值）

解题思路（字符串，模拟，乘法原理）

解题思路（计算几何）

解题思路（离散化，二分）

解题思路（最近公共祖先 LCA，多源bfs）

解题思路（贪心，kruskal 算法思想）