2024 YAC Round 12 题解

A 水上由崎的字符串

出题人：Lynia

题意描述

解题思路（语法题）

直接倒序输出，或者用 C++ 的 reverse 更改整个字符串，也可以直接用 Python 的切片。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T; cin >> T;
    while (T--) {
        string a; cin >> a;
        for (int i = a.size() - 1; i >= 0; i--) cout << a[i];
        cout << '\n';
    }
}

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T; cin >> T;
    while (T--) {
        string a; cin >> a;
        reverse(a.begin(), a.end());
        cout << a << '\n';
    }
}

1 2	`T = int(input()) for i in range(T): print(input()[::-1])`

B 三分之王

出题人：MarisaMagic

题意描述

已知球筐位于 $(0, 0)$ ，三分线为一个半径 $7.25m$ 的圆弧，投篮点可由 $(x, y)$ 表示（单位为 $m$ ）。统计命中的投篮中有多少个是三分球。（“bang!!!” 为投篮命中，“missed” 为未命中）「YAC Round 12」三分之王

解题思路（简单计算几何）

对于每次投篮，先判断是否进球，再判断是否满足 $x ^ 2 + y ^ 2 > 7.25^2$ or $\sqrt{x ^ 2 + y ^ 2} > 7.25$ 即可。

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

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

void marisa(){
    int n, ans = 0; cin >> n;
    for(int i = 1; i <= n; i ++ ){
        string s; cin >> s;
        double x, y; cin >> x >> y;
        ans += (s[0] == 'b' && x * x + y * y > 7.25 * 7.25);
    }
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

C 大空魔术

出题人：MarisaMagic

题意描述

给定一个无数个节点的带权无向完全图，编号 $1 \sim +\infty$ ，两个不同节点 $i$ 和 $j$ 之间的边的长度为 $\text{lcm}(i, j)$ 。有 $m$ 次询问，每次询问两个节点 $x, y$ ，求两个节点之间的最短距离。「YAC Round 12」大空魔术

解题思路（数学）

先判断 $x = y$ 的情况，此时答案为 $0$ ；

若走 $1$ 步，最短的距离就是 $\text{lcm}(x, y)$ ；

若走 $2$ 步，第一步一定 $\ge x$ ，第二步一定 $\ge y$ ，因此走 $2$ 步所得的距离一定满足 $\ge x + y$ 。显然， $x$ 到 $y$ 的走 $2$ 步的最短距离可以在 $\text{lcm}(1, x) + \text{lcm}(1, y) = x + y$ 时取到。

若走大于 $2$ 步，显然不会比只走 $2$ 步更优。因此当 $x \not = y$ 时，答案就是 $\min(\text{lcm}(x, y), x + y)$ 。但是，数据范围为 $1 \le x, y \le 10^{18}$ ，直接求最小公倍数会导致数据溢出（为此本题也卡掉了python）

我们假定 $x < y$ ， $\gcd(x, y)$ 表示 $x, y$ 的 最大公约数，分类讨论 $\text{lcm}(x, y)$ 与 $x + y$ 的大小关系：

若 $\gcd(x, y) = x$ ，可以推出:
$\text{lcm}(x, y) = y < x + y$
故此时答案为 $y$ 。
若 $\gcd(x, y) \not = x$ ，则表明 $\frac{x}{\gcd(x, y)} \ge 2$ ，由此我们可以推出：
$\text{lcm}(x, y) = \frac{x \times y}{\gcd(x, y)} \ge 2 y > x + y$
故此时答案为 $x + y$ 。

我们甚至可以不用求 $\gcd$ 来进行判断， $\gcd(x, y) = x \Leftrightarrow y \mod x = 0$ 是一个充要条件，因此只需要看是否满足 $y \mod x = 0$ 条件判断。

#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 x, y; cin >> x >> y;
    if(x == y){ cout << 0 << "\n"; return; }
    if(x > y) swap(x, y);
    cout << (y % x == 0 ? y : x + y) << "\n";
}

int main(){
    ios;

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

    return 0;
}

D 華鳥風月

出题人：MarisaMagic

题意描述

给定一颗 $n$ 个节点的树，每个节点为黑色或白色。求 相邻节点颜色均不相同 的最长简单路径的长度（节点个数）。「YAC Round 12」華鳥風月

解题思路（树的直径树形DP / 两次DFS）

以下称满足 相邻节点颜色均不相同 的最长简单路径为“合法路径”。

我们设定节点 $1$ 为树的根节点，考虑 树形DP。设 $f_1[u]$ 为 $u$ 为根的子树向下所能延伸的最长合法路径长度， $f_2[u]$ 为 $u$ 为根的子树向下所能延伸的次长合法路径长度。要求得整棵树的最长合法路径长度，枚举每个节点 $i$ 作为中间的点，找出 $f_1[i] + f_2[i] + 1$ 最大值即可（路径长度定义为节点个数，因此要 $ + 1$）。

可以发现上述做法和求解 树的直径 是完全一致的，但需要在状态转移过程中增加节点颜色的判断。自底向上从 $v$ 转移到 $u$ 时，如果颜色不同，用 $f_1[v] + 1$ 对 $u$ 为根的子树所能延伸的最长和次长长度正常更新；如果颜色相同，则不能走过去，直接跳过即可。

// dp求树的直径 写法1
#include<bits/stdc++.h>
using namespace std;

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

int n, ans, c[N], f1[N], f2[N];
vector<int> e[N];

void dfs(int u, int fa){
    for(const auto &v : e[u]){
        if(v == fa) continue;
        dfs(v, u);
        if(c[u] == c[v]) continue; // 颜色相同直接跳过
        int tmp = f1[v] + 1;
        if(tmp > f1[u]) f2[u] = f1[u], f1[u] = tmp;
        else if(tmp > f2[u]) f2[u] = tmp;
    }
    ans = max(ans, f1[u] + f2[u] + 1);
}

void marisa(){
    cin >> n;
    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);
    }

    dfs(1, 0);

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

int main(){
    ios;

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

    return 0;
}

我们也可以用另一种树形 DP 方法。定义 $f[u]$ 为 $u$ 为根的子树向下所能延伸的最长合法路径长度。类似于 树的直径 OI Wiki 中 过程2 的做法，增加一个节点颜色判断即可。

// dp求树的直径 写法2
void dfs(int u, int fa){
    for(auto &v : e[u]){
        if(v == fa) continue;
        dfs(v, u);
        if(c[u] ^ c[v]){
            ans = max(ans, dp[u] + dp[v] + 2); // 节点个数需再+1
            dp[u] = max(dp[u], dp[v] + 1);
        }
    }
}

一条边上节点颜色相同，我们的操作是直接跳过，边上端点所属的子树之间结果互不影响。因此可以在建树的时候忽略这些端点颜色相同的边，构建若干个小树。最终我们只需要在每个小树上单独进行 树形DP / 两次DFS 求得树的直径，再取最大值即为答案。以下给出忽略端点颜色相同的边，用 两次DFS 求解的代码。

// 两次dfs求树的直径
#include<bits/stdc++.h>
using namespace std;

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

int n, ans, id, c[N], dist[N];
vector<int> e[N];

void dfs(int u, int fa){
    for(auto &v : e[u]){
        if(v == fa) continue;
        dist[v] = dist[u] + 1;
        if(dist[v] > dist[id]) id = v; // 记录最远端点
        dfs(v, u);
    }
}

void marisa(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> c[i];
    for(int i = 1, u, v; i < n; i ++ ){
        cin >> u >> v;
        if(c[u] + c[v] != 1) continue;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }

    for(int i = 1; i <= n; i ++ ){
        id = 0;
        dfs(i, 0);  // 找到端点c
        dist[id] = 0;
        dfs(id, 0); // 找到id对应最远点  
        ans = max(ans, dist[id] + 1);
    }

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

int main(){
    ios;

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

    return 0;
}

E 交叉星尘

出题人：MarisaMagic

题意描述

给定一个 $n$ 个节点的带权无向图，有 $m$ 个集合，第 $i$ 个集合可表示为 $P_i = \{(v_1, b_1), (v_2, b_2), \ldots, (v_{|P|}, b_{|P|}) \}$ 。对于同一集合中的任意两个节点 $(v_i, b_i), (v_j, b_j)$ ，有一条连接 $v_i$ 和 $v_j$ 的边权为 $b_i + b_j$ 的无向边。对于节点 $i\in [1, n]$ ，求 $1$ 到 $i$ 的最短路长度。「YAC Round 12」交叉星尘

解题思路（dijkstra，构造）

直接暴力建图跑 $dijkstra$ 最短路，时间复杂度为 $\mathcal{O}((n + \sum{|P_i|^2})\log{\sum{|P_i|^2}})$ ，但是会导致边数太大 MLE。因此需要考虑构造转变建图方式来优化空间。

对于每个集合，考虑构建一个虚点 $x$ 。对于同一个集合的每个点 $(v_i, b_i)$ ，在 $v_i$ 与 $x$ 之间连接一条边权 $b_i$ 的无向边。由此将原本的完全图转换为了 菊花图，边的数量大大减少。

在转换构建的图中，相当于将原先的一条边权为 $b_i + b_j$ 的边拆成了两条分别长为 $b_i$ 和 $b_j$ 的边。这些拆分后的边通过被重复利用以达到 $length_{(v_i, v_j)} = b_i + b_j, \forall \ i, j\in [1, |P|]$ ，所构建出的图与原图等价。

故在转换构建出的图上跑一遍 $dijkstra$ 最短路即可，时间复杂度: $\mathcal{O}((n + \sum{|P_i|})\log{\sum{|P_i|}})$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 6e5 + 10;
using ll = long long;
using pll = pair<ll, ll>;

int n, m, st[N];
vector<pll> e[N];
ll dist[N];

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    priority_queue<pll, vector<pll>, greater<pll> > q;
    q.emplace(dist[1] = 0, 1);

    while(q.size()){
        auto [d, u] = q.top();
        q.pop();

        if(st[u]) continue;
        st[u] = true;

        for(const auto &[v, w] : e[u])
            if(dist[v] > d + w) q.emplace(dist[v] = d + w, v);
    }
}

void marisa(){
    cin >> n >> m;
    for(int i = 1, k; i <= m; i ++ ){
        cin >> k;
        int u = n + i; // 虚拟点
        for(int j = 1, v, w; j <= k; j ++ ){
            cin >> v >> w;
            e[u].emplace_back(v, w);
            e[v].emplace_back(u, w);
        }
    }

    dijkstra();

    for(int i = 1; i <= n; i ++ ) cout << dist[i] << " \n"[i == n];
}

int main(){
    ios;

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

    return 0;
}

F 就在你身边

出题人：Lynia

题意描述

给你长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$ ，你可以进行最多 $k$ 次操作，每次操作可以把一个元素增加或减少 $1$ ，求操作后最长的连续相等的子串。「YAC Round 12」就在你身边

解题思路（双指针，中位数性质，双堆模拟）

很明显这题可以用双指针开个滑动窗口解决。问题是枚举的每个区间该全等于什么值，这里就使用上了中位数性质——最小化绝对偏差，中位数是使得绝对偏差和（即所有数据点与中位数的绝对差值之和）最小的值。

数学上，这可以表示为：

\text{Minimize} \sum_{i=1}^{n} |x_i - M|

其中， $M$ 为中位数， $x_i$ 为数据集中的各个数值。

知道了这个性质后，我们找到滑动窗口枚举的区间的中位数，直接计算区间所有值变成中位数要的总操作次数就行，根据总操作是否超过 $k$ 来判断慢指针的移动。

至于中位数的维护，我们这边使用两个 multiset 即可，当然过程中对这两个双堆要进行不断调整，具体实现参考题解代码。

#include<bits/stdc++.h>
using namespace std;
#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define var auto
#define all(i) i.begin(), i.end()
#define endl '\n'
using ll = long long;
void solve()
{
	ll n, k; cin >> n >> k;
	var a = vector<ll>(n + 1, 0);
	fa(i, 1, n)cin >> a[i];

	// 双堆维护中位数
	multiset<ll>r;              // 右堆，存大于等于中位数的
	multiset<ll, greater<ll>>l; // 左堆，存小于等于中位数的，中位数也存这里了
	ll l_sum = 0, r_sum = 0;    // 双堆各自求和

	// 双堆刷新，维护中位数的正确排位
	// len：当前的区间长度
	var f = [&](int len)->void {
		ll tmp;

		// 先调整大小
		// 左堆不能有大于右堆的
		while (l.size() and r.size() and (*l.begin()) > (*r.begin())) {
			tmp = (*l.begin());
			r_sum += tmp, r.insert(tmp);
			l_sum -= tmp, l.erase(l.begin());
		}

		// 再调整双堆个数
		if (len & 1) { 
			// 奇数的时候，l.size() - r.size() == 1
			while (l.size() < r.size() + 1) {
				tmp = (*r.begin());
				l_sum += tmp, l.insert(tmp);
				r_sum -= tmp, r.erase(r.begin());
			}
			while (l.size() > r.size() + 1) {
				tmp = (*l.begin());
				r_sum += tmp, r.insert(tmp);
				l_sum -= tmp, l.erase(l.begin());
			}
		}
		else {
			// 偶数的时候，l.size() == r.size()
			while (l.size() < r.size()) {
				tmp = (*r.begin());
				l_sum += tmp, l.insert(tmp);
				r_sum -= tmp, r.erase(r.begin());
			}
			while (l.size() > r.size()) {
				tmp = (*l.begin());
				r_sum += tmp, r.insert(tmp);
				l_sum -= tmp, l.erase(l.begin());
			}
		}
		};

	// 双指针找最长全相等区间
	ll j = 1;   // 慢指针
	ll ans = 1; // 最长全相等区间长度
	fa(i, 1, n) {
		if (l.size() == 0)l_sum += a[i], l.insert(a[i]); // 先放左堆一个
		else {
			if (a[i] <= (*l.begin()))l_sum += a[i], l.insert(a[i]);
			else r_sum += a[i], r.insert(a[i]);
		}

		f(i - j + 1); // 刷新双堆
		ll mmid = (*l.begin()); // 当前中位数
		ll now = (mmid * (ll)l.size() - l_sum) + (r_sum - mmid * (ll)r.size()); // 全改成中位数要使用的操作次数

		while (now > k and j < i) { // 更新慢指针
			// 把左右堆的 a[j] 删掉
			if (l.count(a[j])) l_sum -= a[j], l.erase(l.find(a[j]));
			else r_sum -= a[j], r.erase(r.find(a[j]));
			j++;

			f(i - j + 1); // 刷新双堆
			mmid = (*l.begin()); // 当前中位数
			now = (mmid * (ll)l.size() - l_sum) + (r_sum - mmid * (ll)r.size()); // 全改成中位数要使用的操作次数
		}

		ans = max(ans, i - j + 1); // 更新答案
	}
	cout << ans << endl;
	return;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	//cin >> _;
	fa(i, 1, _)solve();
	return 0;
}

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

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

2024 YAC Round 12 题解

https://marisamagic.github.io/2024/12/14/YAC_Round_12/

作者

MarisaMagic

发布于

2024年12月14日

许可协议

2024 YAC Round 13 题解上一篇

2024 YAC Round 11 题解下一篇

2024 YAC Round 12 题解

A 水上由崎的字符串

题意描述

解题思路 （语法题）

B 三分之王

题意描述

解题思路 （简单计算几何）

C 大空魔术

题意描述

解题思路 （数学）

D 華鳥風月

题意描述

解题思路 （树的直径 树形DP / 两次DFS）

E 交叉星尘

题意描述

解题思路 （dijkstra，构造）

F 就在你身边

题意描述

解题思路 （双指针，中位数性质，双堆模拟）

解题思路（语法题）

解题思路（简单计算几何）

解题思路（数学）

解题思路（树的直径树形DP / 两次DFS）

解题思路（dijkstra，构造）

解题思路（双指针，中位数性质，双堆模拟）