world final 14 部分题解

比较口胡。。

Problem A Baggage (safe)

题意是每次可以将两个相邻的字符移动到空位。

然后问从 \(\text{BABABA}\) 转到 \(\text{AAABBB}\) 最少部分。

题解

首先是可以猜出来 \(n\) 的下界。 然后构造 \(\text{(AB)BAS-A}\to\text{(AB)BA-SB(BA)A}\) 然后用四次操作，将 \(n\gets n-4\)，\(n\) 小的时候直接爆搜了。

---

Problem B Buffed Buffet (euclid)

\(n\) 个离散物品，\(m\) 个连续物品。

问凑成 \(w\) 的最大价值。

题解

离散物品容易决策单调性。 连续物品，原本以为可以拉格朗日乘子，可惜的是有 \(\ge0\) 的限制不太会了。 就是实际上如果 \(a_i,a_j\) 选到的价值不同的话，一定不优（我可以把极小一段小的，换成大的，因为极小看成就是 \(a_i,a_j\) 这样更优）。 所以最后的价值一定是相同的。（当然没可以不选）。 发现如果不选，那一定是初始最小的几个不选。 注意讨论一下如果存在权值下降为 \(0\) 的，那权值就一定不能低于他。 （感觉价值一定相同有点像，拉格朗日乘子求完偏导相等的）

---

Problem E Maze Reduction (euclid)

告诉你一个图，边是有序的；两个点被认为等价的当且仅当把人分别放入这两个点，让他们随意走，区分不出来这两个点。（你知道图）

题解

其实这个等价的定义很玄幻。 实际上你是知道出边的顺序的。然后能感受到，实际上走太多步是没啥用的。 我就直接哈希那样dp了一下。 \(dp[x][t]\) 表示 \(x\) 往后走 \(t\) 步的哈希值的拼接。

然后看他们的 \(dp[x][n]\) 一不一样就好了。

Tiw 写的是从边的平凡不等价：终点度数不同可以直接推出，复杂度似乎也是 \(n^4\)?

---

Problem F Messenger

给定你两个人在平面上走的路径，第一个人可以在某个时刻让第三个人去追第二个人，问从第三个人出发到遇到第二个人最短时间。

题解

第三个人能追上第二个人，如何描述？ 显然如果给的时间越多，越有可能追上第二个人，那实际上可以二分答案。 如果我们知道了路上的时间 \(t\)，那可以看成第二个人早走 \(t\) ，然后第三个人是瞬移到半径 \(t\) 的圆内任意一个点。
可以把参考系换到第一个人身上，这样就只剩下第二个人动，那么我们就要找到线段最近距离即可。

值得注意的是，先让第二个人走，然后再换系。

---

Problem G Metal Processing Plant

给定 \(n^2\) 个两两间的价值 \(g_{i,j}\)。

一个集合的价值定义为 \(D(S)=\max_{i,j\in S} g_{i,j}\)。

你需要把全集分成两个集合，最小化，\(D(S)+D({\overline S})\)。

题解

赞美太阳。 先说一个不太阳的垃圾做法。 枚举一个最大值较大集合的最大值。 然后第二个集合的最大值是具有单调性的，尽管我们可能实际取不到这个值。 分成了三层，最上层的限制是 \(x,y\) 不能在一个集合里；中间层是 \(x,y\) 要么都在第一个集合里，要么不在一个集合看成是 \(\mathrm{bitor}\)，最下面是任意了。

这样是垃圾 \(n^4\log n\)。甚至过不去。

但冷静一下，发现上面的构成的是二分图。

1. 如果此时加边是成偶环边，那么如果是最大边，一定会导致这条链产生矛盾。
2. 如果此时加边是成奇环边，那么如果前面不割这条必定被割。可以结束。
3. 否则就是树边，一共 \(O(n)\) 条。 这样直接做是 \(O(n^3\log n)\) 可以跑过，但是不知道比太阳暗淡了多少。

赞美太阳。 我们依旧枚举一条边，但是此时我们打算直接计算出答案。 考虑一定是某条可恶的从 \(i\leadsto i'\) 的链导致矛盾了！ 记住我们依旧可以进行一次操作，一次割边操作（让这个限制根本不存在）。 既然割，那就肯定是割边权最小的，一条链的权值就被定义为链上最小权的边。 既然要有解，那一定找最大权的链，割掉他。 有点绕，并且一定程度上和直觉相反。 所以我们现在要用弗洛伊德算出 \(f_{i,j}\) 从 \(i\) 到 \(j\) 的链，权值最大的。 同时发现会导致 \(f_{i,j}\) 也恰好就是上文提到的 \(O(n)\) 条边，所以复杂度是 \(O(n^3) 的\)

---

Problem I Sensor Network (skipped)

欧几里得距离最大团。

随机做法，最大团有一个错误贪心是，每次如果能加入就加入。

然后我随机的是这个贪心的顺序。很不懂。

---

Problem J Skiing (skipped)

很不明所以的 维护连续段 dp 转移，很奇怪，转移数是对的。

---

Problem K Surveillance

长度为 \(n\) 的环，问最少用几个区间能覆盖完。

题解

首先断环成链。 然后链上怎么做？我们当然选择连续覆盖，且能覆盖最远的一个，不难发现对于一个区间 \([x_i,y_i]\) 唯一的存在另一个区间 \([x_j,y_j]\) 满足，所以我们可以倍增，看什么时候覆盖完链。

值得注意的是，有一个区间直接覆盖完的平凡解。