vfk的数据

算法一

这题是一个对于字符串进行排序的题目

我们第一个想法是按照字典序相同

但这样有个问题，就是100.in的字典序比2.in要小。于是我们改为双关键字排序，即用（长度，字符串）作为一个二元组，以长度为第一关键字，字符串为第二关键字，进行排序

如果使用冒泡排序，复杂度是$O(n^{2}L)$,$L$为串长，能够得到$50\mathrm{\%}$的分数

算法二

对于参加noip的选手，一般来说至少要掌握一种$O(n\log n)$的排序方式

比如使用快速排序，能够把时间复杂度优化为$O(n\log nL)$，可以得到满分

一种会错误的写法

有的人可能会想算出编号

但我们题目中从来没有提到过数字的大小范围，事实上即使你用$longlong$进行存储，也是无法通过所有数据的

对于用$int$和用$longlong$的，都是70分

算法三

如果数据范围加强，也是可以做的

问题主要在于字典序的比较，快速比较两个字符串大小，能用二分+hash的方法在$\log L$里算出，这样子做复杂度是$O(n\log n\log L)$

另外我们可以建立一棵trie，在tire上进行DFS一遍，可以$O(nL)$的预处理出所有字符串的字典序的排名

然后再进行排序，复杂度就是$O(nL+n\log n)$

trie树会有庞大的额外空间……

事实上我们可以改写成100关键字的基数排序来做的话，就能够避免字符集的影响，做到时空都不超过$O(nL)$了

pyx的难题

算法一

我们先来枚举那个题目的优先级

注意到排序后相邻两个优先级之间的所有数字是等价的，换句话我们可以枚举优先级的排名

枚举了排名之后，我们进行判定，如果使用最暴力的方法判定，就是进行模拟

我们用一个队列来存储所有题目，并让队列是有序的。如果新加一个题目，就$O(n)$的进行调整，使他重新有序。

这样的复杂度是：枚举$O(n)$，判定$O(n^2)$，总复杂度$O(n^3)$

如此可以得到$60\mathrm{\%}$的分数

算法二

随着优先级的增高，完成他的时间只可能会变小

对于这种单调性，我们可以使用二分查找的方法优化

用二分查找进行优化，每次暴力判定，时间复杂度是$O(n^2\log n)$

算法三

如果没有想到二分查找，有没有办法优化判定的过程呢？

注意到我们的模拟过程是这样的：添加一个题目，删除一个题目，并且还要随时随地的知道还没做完的题目里优先级最高的题目

那么我们并不需要$O(n^2)$的来做，事实上用堆（或者别的数据结构），是可以$O(n\log n)$的模拟全程的

时间复杂度仍然是$O(n^2\log n)$

算法四

我们可以将算法二和算法三结合起来

二分答案，并用优先队列判定，可以在$O(n{\log }^{2}n)$的时间里出解

可以得到90分

算法五

对于最后的点，数据范围是$3\times {10}^5$，即使手写堆，$O(n{\log }^{2}n)$的时间复杂度也无法在时限内出解

我们需要想办法优化掉一个$\log$。然后第二问基本上毫无特殊性，要优化他几乎是不可能的（除非使用VEB树之类的东西，神犇请受我一拜）；与之对应的是，第一问的二分是建立在单调性上的，而有单调性的题，往往可以试着利用扫描的方法去优化。

我们先假设特殊题目的优先级是-1（本质上是$-\mathrm{\infty }$），进行一遍模拟

经过这一步模拟，我们可以得到$[t_x,T]$这个时间段里的信息：每个题目在$[t_x,T]$内所使用的时间

我们把在这个时间段里做过的题按优先级排序

那么找到前$i$小的，使得他们的存在时间和等于$s_x$，就相当于平移回去了！

如果题目允许实数，只要把他的优先级定为第i小的$+0.5$就好了；当然，由于要求互不相同，所以我们要找到一个最小的没有出现过的优先级。由于题目保证有解，所以找到的最小的一定是个合法解

由于不需要二分答案，所以时间复杂度$O(n\log n)$

ydc的大树

算法一

我们可以的进行一堆预处理，比如说任意两点的距离，他们路径上的所有点等等$\dots$

接下来枚举摧毁的点，枚举所有黑点，利用预处理的信息进行判定。

朴素实现的话，时间复杂度是$O(n{m}^2)$，可以通过$30\mathrm{\%}$的数据，即$1,2,7$号点

算法二

算法一预处理和距离是只需要$O(n^2)$的，但是预处理路径上所有点则是$O(n^3)$

注意到预处理路径上的所有点，是可以用压位技巧或者bitset来进行优化，这样时间复杂度就是$O(n^3/30)$，可以通过。

这个算法能得到60分

算法三

对于六号点，由于是链，所以每个黑点的距离要么是最左边的黑点，要么是最右边的黑点

预处理离最左边的点最远的点有哪些；预处理离最右边的点最远的点有哪些

枚举炸掉的点后，我们要求的就是最远点是最左边点的在他右边的点的个数以及最远点是最右边点的在他左边的点的个数

能得到链的10分

算法四

结合算法三与算法二，可以得到70分

算法五

为了方便描述，我们暂且认为每个点走到的就是单纯意义上的最远点。

由于涉及到最远点的问题，我们引入一些中心的概念。（参考自noip原题树网的核）

树中最长的路径称为树的直径。对于给定的树$T$，直径不一定唯一。但可以证明各直径的中点唯一（不一定恰好是某个结点，可能在某条边的内部），我们称之为中心。

我们还能证明，任何点走到离他的最远点一定经过了中心。如果中心不是某个节点而在边的内部，可以想象既然经过了这个点，必然经过边上的两个点。

我在此定义概念类中心。大概就是说，如果中心恰好是节点，那么他也就是类中心，否则就是它所在的边的任意一个端点。

可以证明，任何点走到离他的最远点一定经过了类中心。

既然类中心有这样优美的性质，那么它是否对我们解题有帮助呢？

我们将无根树变有根树，找到一个类中心，将它提根。

类中心的找法很容易，只需任意求出一条直径，根据定义来找即可。直径可以用做两次最远点或者树形动态规划的方法在$O(n)$时间内求出来，具体算法是noip级别知识，不再赘述。

我们枚举每个点，我们要做的就是看有哪些黑点走到最远点必须经过他。

利用类中心的性质，我们知道任意$a$走到$a$的最远点时必须经过根。判定$a$走到$a$的最远点是否必须经过$b$分两种情况：

• $a$不在$b$子树内。我们只需记录每个子树内最深点的深度，拿$b$所在子树是不是覆盖了所有最深点之类的情况出来讨论即可。
• $a$在$b$子树内。$a$走到$a$的最远点，必须经过根，于是必须经过$b$了。

当然我们还要注意到题目要求的不是单纯意义上的最远点，而是黑点之间的。（也可以理解为在黑点构成的虚树做这道题目）

我们只需稍微改变一下定义即可。我们把直径理解为黑点之间的最长路，中心、类中心的定义跟着变化；要维护的东西（如每个子数内最深点的深度）也跟着把“点”变成“黑点”即可。

问题完美解决，是$O(n)$的算法，他与读入复杂度同阶，非常优秀。

这个算法能够得到100分

其他算法

这题还有很多其他的算法

vfk的树形dp的办法，还看到有人用点分治能$O(n\log n)$做等等……

这是一道一题多解的题目