最暴露真实水平的一把。只做出来 \(4\) 道纯签到题,但其实这把的前 \(6\) 题都是签到题级别,切签到的速度也不快,罚时还上天。
\(F,J\) 没啥好说的。
\(C\) 题能感觉到一定是先克隆,再出题。\(O(\log n)\) 枚举克隆次数计算答案即可。蒟蒻因为未准确估计答案范围,没有计入未克隆的情况,导致吃了很多罚时。
\(G\) 题直接暴力就行。容易发现答案不会超过 \(O(\sqrt n)\),因为对于一个长度为 \(m\) 的字符串,如果字典中包含其所有子串,那么字典中至少应含有长度为 \(1\) 到 \(m\) 的串各一个,这样总长度就至少为 \(\frac{m(m+1)}{2}\),而总长度不超过 \(1e5\),因此可知答案是根号级别的。剩下的就是按长度排序,暴力。
事实上,正解不是这个,上述做法的复杂度最坏情况下也会达到 \(O(n^{2})\),感觉是数据弱了。正解是:如果一个字符串 \(s_{1}s_{2}...s_{n}\) 是好的,当且仅当 \(s_{2}s_{2}...s_{n}\) 和 \(s_{1}s_{2}...s_{n-1}\) 是好的。于是按照字符串长度排序,用 \(set\) 模拟一下就行了。
E. Find Maximum
看到这个题,蒟蒻没有往三进制上想,打表也看不出来任何有用的信息,牢底坐穿了。
打表发现,\(f(x)\) 就是 \(x\) 三进制意义下的数位之和 + 数位个数。
code
L. Tree
长链剖分,还需要用到一些反链的知识。
之前没学过长链剖分。它与重链剖分的唯一区别在于,每个结点的重儿子选取的是其子树中高度最大的子结点。
首先要清楚,如果要将结点 \(u\) 划分至某个第一类集合,那么这个集合中一定会包含 \(u\) 到其子树内某个叶节点的路径上的所有点。否则,我们一定可以将未加入的点 \(v\) 划分至该集合,由于这个集合至少包含点 \(u\),那么集合数量一定不会增加,可能会减少(\(v\) 单独在一个集合时),答案一定不会更劣。
如果学过长链剖分就会知道,按照长链剖分的思路来划分第一类集合,是最优的。
那么,每个第一类集合一定对应了树中的某个完整的长链。选取部分长链作为第一类集合,那么剩下的长链中的所有点就只能划分到第二类集合。在第二类集合中,显然不能出现同一长链中的点。因此最优的划分方式,就是每次选取一个剩余长链中的点划分到一个第二类集合中,那么最终第二类集合的数量,就是剩余所有长链的最大长度。
贪心地想,要让答案最小化,就尽可能地让剩余长链的最大长度最小化即可。因此做法就是将所有长链按长度降序排序,枚举前 \(i\) 条长链划分至第一类集合(数量为 \(i\)),剩余长链划分至第二类集合(数量为 \(len_{i+1}\))。
还有一种做法:对于第二类集合的操作,一定是将当前图中的所有叶节点纳入同一个集合最优;对于第一类集合,集合数量至少是叶节点数。 因此可以直接拓扑模拟,每次删除当前所有叶节点并将它们纳入第二个集合,剩下图中的叶节点数即为所需的第一个集合的数量,在每轮删除后更新答案求最小值。
code
code2