2017 训练赛 1 by hzwer

2017年3月7日1,9740

【poj1054】The Troublesome Frog(恼人的青蛙)

【poj1037】decorative fence

【hdu2197】本原串

【poj2112】Optimal Milkin

【bzoj4010】[HNOI2015]菜肴制作

【hdu2462】The Luckiest number

【bzoj3172】[Tjoi2013]单词

【poj1054】The Troublesome Frog(恼人的青蛙)

首先O(n^3)的算法是显然的,即枚举两个点,check一下这条路径上所有点,由于这道题时限放的比较宽,实际上图可以直接用二维的bool数组存下来

网络上的题解大多都说是暴力剪枝水过,实际上可以证明某个简单的优化可以把复杂度降到O(n^2)

我们注意到,如果纯暴力的话,一条路径会被重复check很多次,我们可以想到,强制使得选定的两个点是开头两个,即检查前一个点是否在图外,那么这样一条路径仅会被check一次

下证复杂度

对任意三个脚印A,B,C,若AB = BC且在同一条直线上,我们把AB边,BC边抽象成新图中的点,并把新图中的这两个点连成边,这样构建一张新图

新图的点数是O(n^2)的,由于每个点度数至多是2,所以边数也是O(n^2)的,而且是一张只有链的图,那么我们可以暴力在新图上找出最长链。其实,上面给出的暴力优化,就是在新图上找一个链头,并沿着这条链得出它的长度,新图的每条边仅会被check一次,故暴力优化的复杂度是O(n^2)

由于时限卡的比较紧,需要一些常数优化

【poj1037】decorative fence

用f(i,j)表示长度为i,开头为j,开头为上升(a0 < a1)的序列

用g(i,j)表示长度为i,开头为j,开头为下降(a0 > a1)的序列

从小到大dp每个数字,考虑把第i个数字放在长度为i-1的上升序列之前,变成下降序列

或放在长度为i-1的下降序列的第2位,变成上升序列

预处理完之后,类似求第K大的全排列的方法,按照排名一位一位确定每一个数字

【hdu2197】本原串

长度为n的01串的总数为2^n,考虑非本原串可以由若干个本原串拼接而成

\(f_n=2^n – \sum{f_i}(i|n)-2​\)

【poj2112】Optimal Milkin

先用floyd处理出求出所有奶牛和挤奶器的距离

二分距离mid,将距离小于mid的奶牛和挤奶器连边,用最大流判断可行性

【bzoj4010】[HNOI2015]菜肴制作

反向输出反图中【最大字典序的拓扑序】

这两个东西是等价的,而且最大字典序的拓扑序不需要考虑依赖关系

具体可以用反证法证明一下:

比如反图中有点6,链 4->5->3 …->8 ,(前面都比6小,最后一个比6大,如果链都比6小,先取显然不优),两种情况列出来会发现先6较优。

拓扑图是形如这样的链的拼接,也就是不可能先取拓扑图上的一部分再回来取编号最大的点。

【hdu2462】The Luckiest number

【bzoj3172】[Tjoi2013]单词

求出fail树后

对每个串的每个节点打标记

然后输出每个串终点子树的标记个数和