NFLSPC #8 题解

ppip · 2025-11-15 18:44:37 · 算法·理论

A. 轨道交通

考虑一维情况如何解决。可以排序后选择前 n + 1 个点，找出其中颜色相同的一对，连接这对点并把前面不同颜色的删除，这样对于剩下 n - 1 种颜色，至少有 n 个点，转化为等价子问题。 对于二维的情况，观察到限制实际上被放松了，因此按照 x 轴排序后做一维的情况，容易验证不会相交。时间复杂度 \mathcal O(n ^ 2 \log n)。

B. 数嘟嘟嘟嘟嘟

首先，需要发现，在题目条件的限制下，有唯二解的题面，唯二解差异涉及的地方，一定只涉及恰好某两个数字。

下面考虑构造。不难发现，一共只有两个数字的情况，差异只可能是偶数，涉及恰好 x 个宫，x 个行，x 个列，满足每行、每列、每宫都恰好含有涉及的两个数字各一个，而且不能由多个独立结构组成，否则解的数量不是 2 ，容易变为 2^y 其中 y 为相互独立的该种结构数量。自然发现，该种结构是类似于哈密尔顿回路的。因此，直接枚举所有2个数字的组合，然后排除掉已经有这两个数字的行、列、宫。剩下的里面，可用的行、列、宫的最小值即为这两个数可能达到的最大差异值的一半，注意排除不可用的宫，如果一个宫只剩少于2个空格，这个宫也是不可用的。

找到全局可能达到的差异值最大的那组数，然后，在此基础上，搜索出一组满足条件的填法两个数字填法。这时，我们有很大概率有至少一组合法的数独解，然后再搜出任意一组整个数独的解，然后把输入的数和这个两个数字差异部分全部去掉，这样组合的补法就有唯二解了。

C. 追忆desuwa

不会

D. 如何区分北京东路和北京东路

容易把每个位置贡献拆开来，根据对称性发现每个位置对自己和对别人的贡献分别相同，并且都形如当前值乘以某个系数。容易发现每轮这两个系数分别是 x\leftarrow kx+b 的形式，做 k 次一次函数复合即可，这里类似快速幂。复杂度 O(n+\log k)。

E. 小 P，小 W，棒棒糖

考虑 n\leq19。此时利用 product trick 将所求化为每个点选一条与其相连的边或不选（不选的贡献是 t）。此时状压每个点选没选，然后依次加入每条边更新 dp 数组，复杂度 O(m2^n)。

对于 n 大的情况，按除以 k 的商分层，依次考虑每一层，同样加边并维护当前层和下一层的状态即可 O(m2^{2k})。

此时我们发现可以删掉已经处理完与其相连的所有边的点，那么现在按连接的点的顺序加入边可以做到 O(m2^{1.5k})。

我们先处理完连接一个和零个下一层点的当前层的点。对于剩下的点，我们在其连接的两个点之间建立虚边，形成了很多连通块，我们按非树边数量从大到小遍历每个连通块，访问一条边就处理其代表的上一层的点即可。可以证明此时复杂度 O(m2^k)，可以通过。

F. 小 W，小 P，彩丝带

一次操作相当于选出一些下标，相邻的选出的下标奇偶性不同，然后全部 -1，不能选 0。

我们先考虑没有 0 的时候，答案一定是所有数的 \max。

那么考虑把有 0 的情况转化成没有 0 的情况，我们观察到 x00\dots 00y 可以做一个缩的操作。

如果有奇数个 0，缩成 x, y，否则缩成 x+y，正确性不难证明。

这样我们维护这个东西扫描的过程，类似一个栈，用线段树二分维护就行了，复杂度 \mathcal O(n\log n)。

G. NFLSPC