1740 Codeforces Round 831 (Div. 1 + Div. 2)
FallenGemini

碎碎念

昨天下午去打ACM模拟赛了,错过了下午的 Codeforces,于是今天上午补了一次 VP。
隔壁CCPC桂林站已经开打了,祝「基本无害」拿个金牌www

比赛

A.Factorise N+M (0:02)(497/500)

题意

给一个质数 ,找到一个质数
使得 不是质数

分析

时,一定不是质数

1
2
3
4
5
6
void solve()
{
int n;
std::cin >> n;
std::cout << n << '\n';
}

B. Jumbo Extra Cheese 2 (0:14)【956/1000】

题意

给若干个矩形,将这些矩形拼成一个多边形,要求每个矩形都有一条边在 轴上。
求这个多边形边长的最小值

分析

假定我们现在已经决定好第 个矩形在 轴上的那一条边长度为 ,平行于 轴的那一条边长度为

当我们把矩形按高度从小到大依次排列,最终的周长为 ,找不到一种更优的排列让周长更小。

接着考虑每一个矩形应该如何放置
为假定的最高值,满足
对于任意的矩形,假定它的边长 时,令长度为 的那条边为高,长度为 的那条边为底,对于整体周长的增加值 一定不会有更小的情况。

此时寻找 的具体值应该是多少。不难发现 就是边长中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve()
{
int n;
std::cin >> n;
std::vector<std::pair<int,int>> s(n);
for(int i = 0; i < n; i++)
{
std::cin >> s[i].first >> s[i].second;
if(s[i].first < s[i].second)
std::swap(s[i].first,s[i].second);
}
std::sort(s.begin(),s.end());
long long sum = 0;
for(auto x : s)
sum = sum + x.second;
sum = sum + s[n - 1].first;
sum = sum * 2;
std::cout << sum << '\n';
}

C. Bricks and Bags (0:54)【1141/1500,-2】

题意

个数字, 个盒子。
玩家 把数字任意放入每个盒子,使得每个盒子至少有一个数字。
玩家 从每个盒子中取出一个数字
记得分

已知玩家 的策略是最小化
的最大值

分析

考虑 号盒子中只有一个数字 的情况
此时玩家 需要把剩余 个数字分成两堆。
无论玩家 如何分这两堆数字,玩家 总能选择一个数字 ,满足对于任意的
于是玩家 的目标是最大化另一个数字产生的价值。也就是让玩家 在这一个盒子中没有其他选择除了选择这一个产生最大价值的数字,即盒子中只有一个数字。不难发现,这个数字要么是 个数字中的最小值,要么是最大值(此时不考虑边界冲突的问题,即假设最小值和最大值都是可以使用的状态)。

在这种情况下,不难发现被选择的这个数字 本身就是最大值或最小值时 最大。因为有一个完整的 (最大值 - 最小值) + (最大值-次大值 或 次小值-最小值),其余情况都是 (最大值 - 中间值 或 中间值 - 最小值) + |中间值 - 相邻值|

再考虑 号盒子中有 数字的情况,这 个数字要么是最小的 个数字,要么是最大的 个数字。
此时玩家 会选择 最小的数字中最大的那个 或 最大的数字中最小的那个。为了让这个数字与 号盒子还有 号盒子中的数字差值尽可能的小。
按照之前的策略,玩家 会把一个产生最大价值的数字单独放在一个盒子中,把剩余的数字全部放在另一个盒子中。

枚举,取最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve()
{
int n;
std::cin >> n;
std::vector<int> a(n);
for(int i = 0; i < n; i++) std::cin >> a[i];
std::sort(a.begin(),a.end());
int ans = 0;
for(int i = 0; i + 2 < n; i++)
ans = std::max(ans, a[i + 1] - a[i] + a[n - 1] - a[i]);
for(int i = n - 1; i - 2 >= 0; i--)
ans = std::max(ans, a[i] - a[i - 1] + a[i] - a[0]);
std::cout << ans << '\n';
}

D. Knowledge Cards (1:18)【1264/1750,-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
28
29
void solve()
{
int n,m,k;
std::cin >> n >> m >> k;
std::queue<int> q;
std::priority_queue<int> Q;
for(int i = 1; i <= k; i++)
{
int x;
std::cin >> x;
q.push(x);
}
while(k)
{
if(!Q.empty() && Q.top() == k)
{
Q.pop();
k--;
}
else if(Q.size() == n * m - 3) break;
else
{
Q.push(q.front());
q.pop();
}
}
if(k) std::cout << "TIDAK\n";
else std::cout << "YA\n";
}

E. Hanging Hearts (2:05)【1050/2000,-3】

题意

给一棵树,点权为 (点权未知)

每次选择一个叶子节点 ,将点权 加入一个队列
之后对于它的父亲节点 进行操作
删除节点

当整棵树被删掉后, 为队列 中最长不下降子序列的长度

点权是 的一个排列,求 的最大值

分析

考虑一条链的情况
只要将叶子节点的点权赋值为 ,最终的队列 就只包含数字

考虑根节点 个子节点
不难发现,无论如何都无法让 ,因为最初我们会选择点权较小的叶子节点 ,刷新根节点的点权 $a{root}’a_xya_y>a_x\cdotsa_x,a_y,\cdots,a{root}’a_{root}’ \le a_x < a_y<\cdotsscore = k$
即有多个子节点产生贡献的情况下,根节点无法产生贡献。

于是考虑对一棵子树 ,定义 表示这棵子树产生的最大价值是多少, 表示 节点不产生贡献的情况下,这棵子树产生的最大价值是多少。
,

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
std::vector<std::vector<int>> To;
std::vector<int> length,f,g;
void dfs(int u)
{
length[u] = 1;
int sum = 0;
for(int v : To[u])
{
dfs(v);
length[u] = std::max(length[u],length[v] + 1);
g[u] += f[v];
}
f[u] = std::max(length[u],g[u]);
}
void solve()
{
int n;
std::cin >> n;
To.resize(n + 1);
length.resize(n + 1);
f.resize(n + 1);
g.resize(n + 1);
for(int i = 2; i <= n; i++)
{
int u;
std::cin >> u;
To[u].push_back(i);
}
dfs(1);
std::cout << f[1] << '\n';
}

F. Conditional Mix

题意

个数字,去构成任意多个集合。
将集合的大小 当做元素放入一个 中,询问有多少种不同的

分析

表示在这 个数字中,数字 出现的次数。
因为我们不关心数字本身是几,只关心它出现了几次,于是将 从大到小排序。

不难发现,我们至少要构成 个集合,因为有这么多个数字,而它们不能放入同一个集合中
对于 ,我们可以在前 个集合中放入元素,再新开 个集合。
以此类推,如下图所示。

2022_10_30图

之后就是考虑如何计算有多少种不同的方案。
猜测是斯特林数,但好像又不是。

总结

表现分:1864

打的并不是很好

题连蒙带猜花了十分钟,直觉认为每个矩形都是大边与 轴平行
写博客时才差不多证明出来正确性

题思考了很久,前面都推的还好,写挂了两次才发现 号盒子可能有多个数字
推广到 个数字时才发现只取一个数字时,那个数字要么是最大值要么是最小值
于是 个数字也应该是最大或最小的

题题意一开始理解错了,以为棋盘上的点都可以叠放成栈
然后想到了华容道
写挂了一次,判断边界是写成了 ,这种情况下刚好把棋盘填满,棋子是无法移动的。

题开始没怎么读懂题目,看样例给的图发现就是一棵树,每次选叶子节点。
能感觉到是树形
第一次只考虑了根节点分叉的情况,也就是第二层节点中最长链之和。过了五个点,感觉方向是对的
第二次和第三次写的代码有点混乱,现在重新看也没理出什么思路,也是挂在第六个点。
最后定义出 状态方程
推导公式的时候也有点想当然,于是写博客时重新推导了一下,从特例出发到普遍情况汇总

题看到 的范围是 感觉可做,看了下 花了五分钟过了这道题。
应该思考一个小时能想出来,虽然思考四十分钟比赛就结束了,或许是什么数学上的算法我还没学过吧

状态不是很好,下周估计不会打比赛,准备期中考试了。