NOI2015 Day2

NOI2015 Day2

荷马史诗

题目描述：给出(n)个数，要求(n)个(k)进制数来对应这(k)个数（允许有前导零），(n)个(k)进制数互不为前缀，求(n)个数乘以对应的(k)进制数长度总和最小值，并求最小值下(k)进制数的最长的最小值。

solution:
(k)叉哈夫曼树，当(n ot equiv 1 (mod (k-1)))时，补零时条件成立，然后类比二叉的做法即可。

时间复杂度：(O(nlogn))

品酒大会

题目描述：给出一个字符串，第(i)个字符对应的值为(a[i]), 对于(i in [0, n)),求最长公共前缀大于等于(i)的字串对个数，并求这些字符串对开头对应值相乘最大值。

solution:
后缀数组求出(Height[i]),根据(sa)对字符串重标号，(Height[i])就是第(i)个字符串与第(i-1)个字符串的最长公共前缀，枚举最长公共前缀(len),对于(Height[i]=len)的(i)，用并查集链接(i)与(i-1)，并更新答案与最大值。注意：字符对应值可能是负值，所以还要记最小值。

时间复杂度：(O(n))或(O(nlogn))

小园丁与老司机

题目描述：给出平面上的(n)个点，点的纵坐标均大于(0)，从原点出发，每次从左、右、上、左上(45^{circ})、右上(45^{circ})
选择一个方向（该方向必须有一个点），走到该方向最近的点，然后继续选择方向走，如此类推，直到不能走为止。求最多能走多少个点（不计原点），并输出一条可行路径。找出所有最长路径上的非左右方向的边，求覆盖所有边的最少路径数（路径只能包含非左右方向的边）

solution：
预处理出每个点在非左右方向离该点最近的点，然后以纵坐标为第一关键字，横坐标为第二关键字排序。以纵坐标为阶段做dp，同层的也做dp。这里只讲同层如何dp。
枚举从哪一个点向上走((i))，假设之前在下一层往上走到(j)，如果(x_j<x_i)，那么与(i)同层的，且在(i)左边的都可以到达（从(j)走到同层的最左边，然后走到(j+1)，再走到(i)），如果(x_i<x_j)，那么与(i)同层的，且在(i)右边的都可以到达（从(j)走到同层的最右边，然后走到(j-1),再走到(i)），那么正向做一次，反向做一次就可以知道最大值了，同时记住方案。
根据方案将非左右方向的边找出，并构出新图，因为有可能多条最长路径同时经过某些边，因此每条边的下界为(1)，做一次最小流即可。