【BZOJ 3019】[Balkan2012] handsome

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3019
神犇题解:http://www.cnblogs.com/clrs97/p/6371367.html

解题报告

因为字典序大小这个东西实在是没有办法
所以我们根据它给的排列顺序来填数

这在原数列上的填充顺序是离散的
但考虑已经填了$i$个数,现在填第$i+1$个数
这大概是把一个空白的区间分成两份
于是我们预处理$f_{i,l,r}$表示长度为$i$,左右端点的字符分别为$l,r$的合法序列的方案数
这样我们就可以使用线段树在$O(\log n)$的时间复杂度内快速维护答案了

于是我们还是类比传统的数位DP,然后按照排列顺序往里加字符,使用线段树来维护答案
预处理的时间复杂度:$O(n)$,主程序的时间复杂度:$O(n \log n)$

One thought to “【BZOJ 3019】[Balkan2012] handsome”

发表评论

电子邮件地址不会被公开。 必填项已用*标注