2025 YAC Round 3 题解

比赛大图来源：pixiv_id=95319826

A 威严大小姐想要整理文件

出题人：MarisaMagic

题意简述

给定一颗有 nn 个叶子节点的树，叶子节点层级分别为 k1,k2,…,knk_1, k_2, \ldots, k_n，求最少需要多少非叶子节点构成这棵树。

解题思路 （贪心）

保证每个 kk 层的叶子节点有一个 k−1k-1 层的父节点即可，因此答案为 max⁡i=1n{ki−1}\max_{i=1}^{n}{ \{ k_i - 1 \} }。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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, k; i <= n; i ++ ){
        cin >> k;
        ans = max(ans, k - 1);
    }
    cout << ans << "\n";
}

int main(){
    ios;

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

    return 0;
}

B 云山

出题人：MarisaMagic

题意简述

给定一个长宽高为 a,b,ca,b,c 的长方体，变大 11 次会使得边长变为 kk 倍，求变大 nn 次后长方体的体积。答案对 109+710^9 + 7 取模。

解题思路 （数学、快速幂）

变大 nn 次后，长方体体积 VV 如下：

V=(a×kn)×(b×kn)×(c×kn)=(a×b×c)×k3n\begin{split} V &= (a \times k^n) \times (b \times k^n) \times (c \times k^n) \\\\ &= (a \times b \times c) \times k^{3n} \end{split}

nn 比较大，用 快速幂 求出 k3nk^{3n} 。按照公式计算答案即可。

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
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int 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;
}

int main() {
    ll a, b, c, n, k; cin >> a >> b >> c >> n >> k;
    ll ans = a * b * c % mod;
    ans = ans * qmi(k, 3ll * n, mod) % mod;
    cout << ans << "\n";

    return 0;
}

C 芙兰也想看烟花

出题人：MarisaMagic

题意简述

给定一个 n×mn\times m 的网格图，# 为障碍物，. 可以往相邻的四个位置移动，X 可以往对角的四个位置移动，求从 (1,1)(1,1) 到达 (n,m)(n,m) 的最短时间。

解题思路 （BFS）

要求最短时间，从起点 (1,1)(1,1) 广度优先搜索（BFS）即可。

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;
const int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};

int main() {
    int n, m; cin >> n >> m;
    vector<vector<char>> g(n + 1, vector<char>(m + 1)); // 地图
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ ) cin >> g[i][j];

    auto bfs = [&](){
        vector<vector<int>> d(n + 1, vector<int>(m + 1, -1)); // 距离
        queue<pair<int, int>> q;
        q.emplace(1, 1);
        d[1][1] = 0;
        while(q.size()){
            const auto& [x, y] = q.front();
            q.pop();
            bool c = (g[x][y] == '.');
            for(int k = (c ? 0 : 4); k < (c ? 4 : 8); k ++ ){
                int nx = x + dx[k], ny = y + dy[k];
                if(nx < 0 || ny < 0 || nx > n || ny > m) continue; // 出界
                if(g[nx][ny] == '#' || d[nx][ny] != -1) continue; 
                q.emplace(nx, ny);
                d[nx][ny] = d[x][y] + 1;
            }
        }
        return d[n][m];
    };

    cout << bfs() << "\n";

    return 0;
}

D 狸猫七十二变

出题人：MarisaMagic

题意简述

给定 nn 个点和 mm 条边以及 qq 次询问，每次询问是否可以从 xx 到达 yy。

解题思路 （Floyd、传递闭包）

考虑预处理任意两点之间的可达性，此预处理可以通过 nn 次搜索 或者 Floyd 求传递闭包 解决。

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
#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<vector<int>> d(n + 1, vector<int>(n + 1, false));
    for(int i = 1, u, v; i <= m; i ++ ){
        cin >> u >> v;
        d[u][v] = true;
    }
    for(int k = 1; k <= n; k ++ ) // floyd 求传递闭包
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                d[i][j] |= d[i][k] & d[k][j];
    int q; cin >> q;
    for(int i = 1, x, y; i <= q; i ++ ){
        cin >> x >> y;
        cout << (d[x][y] ? "YES" : "NO") << "\n";
    }
}

int main(){

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

    return 0;
}

E 前往东之国的新年列车

出题人：MarisaMagic

题意简述

给定 nn 个数字 r1,r2,…,rnr_1, r_2, \ldots, r_n，范围 1∼m1 \sim m。将 1∼m1 \sim m 分成连续的 kk 段，使得每个数字只属于一段。每个数字按照初始顺序放入每段，分别计算每段的正序对个数并求和。求如何分段使得这个和最小，输出最小值。

解题思路 （动态规划、前缀和）

考虑采用动态规划，定义 fi,kf_{i,k} ：将前 ii 排分为 kk 段，以 ii 作为第 kk 段结尾的最优方案下的最小值。由此可得状态转移方程如下：

fi,k=min⁡j<i{fj,k−1+gets(j+1,i)}f_{i,k} = \min_{j<i} \{ f_{j,k-1} + get_s(j + 1, i) \}

其中 jj 表示枚举上一段（第 k−1k - 1 段）的结尾；gets(j+1,i)get_s(j + 1, i) 表示将 j+1∼ij + 1 \sim i 分为一段，这一段的正序对的个数。动态规划枚举 i,j,ki, j, k 的部分时间复杂度为 O(m2k)\mathcal{O}(m^2k)。

关键在于 gets(j+1,i)get_s(j + 1, i) 如何解决。如果每次都遍历一遍整个数组 r1,r2,…,rnr_1, r_2, \ldots, r_n 并判断每个 j+1∼ij + 1 \sim i 范围内的数字前面的 j+1∼ij + 1 \sim i 排的个数，最优也需要 O(n)\mathcal{O}(n) 的时间开销，而我们需要考虑在 O(1)\mathcal{O}(1) 的时间复杂度得到 gets(j+1,i)get_s(j + 1, i)。

可以采用二维前缀和的思想，定义 si,js_{i,j} ：前 ii 排的前面排数为 1∼j1 \sim j 的个数。我们可以先在 O(n2)\mathcal{O}(n^2) 的时间复杂度统计出第 ii 排前面第 jj 排的数量，然后在 O(m2)\mathcal{O}(m^2) 的时间复杂度用二维前缀和求出第 1∼i1 \sim i 排前面第 1∼j1 \sim j 排的数量。

对于 gets(j+1,i)get_s(j + 1, i) 其实也就是第 j+1∼ij + 1 \sim i 排前面的第 j+1∼ij + 1 \sim i 排的数量，故只需要用如下二维前缀和公式求得：

gets(j+1,i)=s[i][i]−s[j][i]−s[i][j]+s[j][j];get_s(j + 1, i) = s[i][i] - s[j][i] - s[i][j] + s[j][j];

可以自行绘图借助二维前缀和矩阵辅助理解。

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
#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, K; cin >> n >> m >> K;
    vector<int> a(n + 1);

    // s[i][j] 表示前 i 排前面有多少坐在 1 ~ j 排
    vector<vector<int>> s(m + 1, vector<int>(m + 1)); 
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        for(int j = 1; j < i; j ++ ) // 统计第 i 排前面有多少人
            s[a[i]][a[j]] += a[j] < a[i]; 
    }

    // 求前缀和
    for(int i = 1; i <= m; i ++ )
        for(int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; 

    // 第 x1 ~ x2 排前面有多少坐在 y1 ~ y2 排
    auto get_s = [&](int x1, int y1, int x2, int y2){ 
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    };

    vector<vector<int>> f(m + 1, vector<int>(K + 1, 1e9));
    f[0][0] = 0; // f[i][j]: 以第 i 排为结尾，分为 j 个段的最优方案
    for(int i = 1; i <= m; i ++ ) 
        for(int j = 0; j < i; j ++ ) // 枚举上一段的结尾
            for(int k = 1; k <= min(i, K); k ++ ) // j + 1 ~ i 分一段
                f[i][k] = min(f[i][k], f[j][k - 1] + get_s(j + 1, j + 1, i, i));

    cout << f[m][K] << "\n";
}

int main(){
    ios;

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

    return 0;
}

F 方差

出题人：South_Orange

题意简述

给定 nn 个数，求最小的 xx 使得前 xx 个数中选 kk 个数方差最小值小于等于 TT

解题思路 （二分、数学）

二分答案位置，然后将该位置前的数组排序（排序后相邻的kk个数方差更优），然后遍历一遍，每次 O(1)O(1) 计算新的方差。

然后问题的关键在于怎么 O(1)O(1) 的计算方差。拆分方差的计算公式：

σ2=∑i=1k(vi−vˉ)2k=∑i=1kvi2−2vˉ∑i=1kvi+kvˉ2k\sigma^2 = \frac{\sum_{i=1}^k (v_i - \bar{v})^2}{k} = \frac{\sum_{i=1}^k v_i^2 - 2\bar{v} \sum_{i=1}^k v_i + k\bar{v}^2}{k}

对于 ∑i=1kvi2\sum_{i=1}^k v_i^2 可以预处理前缀平方和 O(1)O(1) 得到，对于 ∑i=1kvi\sum_{i=1}^k v_i 也是可以预处理前缀和 O(1)O(1) 得到，对于 vˉ\bar{v} 可以通过 ∑i=1kvik\frac{\sum_{i=1}^k v_i}{k} 得到。

对于无解的情况用二分的 check 函数特判一下右端点是否可行即可。

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
#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, k, t;
ll a[N];
double b[N], s[N], ss[N];

bool check(ll x)
{
	for (int i = 1;i <= x;i++) b[i] = a[i];
	sort(b + 1, b + 1 + x);
	for (int i = 1;i <= x;i++)
	{
		s[i] = s[i - 1] + b[i]; //前缀和
		ss[i] = ss[i - 1] + b[i] * b[i]; //平方前缀和
	}
	double fc = 1e18;
	for (int i = k;i <= x;i++)
	{
		fc = min(fc, (double)(ss[i] - ss[i - k] - 2 * (s[i] - s[i - k]) * (s[i] - s[i - k]) / k + k * (s[i] - s[i - k]) / k * (s[i] - s[i - k]) / k) / k); //方差计算
		if (fc <= t) return true;
	}
	return false;
}

void solve()
{
	cin >> n >> k >> t;
	for (int i = 1;i <= n;i++) cin >> a[i];
	if (!check(n))
	{
		cout << -1 << '\n';
		return;
	}
	ll l = k, r = n;
	while (l < r)
	{
		ll mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << '\n';
}

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

G 有序四元组

出题人：South_Orange

题意简述

给定一个含有nn个正整数的数组 {a1,a2,⋯ ,an}\{a_1, a_2,\cdots, a_n\}，求有多少个有序四元组 (i,j,k,l)(i, j, k, l) 满足 aia_i 是 aka_k 的因数且aja_j 是 ala_l 的因数，其中 i,j,k,li, j, k, l 互不相等。

解题思路 （容斥原理）

值域在 105{10}^5 以内，为了方便表示设值域 P=105P={10}^5。先开桶 txt_x 表示 xx 出现的次数。同时预处理出每个数编号不相等的因数个数 sxs_x 和倍数个数 bxb_x，时间复杂度为调和级数 O(Pln⁡P)O(P\ln P)。

考虑先算出 i≠ji\ne j 且 ai∣aja_i\mid a_j 的 (i,j)(i,j) 数量 mm，枚举较小数 xx，得 m=∑x=1Ptx×bxm=\sum_{x=1}^{P}t_x\times b_x。

有了以上问题的答案，平方一下就是 ai∣ak,aj∣ala_i\mid a_k,a_j\mid a_l 且 i≠k,j≠li\ne k,j\ne l 的 (i,j,k,l)(i,j,k,l) 组数，还需要容斥减去 i=j,i=l,k=j,k=li=j,i=l,k=j,k=l 的组数。

首先先减去满足一个条件的：

  • i=ji=j，较小数相等，枚举这个数 xx，取两个倍数，组数为 ∑x=1Ptx×bx2\sum_{x=1}^P t_x\times b_x^2。
  • k=lk=l，较大数相等，枚举这个数 xx，取两个因数，组数为 ∑x=1Ptx×sx2\sum_{x=1}^P t_x\times s_x^2。
  • i=li=l 或 j=kj=k，即一组中较大数与另一组中较小数相等。枚举相等的中间值 xx，取一个因数和一个倍数，组数为 ∑x=1P2(tx×bx×sx)\sum_{x=1}^P 2(t_x\times b_x\times s_x)。

还需要加上满足两个条件的：

  • i=ji=j 且 k=lk=l，此时两个较小数和两个较大数分别相等，组数即为最初求出的 (i,j)(i,j) 数量 mm。
  • i=li=l 且 j=kj=k，由于倍数的要求限制了 i≤k,j≤li\le k,j\le l，所以此时 i,j,k,li,j,k,l 均相等，枚举相等值 xx，组数为 ∑x=1Ptx(tx−1)\sum_{x=1}^Pt_x(t_x-1)。
  • 其他四种情况都会产生 i=ki=k 或 j=lj=l，与已经确定的条件 i≠k,j≠li\ne k,j\ne l 冲突，所以组数为 00。

之后满足三个或四个条件也会产生同样的冲突，组数均为 00，不用处理。

这样就做完了，但是由于 n4n^4 达到了 1020{10}^{20} 级别，开 __int128 才能确保通过。

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
74
75
76
77
78
79
80
#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;
ll a[N], cnt[N];
ll b[N], s[N];
__int128 m;

void print(__int128 x)
{
	if (x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}

void solve()
{
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i], cnt[a[i]]++;
	for (int i = 1;i <= 1e5;i++)
	{
		for (int j = i;j <= 1e5;j += i)
		{
			b[i] += cnt[j]; //倍数
			s[j] += cnt[i]; //因数
		}
		b[i]--; //减去自身
		s[i]--; //减去自身
		m += cnt[i] * b[i]; //满足i!=j且ai|aj的数量
	}
	
	__int128 ans = m * m;
	
	__int128 t = 0;
	for (int i = 1;i <= 1e5;i++)
		t += cnt[i] * b[i] * b[i]; // i == j
	ans -= t;
	
	t = 0;
	for (int i = 1;i <= 1e5;i++)
		t += cnt[i] * s[i] * s[i]; // k == l
	ans -= t;
	
	t = 0;
	for (int i = 1;i <= 1e5;i++)
		t += 2 * cnt[i] * s[i] * b[i]; // i == l 或 j == k
	ans -= t;

	ans += m; // i == j 且 k == l

	t = 0;
	for (int i = 1;i <= 1e5;i++)
		t += cnt[i] * (cnt[i] - 1); // i == l 且 j == k
	ans += t;

	print(ans);
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}
咏唱光芒 > YAC 扬州大学算法练习赛
#C++ #算法 #算法竞赛 #Luogu #YAC
2025 YAC Round 3 题解
https://marisamagic.github.io/2025/02/01/2025_YAC_3/
作者
MarisaMagic
发布于
2025年2月1日
许可协议