【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)$

13 thoughts to “【BZOJ 3019】[Balkan2012] handsome”

  1. Hello, i feel that i noticed you visited my website thus i came to “go back the want”.I’m trying to to find things to improve my site!I suppose its good enough to make use of a few of your concepts!!

  2. 971397 26727Spot up for this write-up, I actually believe this internet internet site requirements a great deal a lot more consideration. Ill likely to end up once again to read a lot far more, many thanks for that data. 796526

  3. 940070 249415Wow, awesome weblog structure! How long have you been running a blog for? you produced blogging appear easy. The total appear of your web site is wonderful, let alone the content material material! 849178

  4. 502976 768126Its a shame you dont have a donate button! Id most surely donate to this outstanding web internet site! I suppose within the meantime ill be pleased with bookmarking and putting your Rss feed to my Google account. I appear forward to fresh updates and will share this weblog with my Facebook group: ) 347958

  5. 897052 196585I discovered your weblog internet site on google and appearance several of your early posts. Keep up the outstanding operate. I merely extra the RSS feed to my MSN News Reader. Looking for forward to reading far more on your part later on! 136369

发表评论

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