本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-12 21:23:18

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

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