A4702 | [CSP-S 2024] 染色

【样例 1 解释】

对于第一组数据，以下为三种可能的染色方案：

1. 将 $A_1, A_2$ 染成红色，将 $A_3$ 染成蓝色（$\red{1}\red{2}\blue{1}$），其得分计算方式如下：

• 对于 $A_1$，由于其左侧没有红色的数，所以 $C_1 = 0$。
• 对于 $A_2$，其左侧与其最靠近的红色数为 $A_1$。由于 $A_1 \neq A_2$，所以 $C_2 = 0$。
• 对于 $A_3$，由于其左侧没有蓝色的数，所以 $C_3 = 0$。
该方案最终得分为 $C_1 + C_2 + C_3 = 0$。
2. 将 $A_1, A_2, A_3$ 全部染成红色（$\red{121}$），其得分计算方式如下：
• 对于 $A_1$，由于其左侧没有红色的数，所以 $C_1 = 0$。
• 对于 $A_2$，其左侧与其最靠近的红色数为 $A_1$。由于 $A_1 \neq A_2$，所以 $C_2 = 0$。
• 对于 $A_3$，其左侧与其最靠近的红色数为 $A_2$。由于 $A_2 \neq A_3$，所以 $C_3 = 0$。
该方案最终得分为 $C_1 + C_2 + C_3 = 0$。
3. 将 $A_1, A_3$ 染成红色，将 $A_2$ 染成蓝色（$\red{1}\blue{2}\red{1}$），其得分计算方式如下：
• 对于 $A_1$，由于其左侧没有红色的数，所以 $C_1 = 0$。
• 对于 $A_2$，由于其左侧没有蓝色的数，所以 $C_2 = 0$。
• 对于 $A_3$，其左侧与其最靠近的红色数为 $A_1$。由于 $A_1 = A_3$，所以 $C_3 = A_3 = 1$。

该方案最终得分为 $C_1 + C_2 + C_3 = 1$。

可以证明，没有染色方案使得最终得分大于 $1$。

对于第二组数据，可以证明，任何染色方案的最终得分都是 $0$。

对于第三组数据，一种最优的染色方案为将 $A_1, A_2, A_4, A_5, A_7$ 染为红色，将 $A_3, A_6, A_8$ 染为蓝色（$\red{35}\blue{2}\red{51}\blue{2}\red{1}\blue{4}$），其对应 $C = [0, 0, 0, 5, 0, 1, 2, 0]$，最终得分为 $8$。

【样例 2】

见选手目录下的 color/color2.in 与 color/color2.ans。

【数据范围】

对于所有测试数据，保证：$1\leq T\leq 10$，$2\leq n\leq 2\times 10^5$，$1\leq A_i\leq 10^6$。

附件下载

color.zip