P7971 [KSN2021] Colouring Balls

Natsume_Rin · 2021-11-28 11:19:54 · 题解

入 OI 以来做的第二道交互题。

题目传送门

题意简述

有 n 个颜色未知的球，你现在可以通过 Q 次询问，每次询问一个区间 [l,r] 中球的颜色数，需要你确定最后的所有球的颜色异同。

数据范围 n \leq 1000，2000 \leq Q \leq 10000，Q 的范围与子任务特性有关。

一般性解法

先可以不考虑子任务，考虑 n=1000,Q=10000 时怎么做。

首先我们可以从 n 号球推到 1 号球，假设当前的颜色已经出现了 k 个不同的，分别为 c_1,c_2,c_3\dots c_k，它们出现的 最靠前的位置 分别为 p_1,p_2,p_3\dots p_k，满足 p 序列升序。

那么假设当前需要求解 i 号球，那么在 [1,k] 中二分一个 p_{mid}，可以自行想象一下，如果询问区间 [i,p_{mid}]，得到的结果是 res，如果

• 好吧，其实没有第三种情况了。

最后就可以通过二分得到答案。这里举一个 col=[1,3,2,2,2,1] 的例子求解 col_1 以便大家理解。

• 当前 c=[3,2,1]，p=[2,3,6]，二分左右端点为 [1,3]。
• 最后更新 c=[1,3,2]，p=[1,2,3]。

这样需要询问 n \log_2 n，实测可以通过 Q=10000 的子任务。

数据分治

不知道正解是否需要，但是我的需要。

• T=2

颜色段连续，所以对于每一个球 i，只需要询问 [i,i+1] 即可知道异同关系。询问次数为 n-1。

• T=3

照常做，用一般性解法，询问次数大约为 2n-2。

• T=5

每次询问区间 [i,n]，如果 res_{i,n}=res_{i+1,n}，那么就二分，否则就是新颜色，询问次数大约为 n+\log_2 n。

• T=4

有点意思。

当颜色数为 4 时，那么就不可能出现新颜色。一个可能二分的过程是这样的。

你会发现这样子每一个球会询问 3 次，总询问次数约为 3n 无法通过。

怎么优化呢？

突破口就在于 不可能出现新颜色，所以当二分区间 [l,r] 满足 l=r 且颜色数为 4 时，那么 col_i=c_l，因为 只有这一种颜色可选，又不可能出现新颜色。这样就可以将询问次数降到 2n 级别，可以通过。

放在最后

很好的一道题。我才不会告诉你我做了很久。 代码就不放了（太丑了）。

完结撒花。