neerc17 部分题解

Problem F. The Final Level

从来没想过被模拟教育了。 题意，你要放置最少的，块数为 \(2n-1\) 的 L字形块，使得 \((0,0)\) 与 \((x,y)\) 联通。

题解

。。。。。。被教育了。 因为，要输出方案。所以可以直接模拟。 如果 \(x\) 坐标差的多，我就尽量给 \(x\) + \(n\)，\(y\) 坐标 + \(n-1\)。 反之亦然。 这样，最后一块也肯定是被任意拼接上的。

---

Problem G. The Great Wall

找两个区间 \([x_1,y_1],[x_2,y_2]\)，贡献形式为第 \(i\) 个位置被 \(j\) 个区间包含贡献就算 \(a[i][j]\) \(j\le 2\)。

找出第 \(k\) 大的。

题解

第 \(k\) 大，那就只能二分了。 然后扫描线一个区间，剩下的区间贡献拿值域线段树来维护，每次形如全局加 \(k\)，单点插入。。。 复杂度就 $2$n。

---

Problem I. Interactive Sort

被排序教育了。感觉就是10-11今天啥都不会，啥都想不到。。。。

题意，一个排列被分成了奇数，偶数两个数组，你每次可以询问 \((i,j)\) 表示 \(e_i\) 是否小于 \(o_j\)。

你希望在 \(\le 300000\) 次得到 \(e,o\)。\(n\le 10000\)。

保证数据随机。

题解

有点自闭。 本来以为是快速排序板子，然后写着写着发现对不齐。 不知道咋想到的/youl。 一个一个询问奇数项，然后在偶数形成的若干个集合里二分。 找到这个奇数属于的集合，然后直接暴力枚举，把集合分裂成两半。 查找当然就是 \(n\log n\)，暴力分裂可以根据随机快速排序来分析到期望 \(n\ln n\)，就完了。

---

Problem J. Journey from Petersburg to Moscow

给定一张带权无向图。

一条路径的权值被定义为，这条路径上的前 \(k\) 大的边的权值和。问 \(x\leadsto y\) 的最短路。

题解

不太好总结这个题的套路。。。 我们枚举第 \(k\) 条边的边权 \(w\)，如果大于 \(w\) 我们将其看成一定带权的边，权值设为 \(e-w\)。 否则我们认为，剩余的权值为 \(0\)。 然后最后加上 \(k\times w\)。考虑如果我们确确实实枚举到 \(k\) 小值，一定会被算进答案。如果我们枚举错了 \(k\) 小值，得到的一定是较劣的答案。 可能像是切凸包那样？

---

Problem K. Knapsack Cryptosystem

题意

题解

不太知道这个为啥解唯一呀。。。 首先映入眼帘的是一个背包判定，拿最好的复杂度就是 meet in the middle。 能做到 \(2^42\) 这样。 然后，考虑太大了，那 \(a_1\) 的可选值也很少了。 我们就枚举 \(a_1\) 那么 \(r\) 的可选值就有 \(\gcd(2^{64},a_1)\) 种。 枚举 \(\gcd\) 后发现就是 \(\sum_{l} [\frac{n}{2^l}]2^l=O(n\log n)\)。 这样就能平衡了。

---

Problem L. Laminar Family

给你一个树，和若干条链，判断这些链有没有交，（就是要么被包含，要么不交）。

题解

首先一个烂怂做法是，最终答案一定是能被划分到若干个链中的。 那么只要算每个链的答案。然后跑个括号匹配就好了。（\(l\) 处加入,\(r\) 处删除）。然后可以 \(n\mathrm{polylog} n\) 做。 一个厉害的做法是，考虑只可能是更长的包含更短的。所以从短到长插入。 并查集维护链，暴力跳链顶，就能均摊 \(O(n)\) 总复杂度 \(O(n\alpha(n))\)。