UCupF 验题记录 | 我的精神状态也是 IDK 了

· · 个人记录

省流:过了 IKD。

I

\texttt{A}\texttt{B} 中出现次数更多的出现了 L 次,先跳过 \max(0,\left\lfloor \dfrac ML\right\rfloor-1) 轮,然后再暴力模拟几轮即可。注意有可能不到 \left\lfloor \dfrac ML\right\rfloor 轮:若 L 整除 M 且在这一轮还没结束的时候已经拿到了 M 分的情况。(因为这个挂了一发)

K

首先考虑无解的情况。如果原来两序列就相等那不需要操作,否则至少要做一次操作。首先如果序列弄出 0 就倒闭了,因为 0 变不了。所以所有数都是整数,那乘 x 肯定 \ge x,模 x 肯定小于 x,那 b 肯定得有不同的数,所以判掉 b 全相等的情况。

考虑这个 2n+10,那肯定是先尽量用两次操作把 n 减小 1。那假如用一个数 x 去弄 y,目标是 z,先不管。那可以选一个质数 p,令 y\gets yr\bmod p。这样 x\gets p(x\bmod r),为了避免 x 变成 0 我们可以让 r 大于值域,也就是 r=(y^{-1}z\bmod p)+p。但是这个时候有两个问题,一个问题是 x 变成 Vp 级别了,这个不要紧,每次拿一个 V 级别的数弄一个 Vp 级别的数就行,这样弄到最后留下来两个不同的 b 的数时,一个是用过的 Vp 级别的数,一个是没有用过的 V 级别的数。但是你发现 x 变成 p 的倍数了,没有逆元,那你换一个质数 q,两个质数轮流用就行。这里选取了 p=361\, 425\, 017,q=314\, 652\, 017。它们满足 10^8<p,q<5\times10^8

那剩下的问题是有一个 Vp 级别和 V 级别的数要变成两个不一样的数,要用 14 步搞定。这个信息量太多了,考虑把它们变成一个确定的状态再变成目标状态。我们能想到的最简单的状态就是 1\, 2

那首先按照刚才的做法,用两步Vp 级别的那个数变成 1,另一个数变成 Vp 级别的东西。这里如果另一个数是 V 的量级是好做的:1,2k\xrightarrow{2k-1}2k-1,1\xrightarrow{2}1,2。当然如果一开始是 1,2 就不用做,这里最多花两步。但是是 Vp 级别的话我们就不能这么干,考虑先把他变小。那我们随便取一个奇数 r,假如 r 不是 x 的因数,就可以 1,x\xrightarrow{r}r,x\bmod r\xrightarrow{2}1,2(x\bmod r),显然 r 不会很大。这里有用了两步,所以这一部分我们一共用了六步。

考虑怎么把 1,2 变成目标状态。先考虑假如目标状态是 1,x,那么可以有 1,2\xrightarrow{k}1,2k\xrightarrow{2k-1}2k-1,1,这里最多花两步。然后考虑如果是 x,y,其中 x<y,那么先变成 1,x,然后 1,x\xrightarrow{y}y,x 即可。这里多花了一步,一共三步

但是我们刚才的讨论好像都当成无序了,所以我们还有 14-6-3=\mathbf 5 步的空间来交换 1,22,1。这是容易的:1,2\xrightarrow3 3,2\xrightarrow4 3,8\xrightarrow7 21,1\xrightarrow5 1,5\xrightarrow2 2,1。这样我们就做完了。

D

考虑如果能构造出最大的,因为黑色最多形成一个环(首先禁止了四元环,然后剩下的环必须围住了唯一一个白色连通块),所以一个一个删就行。注意 n=1 时要判一下,否则从叶子开始删(显然,叶子一定与白色相连,所以删了之后白色还是连通的),剩下一个大环从边开始向两边删就行。

不妨设 n<m。首先 n=1 是容易讨论的,n=2 也不难,用 C 表示给定的位置,分 C 在不在角落上,无非就是

C......#
########

#...C..#
########

状物。

否则,n,m\ge 3,先不考虑钦定为白色的那个位置构造一个最大的解。那这个解根据 n 的奇偶性分类,是

##########
#........#
########.#
#........#
########.#
#........#
##########

##########
#........#
########.#
#........#
########.#
#........#
#.#.#.#..#
##########

状物

这个猜出来是容易的,因为一个直觉是考虑四个格子里面有一个白格子,这些格子还要连起来,那得是一个生成树状物。

考虑钦定的点在中间的情况。对于 n 为偶数,上下翻转,这样要么奇数行全空要么偶数行全空。对于 n 为奇数,如果它在的位置是黑的,可以考虑把黑格调整到行末,也就是

##########
#........#
####C#####
#........#
########.#
#........#
##########

状物。

对于钦定的点在边上的情况,这下不得不删了。但是如果它到中间还有连着的话,那就变成多个连通块了。所以要钦定它同一行相邻的点是空的。

对于钦定的点在角上的情况,这下得删两个。把它和它相邻的点删了就行。