2025 YAC Round 2 题解

A 瓦雷利亚的失落符文

出题人：South_Orange

题意简述

给定一个含未知字符的长度为 9 的字符串，未知字符用 * 表示（不含引号）。下面给出 $n$ 个长度为 9 的字符串，如果下面输入的字符串与一开始输入的字符串除未知部分的其他部分完全相同，则该字符串符合要求。

解题思路（字符串，模拟）

依据题意模拟即可。

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

string s, t;
int n;

bool judge()
{
	for (int i = 0;i < 9;i++)
	{
		if (s[i] == '*') continue;
		if (s[i] != t[i]) return false;
	}
	return true;
}

void solve()
{
	cin >> s >> n;
	vector<string> ans;
	for (int i = 1;i <= n;i++)
	{
		cin >> t;
		if (judge()) ans.push_back(t);
	}
	cout << ans.size() << '\n';
	for (auto it : ans)
		cout << it << '\n';
}

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

B 训练无垢者

出题人：South_Orange

题意简述

有 $n$ 个无垢者，每个人至少需要训练 $c_i$ 次，每次训练各需要 $p_i$ 枚金币。为所有人都训练一次需要花费 $S$ 枚金币。计算最少需要花费多少金币，才能确保所有无垢者都完成所需的训练次数。

解题思路（贪心，结构体排序）

将所有无垢者按训练次数排序，当集体训练的成本小于给剩下所有需要训练的无垢者各自训练的成本时集体训练，否则各自训练。

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

using ll = long long;

const int N = 1e5 + 10;
ll n, s;
struct Node
{
	ll p, c;
	bool operator<(const Node& t)const
	{
		return c < t.c;
	}
}a[N];

void solve()
{
	cin >> n >> s;
	ll nowp = 0, nowc = 0; //当前已集体训练的次数与各自训练的成本
	ll ans = 0;
	for (int i = 1;i <= n;i++)
	{
		cin >> a[i].p >> a[i].c;
		nowp += a[i].p;
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1;i <= n;i++)
	{
		if (s < nowp) //集体训练的成本小于各自训练
		{
			ans += (a[i].c - nowc) * s;
			nowc = a[i].c;
			nowp -= a[i].p; //某个无垢者训练完成之后各自训练的成本相应地减少
		}
		else //集体训练的成本大于各自训练
		{
			ans += (a[i].c - nowc) * a[i].p;
		}
	}
	cout << ans << '\n';
}

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

C 月兔集训中…

出题人：MarisaMagic

题意简述

给定一个 $n \times n$ 的网格图，每格上有一个点，每次操作可以使得所有点同时向上、下、左、右四个方向移动一格。点不会移动到超过网格图范围。构造一个长度不超过 $3 \times (n - 1)$ 的操作序列使所有点移动到指定位置 $(s, t)$ 。

解题思路（构造，模拟）

正确的构造思路主要分为先 汇集到一点，再 整体移动到指定位置 两个步骤：

汇集到一点：

考虑先将所有点汇集到一个角落（ $(1, 1)$ ， $(1, n)$ ， $(n, 1)$ ， $(n, n)$ 中的一个），汇集之后可以将所有点看作一点再进行整体移动。

我们需要选择距离 $(s, t)$ 最近的一个角落，可以通过枚举四个角落距离 $(s, t)$ 的曼哈顿距离得到。

进行若干次移动使得所有点汇集到最近的角落。此步骤所需移动次数不超过 $2 \times (n - 1)$ 次。
整体移动到指定位置：

所有点汇集到最近的角落后，可以看作是一个点进行移动。显然四个角落中最近的角落距离 $(s, t)$ 的曼哈顿距离不会超过 $n - 1$ 。

故此步骤所需移动次数不超过 $n - 1$ 次。

综上，两步骤所需移动总次数不超过 $3 \times (n - 1)$ 次，符合题意。时间复杂度为 $\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, s, t; cin >> n >> s >> t;

    // 1. 汇集到一点
    int x = 1, y = 1; // 枚举得到距离(s,t)最近的角落(x,y)
    for(int i = 1; i <= n; i += n - 1)
        for(int j = 1; j <= n; j += n - 1)
            if(abs(x - s) + abs(y - t) > abs(i - s) + abs(j - t))
                x = i, y = j;

    // 汇集到最近的角落(x,y)
    for(int i = 1; i < n; i ++ ) cout << (x == 1 ? 'U' : 'D');
    for(int i = 1; i < n; i ++ ) cout << (y == 1 ? 'L' : 'R');

    // 2. 整体移动到指定位置(s,t)
    for(int i = 1; i <= abs(s - x); i ++ ) cout << (s < x ? 'U' : 'D');
    for(int i = 1; i <= abs(t - y); i ++ ) cout << (t < y ? 'L' : 'R');
}

int main(){
    ios;

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

    return 0;
}

D 练歌可以，但是不要吵闹哦~

出题人：MarisaMagic

题意简述

给定一个长度为 $n$ 的 $01$ 串，一个 $01$ 子串的权值定义为 $0$ 的个数 $\times$ $1$ 的个数。最小化划分为恰好 $k$ 个 $01$ 子串的最大权值。

解题思路（二分）

此问题具有二段性。最大权值越大，显然划分的 $01$ 子串越长，划分的子串个数也越少；最大权值越小，划分的 $01$ 子串越小，子串个数也越多。

因此，考虑二分答案。对于当前二分的权值 $mid$ ，从左至右遍历整个 $01$ 串进行划分，用 $cnt_0$ 和 $cnt_1$ 分别维护当前子串的 $0$ 和 $1$ 的个数。如果当前 $cnt_0 \times cnt_1 > mid$ ，那么需要重新划分出一个子串；否则，可以继续累计 $0$ 和 $1$ 的个数。

若最终划分出的子串个数 $\le k$ ，记录答案，并继续向左是否答案可以更小；否则，结果不合法，需继续向右。注意要开 long long。时间复杂度为 $\mathcal{O}(n\log n)$

#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, k; cin >> n >> k;
    string s; cin >> s;
    
    auto check = [&](ll mid){
        vector<int> cnt(2); // 维护0和1的个数
        int num = 1; // 划分出的子串个数
        for(const auto& ch : s){
            cnt[ch - '0'] ++ ;
            if((ll)cnt[0] * cnt[1] > mid){
                cnt[0] = cnt[1] = 0; // 重开一个子串
                cnt[ch - '0'] = 1;
                num ++ ; // 更新划分子串个数
            }
        }
        return num <= k;
    };
    
    ll l = 0, r = (ll)n * n; // 二分权值，权值最大可达n*n
    while(l < r){
        ll mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << "\n";
}

int main(){
    ios;

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

    return 0;
}

E 都市派与野生派

出题人：MarisaMagic

题意简述

此问题等价于：Alice 和 Marisa 在 $a$ 序列和 $b$ 序列中分别选择一个数，Alice 想让它们相差的绝对值最大，Marisa 想让它们相差的绝对值最小，求它们的绝对值。

解题思路（博弈论，思维）

从 Marisa 的角度出发，Alice 先手，故 Alice 可以最后选择留下任意一个数 $x$ 结束游戏，因此 Marisa 得不到更好的结果。接下来证明：无论 $x$ 取何值，Marisa 一定能够选到最优的 $y$ ，使得 $|x - y|$ 最小化。

对于 $a$ 序列的每个数 $a_i$ ，求出 $b$ 序列中使得 $|a_i - b_j|$ 最小的对应的下标 $j$ 。我们可以用一个新的序列来记录每个 $a_i$ 对应的 $b$ 序列中最优的下标，记为 $c_i$ 。

考虑 Alice 删掉一个数 $a_x$ ， $b$ 序列暂时不动， $a$ 序列中剩余的其他数 $a_i$ 都可以在此时的 $b$ 序列中找到 $c_i$ 。由于此时 $b$ 序列比 $a$ 序列多一个数，因此 $b$ 序列中必然 存在至少一个 数对应下标 不是 $a$ 序列中剩余的其他数 $a_i$ 所对应的 $c_i$ 。我们选择此时 $b$ 序列中任意一个不是的数的下标，记为 $y$ 。

Marisa 需要让差值尽可能小，为了 $b$ 序列中保证能找到 $a$ 序列剩余数每个 $a_i$ 的 $c_i$ ，Marisa 需要将 $b_y$ 删去。接下来就变成一个序列长度 $n - 1$ 的子问题，且剩余的 $c$ 数组不变。因此，无论 $a_x$ 取何值，Marisa 一定能够选到最优的 $b_{c_x}$ ，使得差值最小化。

由此，我们可以得到本题做法如下：

将 $b$ 序列从小到大排序，枚举 $a$ 序列的每个数 $a_i$ ，在 $b$ 中二分找到 $a_i$ 对应使得差值最小的 $b_j$ 。由于 Alice 可以最后选择留下任意一个数结束，故最终输出所有 $|a_i - b_j|$ 的最大值。时间复杂度 $\mathcal{O}(n\log 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), b(n);
    for(auto& x : a) cin >> x;
    for(auto& x : b) cin >> x;
    sort(begin(b), end(b));
    int ans = 0;
    for(const auto& x : a){
        int j = lower_bound(begin(b), end(b), x) - begin(b);
        int mn = 1e9; // |a_i - b_j|
        if(j < n) mn = min(mn, b[j] - x);
        if(j > 0) mn = min(mn, x - b[j - 1]);
        ans = max(ans, mn); // 更新 |a_i - b_j| 的最大值
    }
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

F 華鳥風月 II

出题人：MarisaMagic

题意简述

给定一颗 $n$ 个节点的树，节点有黑色和白色，可以删除一个白色节点，也可以将一个白色节点变为黑色，求使得这颗树变为一颗全为黑色节点的树所需最少的变色操作次数。

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

可以发现，任意两个黑点之间的白点都不能被删除，我们只能将这些白点变为黑色才能保证最终节点全为黑且是一颗树（连通）。

我们需要选择一个黑点作为根节点，进行 dfs。不难发现位于黑点之间的白点具有一个特性：以此白点为根的子树中包含黑点。而全为白点的子树我们都可以直接删除。

因此，我们以一个黑点作为根进行 dfs，并自底向上更新每个子树 $u$ 中黑节点数量 $sz_u$ ，统计 $sz_u = 0$ （全为白点）的子树个数。由此就可以得到可以删除的白点的个数。

最终答案即白点总数减去可以删除的白点的个数。时间复杂度 $\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, cnt0 = 0; cin >> n;
    vector<int> c(n + 1); // 每个点的颜色
    for(int i = 1; i <= n; i ++ ){
        cin >> c[i];
        cnt0 += (!c[i]); // 白点个数
    }

    vector<vector<int>> e(n + 1); // 图
    for(int i = 1, u, v; i < n; i ++ ){
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }

    int rt = 1; // 找到一个黑点作为dfs的根节点
    while(c[rt] == 0) rt ++ ;
    if(rt > n){ // 全是白点
        cout << 0 << "\n";
        return;
    }

    int res = 0; // 统计全为白点的子树个数
    vector<int> sz(n + 1); // sz[u]: 以u为根的子树中的黑点个数
    function<void(int, int)> dfs = [&](int u, int fa){
        sz[u] = c[u];
        for(const auto& v : e[u]){
            if(v == fa) continue;
            dfs(v, u);
            sz[u] += sz[v]; // 自底向上
        }
        if(!sz[u]) res ++ ; // 更新全为白点的子树个数
    };

    dfs(rt, 0);

    cout << cnt0 - res << "\n";
}

int main(){
    ios;

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

    return 0;
}

G 帕琪不希望发生的事

出题人：MarisaMagic

题意简述

给定 $n$ 个字符，求有多少种下标排列使得构成的字符串为 非回文串。答案对 $10^9 + 7$ 取模。

解题思路（数学，组合数）

对于 $n$ 个字符，有 $n!$ 种排列构成一个字符串。记每种字符出现的次数为 $cnt_i$ （ $0 \le i < 26$ ），如果 $cnt_i$ 为奇数的字符个数大于 $1$ ，那么必然不能构成回文串，故次数直接输出 $n!$ 即可。

我们可以反过来考虑有多少种下标排列使得构成的字符串为回文串，然后将 $n!$ 减去这个数量即为答案。

对于每种字符，显然有 $cnt_i!$ 种排列方式。我们要构成回文串，只需要考虑前一半数量的字符在整个字符串前 $\frac{n}{2}$ 个位置中的组合方式（即选择前 $\frac{n}{2}$ 个位置中的任意 $\frac{cnt_i}{2}$ 个位置放入前一半数量的字符）。

如果有一个奇数字符，那么这个字符必然有一个放在回文串中间。上面的过程依然成立。

因此我们枚举每种字符 $i$ ，记录当前加入到整个字符串前 $\frac{n}{2}$ 个位置的字符数量 $sum$ ，每次 $sum += \frac{cnt_i}{2}$ 。当前字符有 $cnt_i!$ 种排列方式，其组合方式数量为 $C_{n / 2 - sum}^{cnt_i / 2}$ 。最终回文串的答案为 $\prod_{i=0}^{25} cnt_i! \times C_{n / 2 - sum}^{cnt_i / 2}$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using ll = long long;
const int N = 2010, mod = 1e9 + 7;

// 快速幂
inline ll qmi(ll a, ll b, int p){
    ll res = 1; 
    a %= p; 
    while(b){
        if(b & 1) res = (res * a) % p; 
        a = (a * a) % p;
        b >>= 1;
    } 
    return res;
}

// 阶乘，阶乘逆元（逆元求组合数）
ll fac[N], infac[N];

void work(){
    fac[0] = infac[0] = 1;
    for(int i = 1; i < N; i ++ ){
        fac[i] = fac[i - 1] * i % mod;
        infac[i] = infac[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

// 组合数
inline ll C(int n, int m){
    if(n < 0 || m < 0 || n < m) return 0ll;
    return fac[n] * infac[n - m] % mod * infac[m] % mod;
}

void marisa(){
    int n, cnt_odd = 0; cin >> n;
    string s; cin >> s;
    vector<int> cnt(26);
    for(const auto &c : s) cnt[c - 'a'] ++ ;
    for(int i = 0; i < 26; i ++ ) cnt_odd += (cnt[i] & 1);

    // 如果超过一种字符为奇数，答案为 n!
    if(cnt_odd > 1){
        cout << fac[n] << "\n";
        return;
    }

    ll ans = 1, sum = 0; // 答案，记录当前加入前一半位置字符个数
    for(int i = 0; i < 26; i ++ ){
        ans = ans * fac[cnt[i]] % mod * C(n / 2 - sum, cnt[i] / 2) % mod;
        sum += cnt[i] / 2;
    }    
    ans = (fac[n] - ans + mod) % mod;
    cout << ans << "\n";
}

int main(){
    ios;

    work();

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

    return 0;
}

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

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

2025 YAC Round 2 题解

https://marisamagic.github.io/2025/01/20/2025_YAC_2/

作者

MarisaMagic

发布于

2025年1月20日

许可协议

2025 YAC Round 3 题解上一篇

2025 YAC Round 1 题解下一篇

2025 YAC Round 2 题解

A 瓦雷利亚的失落符文

题意简述

解题思路 （字符串，模拟）

B 训练无垢者

题意简述

解题思路 （贪心，结构体排序）

C 月兔集训中…

题意简述

解题思路 （构造，模拟）

D 练歌可以，但是不要吵闹哦~

题意简述

解题思路 （二分）

E 都市派与野生派

题意简述

解题思路 （博弈论，思维）

F 華鳥風月 II

题意简述

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

G 帕琪不希望发生的事

题意简述

解题思路 （数学，组合数）

解题思路（字符串，模拟）

解题思路（贪心，结构体排序）

解题思路（构造，模拟）

解题思路（二分）

解题思路（博弈论，思维）

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

解题思路（数学，组合数）