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 长度即可，每个点在树上查询并扔进线段树即可。

答案在线段树合并的同时不难维护。

$\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{题意} $n \leq 70,m \leq 10^5 \texttt{题解}

吐槽一下，学弟告诉我题意的时候我以为有标号，结果觉得完全不能做(信息量不够)，哈哈

儿子有顺序的话，一棵树对应唯一一个括号序列，且这个括号序列的开头结尾必然是一对匹配的括号，因此将它们去掉，剩下一个长度为 2(n-1) 的括号序列，由于 Cat_{69} < 2^{128}, 所以对括号序列编码即可。

编码可以用字典序来编码，转移的过程可以事先 dp 好，存在 static 里.