天津省队互测解题报告

发生

【题意】给定一棵带权树,现有若干个有序对,每个有序对代表树上的一条路径。。求以K为起点的单源最短路。
【题解】
考虑有序对数量很少的情况。
我们将两条路径上的点划分成2个集合,再将对应边连上,就构成一个完全有向的二分图。
这样边数量是O(N^2)级别的。我们不妨虚加入一个点M,将集合的点分别连一条费用的边到M,同理将M与的每个点连一条费用的边。这样边数是O(N)的。

如果是一条链该怎么做呢?这就是本题最精彩的地方所在。
借助刚刚的思想,我们可以将一段连续的区间在线段树中拆分成log(N)个区间,再让这两个区间集相应连边即可。实现共用最低层,一棵顺着建,另一棵倒着建。最后跑SPFA就可以了。
树的做法与链大同小异,剖分一下即可。

适者

【题意】你在玩一个回合制的游戏,现有若干敌机,每个敌机均有血量和攻击输出值。每个回合你先出手,可以对敌方造成固定的伤害,当前回合所有血量大于0的家伙可以向你输出对应的伤害。请你安排最优的攻击顺序使得你收到的伤害总量最低。
【题解】
这题的贪心就是NOIP水平的。先不考虑删点的操作,不妨设,由调整法可知按照从小到大的顺序打伤害总和最小。
现在回到原问题。
如果我们每次枚举删除的两个单位,除掉他们会减少的伤害值为

这样的时间复杂度显然是不优的。
我们不妨枚举第一个被删除的对象,这个点后面所有的点都可以变为该点的决策。发现实质是维护一个凸包,并且从无穷远处有一根斜率为的直线打下来,询问最优解。用栈维护一个凸包,在上面二分最优决策值就好了。
这样非常符合CDQ分治DP的模型,直接上模板即可。

采样

【题意】
给出若干字符串,定义采样为一个字符串的最小表示,对于每个采样求有多少个其他的采样是当前采样的前缀。
【题解】
考察了对长相和谐(丑陋)函数的求导能力。
直接最小表示法后建立Trie树即可。