【题解】B. Gellyfish and Camellia Japonica

· · 题解

B. Gellyfish and Camellia Japonica

题意

最开始有个未知的序列 a，每次操作有三个参数 x,y,z，代表将 a_z 赋值为 \min (a_x,a_y) 现已知操作完的序列 b 和每次操作的三个参数，构造一种合法的序列 a，无解输出 -1。

思路

我们考虑从最后一个询问倒着往前推，对于最后一个询问，这里记作 x,y,z，我们知道 b_x,b_y \ge b_z，这个条件是必要的，即无法从 b_x,b_y \ge b_z 向 b_z= \min(b_x,b_y) 推导，之后我们考虑递归解决问题，我们考虑只差最后一步的操作没做的 b' 数组，有 b'_z 是可以任取的，因为只需要保证 \min(b'_x,b'_y)=b_z 即可，注意此处是 b_z 而非 b'_z。我们注意到一定有 b'_x=b_x \ge b_z,b'_y=b_y \ge b_z，我们注意到对于任意的 a_i，其都得满足他比他所更新的 z 要更大，我们记录对于 a 的限制数组为 c。

但上述还是一个必要条件，可证 b_z= \min (b_x,b_y) 的充要条件是 b_x,b_y \ge b_z，b_x,b_y 当中至少有一个等于 b_z。我们考虑怎样取数最优，因为 a_i 无法取 c_i 以下的数，而 c_i 又一定是曾经的一个 b_z 而在 c_i 以上就不会存在另外一个曾经是 b_z 的数，因此 a_i 取 c_i 一定最优，之后倒着模拟一边判断其是否合法即可。

代码

Submission-322597568