CF341E Candies Game 题解

zrl123456 · 2025-11-12 10:01:54 · 题解

:::::info[题目基本信息] 考察：构造（3000）。
题目简介：
给定非正整数序列 \{a_n\}，有操作：

• 选择 x,y\in[1,n]，使得 a_x\le a_y，同时令 a_y\leftarrow a_y-a_x,a_x\leftarrow 2a_x。

要求一系列操作完成后序列中恰好有两个数非 0，要求构造一组操作，操作数不得超过 10^6，无解给出 -1。
数据范围：

• 1\le n\le 1000
• 0\le \sum a_i\le 10^6

  ::::: 显然，操作不会使序列中 0 的个数减少，同时也不会使 0 的个数一次性减少的个数超过 1，所以在序列非 0 个数小于 2 时便无解。
  我们先考虑让两个数来回操作的情况，但是这样很快就寄了，比如我们无法通过操作把 1,2 两个数中的一个变为 0。
  那我们再考虑 3 个数内部操作，我们先考虑特殊情况。
  钦定操作的三个数为 a_x.a_y,a_z，且 a_x\le a_y\le a_z。
  容易发现，在 a_x\mid a_y 时，我们可以通过对于 k=\dfrac{a_y}{a_x} 二进制下的从低到高的每一位进行分讨（设目前处理到了第 i 位）：

• 当第 i 位为 1 时，操作 (x,y)。
• 当第 i 位为 0 时，操作 (x,z)。

这时我们就能把 a_y 清空成 0，且由于 a_z 的减少量小于 a_y 的减少量，故 a_z 不会被清零，这样我们就将一个数清为 0 了。
但是在 a_x\nmid a_y 时又该如何呢？
令 p=a_y\bmod a_x，最终 a_y\leftarrow p，这时将 a_x,a_y,a_z 重新排序 a_y 一定会被被排序到 a_x 的位置上，成为 a'_x，这时 a'_x=p<a_x，那么这样下去早晚会产生 0。
这样我们就有了一种构造方案，现在我们来观察一下复杂度。
容易发现，令 a_x\leftarrow a_y\bmod a_x 的一轮操作构造复杂度为 \Theta(\log V) 次。同时由于有结论（下文钦定 a\ge b）：

:::::success[证明] 当 b>\dfrac{a}{2} 时，a\bmod b=a-b<a-\dfrac{a}{2}=\dfrac{a}{2}。
当 b\le\dfrac{a}{2} 时，a\bmod b<b\le\dfrac{a}{2}。
::::: 这样轮数大概是在 \Theta(\log V) 量级的，但是这个东西和辗转相除法等价在哪？？？？故本人目前不会严谨的证明。
这样构造复杂度大约是在 \Theta(n\log^2 V) 的，反正能过。
时间复杂度为 \Theta(n\log^2 V)，空间复杂度为 \Theta(n)。

code