会议难题 题解

思路

先把区间按右端点从小到大编号为 $1,2,\ldots,n$。对科学家 $i$，记 $S_i$ 为所有与其相遇的科学家的已知国家集合，并额外用 $0$ 表示其中存在国家未知者。

若 $0\notin S_i$，科学家 $i$ 是否不高兴已经确定：当 $S_i$ 恰含一个国家时计入答案，否则不计入。若 $0\in S_i$ 且其中至少出现两个已知国家，无论怎样指定未知国家，$i$ 都不可能不高兴。剩余候选只有两类：$S_i=\{0\}$，或 $S_i=\{0,c\}$。

我们还需要判断一批候选能否同时变得不高兴。若候选 $i$ 被选中，则所有与 $i$ 相遇的未知科学家必须使用同一个国家：对于 $S_i=\{0,c\}$，这个国家只能是 $c$；对于 $S_i=\{0\}$，可以任选一个国家。同一批互相牵连的候选必须选择同一国家，而互不牵连的批次可以独立处理。

做法

对每个 $i$，令 $f_i$ 为与 $i$ 相遇的科学家中编号最小者。再定义

区间按右端点排序后，$h_i$ 是包含候选 $i$ 的最左侧相关位置。若某一批候选的最后一个位置是 $i$，则这批的起点 $k$ 必须满足 $k\le h_i$；批内的所有候选都能统一选为同一个国家，批前 $1\ldots k-1$ 与它独立。

用 $F_i$ 表示只考虑前 $i$ 个位置时，可选候选的最大数量。扫描 $i$，维护计数 $A_{c,x}$：已经出现、要求国家为 $c$ 且 $h=x$ 的候选数；$A_{0,x}$ 表示国家可自由选择的候选。

• 若 $S_i=\{0,c\}$，把它加入 $A_{c,h_i}$；枚举起点 $k$，批内贡献为所有 $x\ge k$ 的 $A_{0,x}+A_{c,x}$，转移到 $F_i$。
• 若 $S_i=\{0\}$，把它加入 $A_{0,h_i}$；再枚举国家 $c\in[1,200]$ 和起点 $k$，使用同样的转移。
• 任何位置都可不作为新批次的末尾，因此先令 $F_i=F_{i-1}$。

最后把已确定不高兴的科学家数量加上 $F_n$。

子任务 1 可以枚举所有未知科学家的国家等价类，再直接检查答案。子任务 2 没有未知国家，直接两两判断。子任务 3 的每个相交图连通分量都是团，即该分量的所有区间有公共点；不同分量独立，分量内已知国家数不超过一个时整组都能不高兴。

正确性证明

首先，$S_i$ 不含 $0$ 时没有可修改国家，恰有一个已知国家当且仅当 $i$ 遇到的所有人同国；含至少两个已知国家时必然遇到异国人。若 $S_i$ 含 $0$ 和至少两个已知国家，同样不可能通过给未知者赋值消除异国相遇。因此分类完整且正确。

对其余候选，令它不高兴等价于把其所有未知邻居都指定为唯一允许的国家；若没有已知国家，这个国家可以任选。相互重叠的这些要求会传递合并为一个批次。按右端点排序后，一个以 $i$ 为最右端的批次恰覆盖某个后缀段 $[k,i]$，而 $k\le h_i$ 正是该批次包含所有传递相交位置的条件。因此，固定批次国家为 $c$ 时，$A_{0,x}$ 与 $A_{c,x}$ 且 $x\ge k$ 的候选恰好全部可选，其他国家的候选恰好不可选。

转移 $F_{k-1}$ 加上该批贡献，把最后一个批次与此前最优方案拼接；反之，任一可行方案按最后一个批次分割，都对应某次这样的转移。由归纳法，$F_i$ 等于前 $i$ 个位置的最优候选数。再加上分类中已确定不高兴者，即得全局最优答案。

复杂度

每组数据预处理相交关系需要 $O(n^2)$ 时间；动态规划需要 $O(200n^2)$ 时间。空间复杂度为 $O(200n)$。