IOI 2024 题解选贺

· · 题解

nile

题意：有 N 个物品，每个物品有属性 A_i,B_i,W_i，保证 B_i \le A_i。你每次可以把一个物品运走，花费 A_i，或者把两个物品一起运走，花费 B_i+B_j。一起运走的两个物品必须满足 |W_i-W_j| \le D。Q 次询问，每次询问给定 D 问最小代价。

没有天天爱打卡难。

注意到形成的匹配一定不会相交或包含，然后又发现按照 W 排序之后 i 和 j 匹配仅当 |i-j| \le 2。于是容易设计 DP。多组询问 DDP 即可。

message

题意：通信题。有一个长度为 S=1024 的 01 串，A 要把它传给 B。A 可以传递 Q=66 次，每次可以传一个长度为 31 的 01 串。交互库会对其中的 15 位作修改（可以不改，且交互库自适应），然后传给 B。交互库每次修改的位置集合相同，且 A 知道 B 收到的修改后的串是什么。

我靠这咋想到的。

设 a_{i,j} 代表第 i 位第 j 次传的值。

考虑把所有位置放到一个环上，对每个好的位置 i 找到下一个好的位置，记它们之间的距离为 d，就令 a_{i,j}=0（j<d），a_{i,d}=1。这样完事之后对每一列找到第一个 1。如果这是一个好的位置，那么我们知道下一个好的位置在哪，如果这是一个坏的位置，它会连向一个神秘地方。把这棵基环森林连出来，发现只有恰好一个大小为 16 的环，这就是所有好的位置。这样我们只花费了 31 个 bit 就传给了 B 所有好的位置，接下来再花 1024 个 bit 传就完了。

但是其实没完，观察原题面发现 S 不是恰好 1024 位而是 S \le 1024，所以其实要 1025 个 bit，但是问题不大还是能过。

tree

题意：有一棵有根树，每个点有点权 W_i，Q 次询问，每次询问给定 L,R，你需要给每个点赋整数点权 X_i，满足每个点子树内点权和在 [L,R]，且 \sum|X_i| \times W_i 最小。

这咋做啊？

hieroglyphs

题意：给定两个长度为 N \le 10^5 的序列，值域为 2 \times 10^5。求一个公共子序列使得所有公共子序列都是它的子序列，或者报告无解。

mosaic

题意：给定一个 N \times N（N \le 2 \times 10^5）的 01 矩阵的第一行和第一列，对于剩下的格子，如果上方左方相邻的格子都是 0 它就是 1，否则它就是 0。Q \le 2 \times 10^5 次询问，每次给一个子矩阵求里面 1 的数量。

注意到迭代很少次之后就满足：一条对角线上的值一样。后面的部分是简单的。

sphinx

题意：交互题。N \le 250 个点的连通图，你知道图的形态，每个点的颜色在 [0,N-1]，你不知道点的颜色。你可以作不超过 2750 次询问，每次询问你改变一些点的颜色，可以改成 N。交互库返回同色连通块的数量，询问之间独立。求每个点的颜色。交互库不是自适应的。