Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2) A-F1

· · 题解

A

给定 a,b，找到最小整数 m 满足 m \bmod a = m \bmod b。

考虑答案是 n，那么 n - n \bmod a 就是一个小于等于 n 的答案。

所以，答案就是 lcm(a,b)。

B

给定长度为 n 的二进制数列，你单次操作可以选择一个长度为 k 的子区间，将这个子区间的所有数变为 1，要求最终没有长度大于等于 m 的全 0 子区间，求最少操作次数。

从前往后扫，遇到一个点长度达到 m 了，就从这个点开始操作一次，显然最优的。

C

有一个 n\times m 的矩阵，每个矩阵格子都指向一个相邻的格子。

一部分格子的指向已经确定，问在最优操作方案下，能到达环的格子数量最多是多少个？

先考虑那些已经确定方向的格子。

对于一个这样的格子， dfs 一下，如果最终到达的点是未确定方向的格子，或者回到了起点，那么这个格子就是可以在环里面的，这个结论很容易发现并证明。

对于未确定方向的格子，只要这个未确定格子所在的同类型的格子的连通块大小大于等于 2，或者连着一个能达到环的格子，那么这个未确定格子连通块内的所有格子都可以计入答案，这也比较显然。

上述结论都需要画图证明，就先不画图了。

D

题意

给定一个长度为 n 的整数数组，值域 [0,2]，仅允许差的绝对值为 1 的数交换位置。

要求构造一组操作方案使得操作次数小于等于 n，且最后数组单调不降。

保证至少存在一个 1。

不要求最小化操作次数，可以证明一定存在合法方案。

做法

考虑按照升序结果划分为 3 个前后连接的部分，分别代表 0 的位置区间，1 的位置区间，2 的位置区间。

考虑最简单的方式：

首先考虑 0 区间，先把里面的 1 换出去。

然后，考虑 0 区间里面的 2，注意到每个 2 需要两次操作才能交换出去。

此部分的最大代价为 2\min(cnt_0,cnt_1+cnt_2)。

操作完之后，0 区间已经搞定了，1 区间还有一部分 2，2 区间还有一部分 1，交换一下就可以了。

此部分的代价为 \min(cnt_1,cnt_2)。

vp 赛时随机了 10^5 组数据没出错，提交就过了。

赛后参考了洛谷第一篇题解，证明一下正确性。

总代价 2\min(cnt_0,cnt_1+cnt_2)+\min(cnt_1,cnt_2)。

注意到原数组 0,2 交换之后操作次数也是一样。

那么令 cnt_0 \le cnt_2。

总代价为 2cnt_0+\min(cnt_1,cnt_2) \le cnt_0+\max(cnt_1,cnt_2)+\min(cnt_1,cnt_2)=n

E

题意

给定正整数 n,k。
要求构造 k 个不同的长度为 n 的排列，使得每个位置在 k 个排列的总和是相同的。 显然最后每个位置的总和是确定的。

解法

无解比较好判定，这里不记录。

如果 k 是偶数，那么只需要两两配对就可以了。

如果 k 是奇数，那么必然存在一个三元组满足要求。

三元组的构造可以先固定第一个排列为 1,2,\cdots,n。

每个位置的值总和是 \frac{3(n+1)}{2}，令 m=\lfloor \frac{n}{2}\rfloor，那么它可以表示为 3m+3

然后，第二三排列的第一个位置临时固定为 m+1,2m+1。

随后模拟一下大概就得出来了。

F1

没来得及写代码，以后再补。