2024 YAC Round 11 题解

A 玩弄人形的少女

出题人：MarisaMagic

题意描述

分别统计字符串 “shanghai”“\text{shanghai}” 和 “penglai”“\text{penglai}” 的个数 「YAC Round 11」玩弄人形的少女

解题思路

开一个 map 直接统计即可，或者写判断语句分别统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

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

void marisa(){
    unordered_map<string, int> mp;
    int n; cin >> n;
    for(int i = 0; i < n; i ++ ){
        string s; cin >> s;
        mp[s] ++ ;
    }
    cout << mp["shanghai"] << ' ' << mp["penglai"] << "\n";
}

int main(){
    ios;

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

    return 0;
}

B 魔法学徒KKK的试炼

出题人：South_Orange

题意描述

工作日获得 aa 点魔力值，双休日获得 bb 点魔力值。判断魔力值达到 nn 题需要多少天。「YAC Round 11」魔法学徒 KKK 的试炼

解题思路 (模拟)

先求出一周能获得多少魔力值。再求出需要几个完整的星期，还剩多少魔力值未获得。

  • 如果剩的魔力值在工作日能获得完，就加上需要的天数。
  • 否则，先加上工作日的 55 天，再加上双休日需要的天数。
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
#include <iostream>
using namespace std;

typedef long long ll;

ll a, b, n;

int main()
{
    LL res = 0;
    cin >> a >> b >> n;
    res = n / (5 * a + 2 * b) * 7; // 完整的周数*7
    n %= (5 * a + 2 * b); // 剩余的魔力值
    if (n != 0)
    {
        if (n < 5 * a) // 工作日能完成
        {
            if (n % a != 0) res += n / a + 1;
            else res += n / a;
        }
        else // 工作日不能完成
        {
            res += 5;
            n -= 5 * a;
            if (n % b != 0) res += n / b + 1;
            else res += n / b;
        }
    }
    cout << res << endl;
    return 0;
}

C 社交媒体

出题人：South_Orange

题意描述

如果一个人同时是评论者与被评论者的好友则可以看到这条评论，判断最多添加两个新好友后能看到的最多的评论数量。「YAC Round 11」社交媒体

解题思路 (思维)

如果暴力枚举所有未加的好友时间复杂度为O(N2)O(N^2)，会超时。

考虑到只有出现过的才值得枚举，这样最多只需要枚举mm对，时间复杂度降为O(N)O(N)

先预处理出来添加第ii个人后能增加的评论数zhi[i]zhi[i]，再预处理出来添加两个人 i,ji,j 时增加的评论数 mp[i,j]mp[{i,j}] (此评论数不包含添加他们中单个人时所增加的评论数),最后枚举每一对评论，以及不添加任何人能看到的初始评论数 resres，答案:

ans=max⁡(ans,res+max⁡(mp[i,j]+zhi[i]+zhi[j]))ans = \max(ans,res + \max(mp[{i,j}]+zhi[i]+zhi[j]))

然后再考虑要选的两个人并没有相互评论过的情况，zhi[i]zhi[i] 最大值为 mxmx，次大值为 cimxcimx

ans=max⁡(ans,res+mx+cimx)ans = \max(ans,res + mx + cimx)

最后注意评论者与被评论者是同一个人的情况

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
81
82
83
84
85
86
87
88
89
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>

using ll = long long;
using pii = pair<int, int>;

const int N = 2e5 + 10;

int n, k;
int m;
int a[N], b[N];

void solve()
{
	set<int> se;
	map<pii, int> mp;
	cin >> n >> m >> k;
	vector<int> zhi(k + 1);
	for (int i = 1;i <= n;i++)
	{
		int t;
		cin >> t;
		se.insert(t);
	}
	int ans = 0;
	int res = 0;
	for (int i = 1;i <= m;i++)
	{
		cin >> a[i] >> b[i];
		if (a[i] > b[i]) swap(a[i], b[i]);

		if (a[i] == b[i])
		{
			if (!se.count(a[i])) zhi[a[i]]++;
			else res++;
		}
		else
		{
			if (!se.count(a[i]) && se.count(b[i])) zhi[a[i]]++;
			else if (se.count(a[i]) && !se.count(b[i])) zhi[b[i]]++;
			else if (se.count(a[i]) && se.count(b[i])) res++;
			else mp[{a[i], b[i]}]++;
		}
	}
	for (int i = 1;i <= m;i++)
	{
		if (a[i] == b[i])
		{
			if (!se.count(a[i])) ans = max(ans, res + zhi[a[i]]);
		}
		else
		{
			if (!se.count(a[i]) && !se.count(b[i]))
				ans = max(ans, res + mp[{a[i], b[i]}] + zhi[a[i]] + zhi[b[i]]);
		}
	}
	int mx = 0, cimx = 0;
	for (int i = 1;i <= k;i++)
	{
		if (zhi[i] > mx)
		{
			cimx = mx;
			mx = zhi[i];
		}
		else if (zhi[i] > cimx)
			cimx = zhi[i];
	}
	ans = max(ans, res + mx + cimx);
	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;
}

D 梦违科学世纪

出题人：MarisaMagic

题意描述

给定一个图，每个点有一个值 aia_i，可以花费 a[u]+a[v]a[u] + a[v] 代价构建一条 u→vu \rightarrow v 的边。求使得存在任意两点 u,vu, v 可以互相到达的最小代价。「YAC Round 11」梦违科学世纪

解题思路

如果图中本来就存在环，那么我们无需构建任何边。此时最小代价为 00;

如果不存在环，那么该图为一个有向无环图。考虑进行拓扑排序，并在拓扑排序中进行动态规划维护最小值。设 dp[u]dp[u] 表示所有能到达 uu 的点 vv 中 a[v]a[v] 的最小值，因此只需要在拓扑排序的过程中找到 min⁡(u→v)∈Edp[u]+a[v]\min_{(u\rightarrow v) \in E} dp[u] + a[v] 即可。

当然，图可能不连通，可能 a[u]a[u] 最小的两个点互相不可达，我们还需考虑凭空构造这两个点之间的环所需的代价。

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
#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 = 5e5 + 10;
const ll INF = 2e9;

vector<int> e[N];
int n, m, ind[N], a[N];
ll mn1 = INF, mn2 = INF, ans = INF;
int dp[N];  // dp[u]表示可以到达u的点中结界强度的最小值

void topo(){
    queue<int> q;
    for(int i = 1; i <= n; i ++ ){
        dp[i] = a[i];
        if(!ind[i]) q.emplace(i);
    }

    while(q.size()){
        int u = q.front();
        q.pop();

        for(const auto &v : e[u]){
            ans = min(ans, (ll)dp[u] + a[v]); // v -> 到达u的最小值点
            dp[v] = min(dp[v], dp[u]); // 更新到达v的点中的结界强度最小值
            if(!( -- ind[v])) q.emplace(v);
        }
    }

    for(int i = 1; i <= n; i ++ ) if(ind[i]) ans = 0; // 本来就存在环
}

void marisa(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){  // 找到最小和次小值
        cin >> a[i];
        if(a[i] <= mn1) mn2 = mn1, mn1 = a[i];
        else if(a[i] < mn2) mn2 = a[i];
    }
    ans = (mn1 + mn2) << 1;  // 凭空构造一个环的情况

    for(int i = 1, u, v; i <= m; i ++ ){
        cin >> u >> v;
        e[u].emplace_back(v);
        ind[v] ++ ;
    }

    topo();

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

int main(){
    ios;

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

    return 0;
}

E 秘银之塔

出题人：South_Orange

题意描述

给定 NN 个整数 A1.A2,⋯ ,ANA_1.A_2, \cdots, A_N 中选出两个进行异或计算，得到的结果最大是多少？「YAC Round 11」秘银之塔

解题思路 (01 trie树)

首先 O(N2)O(N^2) 模拟肯定会 TLETLE。

字典树：
字典树（trie 树）是一种用于实现字符串快速检索的多叉树结构。
trie 树的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符 c，就沿着当前节点的 c 字符指针，走向该指针指向的节点。

上文提到，用枚举肯定超时。
考虑运用字典树对其进行优化。

优化方法：
把每一个数字转换成二进制的0101字符串插入字典树，再依次遍历整棵字典树。
遍历的时候我们该注意什么？该选择哪一条分支遍历下去？
选择：因为异或运算是相同为00，不相同为11，所以我们考虑贪心，即这一位尽量为11。

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
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>

using ll = long long;

const int N = 1e5 + 10;

ll son[N * 31][2], a[N];
ll idx;
int n;

void insert(ll x)
{
	ll p = 0;
	for (int i = 31;~i;i--) // 拆位插入字典树
	{
		ll& s = son[p][x >> i & 1];
		if (!s) s = ++idx;
		p = s;
	}
}

ll query(ll x)
{
	ll res = 0, p = 0;
	for (int i = 31;~i;i--)
	{
		ll s = x >> i & 1;
		if (son[p][!s]) // 尽量选择与当前位不同的路径
		{
			res += 1ll << i;
			p = son[p][!s];
		}
		else p = son[p][s];
	}
	return res;
}

void solve()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		cin >> a[i];
		insert(a[i]);
	}
	ll res = 0;
	for (int i = 1;i <= n;i++)
		res = max(res, query(a[i]));
	cout << res << '\n';
}

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

F 活泼纯情的数学家

出题人：MarisaMagic

题意描述

删去 1,2,…,91, 2, \ldots, 9 之间的某个数字 xx，求数 nn 在删去数字 xx 的情况下在自然数中排在第几位。「YAC Round 11」活泼纯情的数学家

解题思路

先考虑 x=9x = 9 的情况。如果删除的是 99，那么 88 之后是 1010，8888 之后是 100100，188188 之后是 200200。不难发现，这其实就是 “逢九进一”，也就是说新的自然数列是九进制数。因此我们只需要把 nn 看作是九进制数，然后转换为十进制数就是答案。

再考虑 x≠9x \not = 9 的情况。我们可以将所有大于 xx 的数位都减 11，小于等于 xx 的数位保持不变，此时也可以把新的数列看成九进制数。因此同样将 nn 转换成十进制数即可。

注意：自然数包括 00，因此最后答案需要 +1+1。

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
#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 s; int x; cin >> s >> x;
    for(auto &c : s) if(c - '0' > x) c -- ; // 大于x的数字--

	// 看作九进制数，转换为十进制数即为其排名
    ll ans = 0, pro = 1;
    for(auto it = s.rbegin(); it != s.rend(); it ++ ){ // 反向遍历
        ans += (*it - '0') * pro; 
        pro *= 9;
    }
    cout << ans + 1 << "\n";  // 自然数包含0，最后需要+1
}

int main(){
    ios;

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

    return 0;
}
咏唱光芒 > YAC 扬州大学算法练习赛
#C++ #算法 #算法竞赛 #Luogu #YAC
2024 YAC Round 11 题解
https://marisamagic.github.io/2024/12/14/YAC_Round_11/
作者
MarisaMagic
发布于
2024年12月14日
许可协议