2025 YAC Round 4 题解

A 开始还是结束？

出题人：MarisaMagic

题意简述

给定一个格式为“小时:分钟”的时间 $t$ ，判断在 $14:00$ 前、 $14:00\sim 17:00$ 内还是 $17:00$ 后。

解题思路（语法）

输入得到小时 $h$ 和分钟 $m$ ，由此可以得到总分钟数为 $h \times 60 + m$ ，判断是否位于时间段内的分钟数即可。

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

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

void marisa(){
    int h, m; char ch;
    cin >> h >> ch >> m;
    int t = h * 60 + m;
    if(t < 14 * 60) cout << "wei kai shi." << "\n";
    else if(t > 17 * 60) cout << "yi jie shu." << "\n";
    else cout << "bi sai zhong." << "\n";
}

int main(){
    ios;

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

    return 0;
}

B 不要为难鸟脑袋了！

出题人：MarisaMagic

题意简述

给定一个整数 $n$ 和一个字符串 $s$ （ $s_i \in \{ '1', '2' \}$ ）。初始有 $n$ 个空位。从头开始遍历字符串 $s$ :

若 $s_i = '1'$ ，表示这个元素需要占用 $1$ 个空位；否则，表示需要占用相邻的 $2$ 个空位。
每次遍历到一个字符，可以选择占用一些空位来放置这个元素，也可以选择跳过不放置。若空位不足，可以撤除之前已经放置的一些元素。

每个放置了的元素从放置回合起，每回合产生 $1$ 个单位价值，一个元素被撤除后不再产生价值。求能够获得的价值总和的最大值。

解题思路（贪心，模拟）

每个元素每回合产生的价值都为 $1$ ，记占用 $1$ 个空位的元素为元素 $1$ ，占用相邻 $2$ 个空位的元素为元素 $2$ 。考虑贪心算法维护每一回合放置的元素 $1$ 个数 $cnt_1$ 和 $2$ 的个数 $cnt_2$ ：

设当前回合元素所需占用的空位个数为 $v$ 。

如果当前空余的空位个数大于等于 $v$ ，那么可以直接放置这个元素。
如果当前空余的空位个数小于 $v$ ：
- 若 $v = 1$ ，所需的空位个数相对于元素 $2$ 更少，因此可以尝试撤除一个元素 $2$ ，然后再放置这个元素 $1$ 。这样 这一回合产生的价值数没有下降，同时 空出更多位置 可以使得后续回合放置更多的元素。
- 若 $v = 2$ ，如果撤除一些元素 $1$ 来放置，这一回合产生的价值数反而下降，也没有空出多余的位置；如果撤除一个元素 $2$ 来放置，不会有更好的效果。

基于上述贪心策略，可以使得每一回合产生的价值数是非降的，前后回合价值数差距不超过 $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; cin >> n;
    string s; cin >> s;
    long long ans = 0;
    vector<int> cnt(3);
    for(const auto& ch : s){
        int v = ch - '0';
        if(n >= v){ // 直接放置
            cnt[v] ++ ;
            n -= v;
        }else if(v == 1 && cnt[2] > 0){
            cnt[2] -- ; // 可以撤除一个元素 2
            cnt[1] ++ ; // 放置一个元素 1
            n ++ ; // 多出一个空位
        }
        ans += cnt[1] + cnt[2]; // 当前回合产生价值
    }
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

C 寺子屋的新老师

出题人：MarisaMagic

题意简述

计算斐波那契数列的前 $n$ 项中有多少对二元组 $(i, j)$ （ $i < j$ ）满足乘积 $f_i \times f_j$ 为偶数。

解题思路（数学）

斐波那契数列有一个奇偶性规律，即数列每一项的奇偶性满足：奇、奇、偶、奇、奇、偶…

可以发现，斐波那契数列的前 $n$ 项有 $x = \lfloor \frac{n}{3} \rfloor$ 个偶数。两项乘积为偶数包括 偶数乘偶数 和 偶数乘奇数 两种可能。因此，两种可能对答案的贡献如下：

偶数乘偶数： $\frac{x(x - 1)}{2}$ ，即 $x$ 个偶数中任选两个数相乘。
偶数乘奇数： $x(n - x)$ ，即 $x$ 个偶数和 $n - x$ 个奇数各任选一个相乘。

#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(){
    ll n; cin >> n;
    ll x = n / 3;
    // 偶数乘偶数 + 偶数乘奇数
    cout << x * (x - 1) / 2 + x * (n - x) << "\n";
}

int main(){
    ios;

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

    return 0;
}

D 可以办一整个月的宴会吗

出题人：MarisaMagic

题意简述

给定 $n$ 个数 $a_1, a_2, \ldots, a_n$ ，选择 $m$ 个数使得这些数做 按位与运算 最大。

解题思路（位运算、贪心）

输入的数二进制下最多 $29$ 位，考虑从高位到低位遍历每个二进制位。对于当前二进制位 $i$ 若有大于等于 $m$ 个数满足第 $i$ 位为 $1$ ，那么我们必须选择这一位并将 $2^i$ 加到答案中，因为后面的位更低，即便全部加起来也不会比 $2^i$ 更大。

如果当前第 $k$ 位被选择，那么后续选择二进制位的候选数仅包含第 $i$ 位为 $1$ 的数。故我们在选择一位后可以对第 $i$ 位不为 $1$ 的数进行标记（一种方式是直接将数赋为 $0$ ）

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

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

void marisa(){
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for(auto& x : a) cin >> x;
    int ans = 0;
    for(int i = 29; ~i; i -- ){
        int cnt = 0;
        for(int j = 0; j < n; j ++ ) cnt += (a[j] >> i) & 1;
        if(cnt >= m){ 
            ans |= (1 << i); // 加上2^i
            for(int j = 0; j < n; j ++ ) // 标记第k位不为1的数
                if(!((a[j] >> i) & 1)) a[j] = 0;
        }
    }
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

E 刺刺乐队

出题人：MarisaMagic

题意简述

给定 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le 2n$ ）。构造一个序列 $b_1, b_2, \ldots, b_n$ （ $1 \le b_i \le 2n$ ），且 $\forall i \neq j$ ， $b_i \neq b_j$ ；同时 $\forall i$ ， $b_i = i$ 或 $b_i = a_i$ 。

求序列 $b$ 满足 $b_i = a_i$ 的最大数量。

解题思路（拓扑排序、dfs）

我们考虑对于每个 $a_i$ ，构建一条 $i \rightarrow a_i$ 的边。观察这些边构成的图可以发现，图中只有单链和环两种结构。

对于环，可以发现环上的点都可以穿上自己心仪的服装，即满足 $b_i = a_i$ 。
对于单链，分为两种情况：
- 单链的 终点是一个大于 $n$ 的点。任何大于 $n$ 的点都不会出边，一条链上不会有大于 $1$ 个大于 $n$ 的点。可以发现，这样的单链上的点都可以满足 $b_i = a_i$ ，故我们可以考虑在反向图上从每个大于 $n$ 的点进行搜索，加上每个这样的单链的长度。
- 单链最终 连接到一个环 上。对于这样的单链，如果链上有一个点要穿上心仪的服装，那么链上的这个点后面的点也必须穿上心仪的服装才可满足 $b_i = a_i$ 或 $i$ 的要求。引发一系列连锁反应最终导致所连接到的环上存在一点无法满足 $b_i = a_i$ 或 $i$ ，故这样的单链上的点 都不能满足 $b_i = a_i$ 。

综上所述，答案分为两个部分：（1）在反向图上以每个大于 $n$ 的点为起点进行 dfs 加上所有单链的长度（并标记这些点）；（2）在剩余的正向图上进行拓扑排序，加上剩余遍历不到的环上的点的个数。

#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;

int n, ind[N], vis[N];
vector<int> e[N], re[N];

void dfs(int u, int dep, int& mx_dep){
    if(u <= n){
        vis[u] = true; // 标记
        mx_dep = max(mx_dep, dep);
    }
    for(const auto& v : re[u]) // 在反向图上搜索
        dfs(v, dep + 1, mx_dep);
}

void topo(){
    queue<int> q;
    for(int i = 1; i <= n; i ++ )
        if(!vis[i] && !ind[i]) q.emplace(i);
    while(q.size()){
        int u = q.front();
        q.pop();
        vis[u] = true;
        for(const auto& v : e[u])
            if(!( -- ind[v])) q.emplace(v);
    }
}

void marisa(){
    cin >> n;
    for(int i = 1, a; i <= n; i ++ ){
        cin >> a;
        e[i].emplace_back(a);
        re[a].emplace_back(i);
        ind[a] ++ ;
    }
    int ans = 0;
    for(int i = n + 1; i <= 2 * n; i ++ ){
        int mx_dep = 0;
        dfs(i, 0, mx_dep); 
        ans += mx_dep; // 加上所有终点大于n的单链长度
    }
    topo();
    for(int i = 1; i <= n; i ++ ) ans += !vis[i]; // 环上的点
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

F 華鳥風月 III

出题人：South_Orange

题意简述

给点一棵包含 $n$ 个节点的树，节点有黑色和白色。求相距最远的一对不同颜色节点的距离是多少。

解题思路 1 （树的遍历）

类似树的直径的解题思路，维护一个子树中最长和次长的黑色节点与白色节点链。

记录黑色最长链与白色最长链是否在同一条链上，如果不在同一条链上则答案与黑色最长链+白色最长链取 $max$ ，否则如果次长链存在，答案与黑色最长链+白色次长链和黑色次长链+白色最长链取 $max$ 。

最后答案与当前节点的不同颜色的最长链取 $max$ 。

// South_Orange
#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;

int n;
int col[N];
vector<int> v[N];
int ans;
struct Node
{
	int bd, wd, cibd, ciwd;
	int bpos, wpos, cibpos, ciwpos;
};

Node dfs(int u, int fa)
{
	Node res = { 0,0,0,0 };
	for (auto it : v[u])
	{
		if (it == fa) continue;
		auto itres = dfs(it, u);
		if (itres.bd > res.bd) // 维护黑色链长度
		{
			res.cibd = res.bd;
			res.cibpos = res.bpos;
			res.bd = itres.bd;
			res.bpos = it;
		}
		else if (itres.bd > res.cibd)
		{
			res.cibd = itres.bd;
			res.cibpos = it;
		}
		if (itres.wd > res.wd) // 维护白色链长度
		{
			res.ciwd = res.wd;
			res.ciwpos = res.wpos;
			res.wd = itres.wd;
			res.wpos = it;
		}
		else if (itres.wd > res.ciwd)
		{
			res.ciwd = itres.wd;
			res.ciwpos = it;
		}
	}

	if (res.bpos != 0 && res.wpos != 0) // 黑色最长链与白色最长链存在
	{
		if (res.bpos != res.wpos) // 黑色最长链与白色最长链不在同一条链上
		{
			ans = max(ans, res.bd + res.wd);
		}
		else // 黑色最长链与白色最长链在同一条链上
		{
			if (res.ciwpos != 0) ans = max(ans, res.bd + res.ciwd);
			if (res.cibpos != 0) ans = max(ans, res.wd + res.cibd);
		}
	}

	if (col[u] == 0)
	{
		ans = max(ans, res.bd);
		res.wd++;
		if (res.bpos != 0) res.bd++;
	}
	else
	{
		ans = max(ans, res.wd);
		res.bd++;
		if (res.wpos != 0) res.wd++;
	}

	return res;
}

void solve()
{
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> col[i];
	for (int i = 1;i < n;i++)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, -1);
	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;
}

解题思路 2（树的直径）

类似于两次dfs求树的直径的做法，考虑任选一点（选择 $1$ 号点）作为起点进行第一次 dfs，找到最远的白色点 $f_0$ 和最远的黑色点 $f_1$ 。并记录 $s_0 = f_0, s_1 = f_1$ ，作为后续 dfs 的起点。

第二次 dfs 以 $s_0$ 为起点，找到对应最远的黑色点 $f_1$ ，由此求出 $s_0$ 到对应最远黑点 $f_1$ 的距离；

第三次 dfs 以 $s_1$ 为起点，找到对应最远的白色点 $f_0$ ，由此求出 $s_1$ 到对应最远白点 $f_0$ 的距离。

答案为第二次 dfs 和第三次 dfs 所求最远距离的最大值。不会有更大的距离。

// MarisaMagic
#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> c(n + 1); // 点的颜色
    vector<vector<int>> e(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> c[i];
    for(int i = 1, u, v; i < n; i ++ ){
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }

    int ans = 0, f0 = 0, f1 = 0;
    vector<int> d(n + 1);
    function<void(int, int)> dfs = [&](int u, int fa){
        for(const auto &v : e[u]){
            if(v == fa) continue;
            d[v] = d[u] + 1;
            if(!c[v] && d[v] > d[f0]) f0 = v; // 最远的白色点
            if(c[v] && d[v] > d[f1]) f1 = v;  // 最远的黑色点
            dfs(v, u);
        }
    }; 
    // 第一次dfs
    dfs(1, 0);
    int s0 = f0, s1 = f1; // 分别记录作为起点
    // 第二次dfs
    f0 = f1 = 0;
    d[s0] = 0;
    dfs(s0, 0); // 最远白色点作为起始点dfs
    ans = max(ans, d[f1]);
    // 第三次dfs
    f0 = f1 = 0;
    d[s1] = 0;
    dfs(s1, 0); // 最远黑色点作为起始点dfs
    ans = max(ans, d[f0]); 

    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

G 长夜

出题人：South_Orange

题意简述

给定平面直角坐标系上的 $n$ 个点，求出距离最远的两个点的距离。

解题思路（凸包）

平面最远点对问题可以等价于凸包直径问题。

首先我们需要求出点集的凸包。

然后我们考虑选定凸包的一条边所在的直线，比如 AB 。然后找到凸包的所有顶点中离它最远的点，在这个例子中是 D 。然后凸包直径就可能是 AD 或 BD 。

然后我们继续。逆时针选择下一条边 AE ，这时我们发现最远点变成了 C ，然后尝试用 AC,EC 更新答案。以此类推。这样我们就找到了凸包直径。

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

但是根据以前的经验，似乎最远点也是逆时针旋转的。换句话说，逆时针遍历的点到直线的距离单调。

这也可以用凸包的凸性来解释。我无法给出详细证明，但是大家不妨手动画几个图，就可以感性的理解了。

于是我们就可以用一个漂亮的双指针解决了。

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

namespace Geo{ ... }
using namespace Geo;
using ll = long long;

const int N = 50010;
int n;

template<typename T>
ll d2(const Point<T>& A, const Point<T>& B)
{
	return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

void solve()
{
	cin >> n;
	vector<Point<ll>> v;
	for (int i = 1;i <= n;i++)
	{
		ll a, b;
		cin >> a >> b;
		v.push_back(Point<ll>(a, b));
	}
	auto poly = convex_hull(v); // 求凸包
	int m = poly.size();
	int pos = 1;
	ll ans = 0;
	for (int i = 0;i < m;i++)
	{
		auto line = Line<ll>(poly[i % m], poly[(i + 1) % m]); //枚举边
		while (point_line_dis(poly[pos % m], line) < point_line_dis(poly[(pos + 1) % m], line)) pos++; //双指针枚举最远点
        ans = max(ans, d2(poly[i % m], poly[pos % m])); 
		ans = max(ans, d2(poly[(i + 1) % m], poly[pos % m]));
	}
	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;
}

namespace Geo 可见：Geo.cpp

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

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

2025 YAC Round 4 题解

https://marisamagic.github.io/2025/02/10/2025_YAC_4/

作者

MarisaMagic

发布于

2025年2月10日

许可协议

2025 扬州大学 GPLT 团体天梯赛校内选拔赛题解上一篇

2025 YAC Round 3 题解下一篇

2025 YAC Round 4 题解

A 开始还是结束？

题意简述

解题思路 （语法）

B 不要为难鸟脑袋了！

题意简述

解题思路 （贪心，模拟）

C 寺子屋的新老师

题意简述

解题思路 （数学）

D 可以办一整个月的宴会吗

题意简述

解题思路 （位运算、贪心）

E 刺刺乐队

题意简述

解题思路 （拓扑排序、dfs）

F 華鳥風月 III

题意简述

解题思路 1 （树的遍历）

解题思路 2（树的直径）

G 长夜

题意简述

解题思路 （凸包）

解题思路（语法）

解题思路（贪心，模拟）

解题思路（数学）

解题思路（位运算、贪心）

解题思路（拓扑排序、dfs）

解题思路（凸包）