IOI2024 D2T3 sphinx

zjy2008 · 2024-09-08 19:59:49 · 题解

人类智慧题喵。

先考虑 50 分怎么做，按 1\cdots N 的顺序依次加入点，若没有被加入就把颜色记为 N 。先假设这个点 u 新构成了一个颜色连通块，可以通过已知信息推导出查询应该有的连通块数。若符合期望，直接退出，开始加入下一个点。否则在 1\cdots u-1 中二分第一个和它形成同一连通块的点，将这 2 个联通块合并后回到第一步。

分析一下操作次数，记最终连通块数为 C。每次合并 2 个连通块需要 \log N 次查询。一个点加入完成后需要 1 次查询，共有 (N-C)\log N+N 次查询。

如果最后只剩下了 1 个连通块，这是平凡的。

考虑把整个连通块视为一个点，建成点数为 C 的新图，随便搜出一棵生成树并黑白染色。先枚举颜色 c，把白色点都赋为 c，黑色点保持原状。假设所有黑色点的颜色都不为 c，可以推导出应该有的连通块数。若查询符合期望，直接退出，枚举下一个颜色。否则二分所有白点中第一个和 c 颜色相同的。

显然你需要交换黑白，再做一次，故操作数是 C\log N+2N 的。

总操作数为 N\log N+3N，可以获得满分。