最近的模拟赛的部分题解

前言

Edgration是个非常菜的小伙子,看到ZhYic假假总喜欢写前言这么一个有趣的东西,也跟着写了起来。NOIp2018来临,他开始了水水水的道路。文化课是全班倒数,OI也是天天被吊打。不仅如此一天还比一天颓废,还是在去世之前记录一下留作我这个蒟蒻爆菜的证明。

11.5

题解

ViXbob又AK了,被吊起来打。

我又倒数第一了

11.6

ViXbob.AK++;

我又倒数第一了

写下T1的题解。

题意

求出包含$n$个短串的长度最小并且最小字典序最小的母串。
$a$包含$b$指$b$是$a$的子串。

$n \leq 15, |S| \leq 100$。

分析

考场上的打法是AC自动机上BFS,不仅被卡空间,而且还是跑的巨慢无比,只得到了30分的暴力分。具体愿意是访问了一些无用的节点,乘了个26的常数。

正解是一个状压DP。

首先去掉包含的状态,倒着DP,$f[i][j]$表示当前包含的状态为$j$,最前面的串为$i$的方案里面最小的长度。
$$
f[i][s | (1 << i)] \leftarrow f[j][s] + cost[i][j]
$$
其中$cost[i][j]$是预处理好的,表示把$i$接在$j$前面的最小花费,也就是$i$的长度减去$i$的后缀和$j$的前缀的$LCP$。
复杂度$O(n^2 2^n)$。

实际能跑的很快。

11.7

ViXbob又几乎AK了。

写一下T1的题解。

题意

bzoj5278

题解

考虑到这个冒泡的含义,相当于把一个大的数放到后面去,小的放到前面来。

对于$1 \sim i$这个前缀,每次把不属于这个前缀的数放到后面去,属于这个前缀的放到这个前缀里面来,对于每次的冒泡,等同于踢出了一个不属于该区间的数。如果前缀$[1,n]$有$i$个不属于$[1,n]$的数,处理好这个前缀的答案就是$i$,用树状数组维护即可。

那么对于每个前缀直接取$max$。

Leave a Reply

Your email address will not be published. Required fields are marked *