THUSC2021 Day1口胡题解

$\texttt{T1}$ $\texttt{题意}$ 有 $n$ 个有重量的物品和一个大小为 $m$ 的背包，一轮一轮装物品，要求每轮装尽量多数目的物品，且最大化拿走的物品按编号排序后的编号字典序，如此模拟下去求轮数。 $n \leq 5\times 10^4,m \leq 10^9$ $\texttt{题解}$ 首先我们可以用 $\Theta(n\log n)$ 的复杂度求出每轮删的物品个数(不是一开始求出，而是每一轮同步进行)，可以用堆做，也可以排个序用指针扫。 考虑一个一轮 $\Theta(n)$ 解决的做法： 我们事先给物品排好序，记当前这一轮需要拿走 $k$ 个, 然后在剩下的物品数组中,维护一个链表的同时一边跳一边 $check$ . 这样做复杂度是 $\Theta(n^2),$ 但并不能通过全部数据。 考虑如果 $k$ 比较小，可以在线段树上维护拿走的物品集合，可以用类似归并排序的方法实现，一次 $update$ 复杂度 $\Theta(k).$ 在维护好信息的情况下考虑每次找到下一个数字拿什么，在线段树上二分就行，虽然一次查询的复杂度是 $k\log n $ 但是总共不超过 $n$ 次查询因此总复杂度是 $\Theta (nk\log n)$ 设一个阈值 $B$ , $k \geq B$ 时用 $\Theta(n)$ 的暴力，当 $k$ 开始 $\leq B-1$ 的时候建线段树维护即可。 复杂度 $\Theta(\frac{n^2}{B}+n\log nB)$ , 取 $B=\sqrt{\frac{n}{\log n}}$ 时时间复杂度为 $\Theta(n\sqrt{n\log n})$ . ## 一个 $\Theta(n\sqrt n)$ 的做法： 对于 $k<B$ 的部分，分块做，设块长为 $S$ ,每个块用链表存一下排序结果即可，单次复杂度$\Theta(B^2+B(S+\frac{n}{S})).$ 总复杂度$\Theta(nB+n(S+\frac{n}{S})+\frac{n^2}{B}),$取 $B=S=\sqrt n$ 总复杂度为 $\Theta(n\sqrt n)$ ## 如果空间卡的很紧，可以适当将 $B$ 缩小,由于 $\Theta(n)$ 的暴力常数很小所以问题也不大。 哦还有另一个 $\texttt{polylog}$ 做法，~~大概是二分套树套树上二分，还要开俩线段树，所以还是分块吧~~ 大概是，每一轮求出个数仍然是随便求，然后二分 $k$ 次下一个拿的数字的位置，二分里面要写一个，支持 $n$ 次删除 的 查询后缀 $k$ 大值的数据结构，这个可以开两个树套树来实现。~~这东西场上真的有人写？~~ ~~哦好像有很多，那没事了~~ $\texttt{T2}$ $\texttt{题意}$ 给你一颗带点权树,要选一个点集使得它是一条链，并且按照链的顺序 , 点权序列是最长上升子序列，最大化最长上升子序列长度。 $n\leq 10^5$ $\texttt{题解}$ ~~本来看到同学给我发这个题我觉得是个点分治，结果我 naive 了，原来可以直接线段树合并，哈哈~~ 直接线段树合并，记值域上升/下降到当前值时候的 $LIS$ 长度即可，每个点在树上查询并扔进线段树即可。 答案在线段树合并的同时不难维护。 $\Theta(n\log n)$ , 当然也可以点分治/dsu on tree/启发式合并,由于没卡 $2\log$ ~~甚至没卡3log~~所以上述做法都能过。 $\texttt{T3}$ $\texttt{题意}$ 有 $n$ 个人和 $m$ 种菜 , 第 $i$ 个人对第 $j$ 道菜的喜爱程度为 $a_{i,j}$ , 如果 $a_{i,j} = -1$ 则表示不喜欢 . 现在你要选择一个菜的集合，你会获得喜欢集合中所有菜的人对这些菜的喜爱程度之和的权值，最大化这个权值. $n\leq 20,m \leq 10^6$ $\texttt{题解}$ ~~知道题意的时候降智了，只会一个2^nn^2的做法，我好菜啊~~ 显然是个 $fwt$ 题。 考虑求所有的人集合的答案。 对于一道菜 $x$ ，记它对应的人的集合为 $S$ $A[S] += \sum\limits_{i} a_{i,x}$ , $A[S-(1<<i)] -= a_{i,x}$ 然后对 $A$ 做 $fwt$ 就行了。 $\Theta(mn+n2^n)$ $\texttt{T4}$ $\texttt{题意}$ $m$ 测，要求实现对一棵有 $n$ 个节点，儿子有顺序的无标号树的编码和解码，只能用一个 `__int128` . $n \leq 70,m \leq 10^5$ $\texttt{题解}$ ~~吐槽一下，学弟告诉我题意的时候我以为有标号，结果觉得完全不能做(信息量不够)，哈哈~~ 儿子有顺序的话，一棵树对应唯一一个括号序列，且这个括号序列的开头结尾必然是一对匹配的括号，因此将它们去掉，剩下一个长度为 $2(n-1)$ 的括号序列，由于 $Cat_{69} < 2^{128},$ 所以对括号序列编码即可。 编码可以用字典序来编码，转移的过程可以事先 $dp$ 好，存在 `static` 里.