摘要:出了场水赛拿给机房神仙做 /kk

09122020机房赛

说是赛后总结其实赛前就写了.

话说出题人能不能参赛混一波rating啊 (笑)

T1 「MZOI2020」快速班号变换

杂谈

忘了说明数字不能重复变换实在是抱歉.

被syc猜中是dp了,预言题目做法程度的能力吗…

想着是t1所以数据放了点水,反正本来定位就是个签到题.

正解$O(n^2)$的dp,但是$n \leq 1000$的数据$O(n^2logn)$的诡异做法应该也能过了.

样例很草生但愿你们不要考场上笑出来.

题目分析

设计状态$f_{i,j}$表示仅考虑字符串$a$的前$i$位和字符串$b$的前$j$位完成变换的最小花费.

那么转移其实就很显然:

分别表示在这个位置删除一个数,插入一个数,替换一个数.

分别讲一下,删除当前数,就从$f_{i-1,j}$这个状态转移,相当于这个位置作废不计,加上转移的花费.

插入一个数同理.

替换数的话就从$f_{i-1,j-1}$这个状态转移,直接加上让两个字符串下一位相等的花费即可,这个花费即为替换需要的李距离.

代码

见下发文件.

T2 「MZOI2020」魔导书

杂谈

这个题之前自己都只有状压思路而且这个状压写起来特别鬼怪.

这周一早上把题发给绵实机房他们证出来可以贪心,然后我中午回去想了想把贪心过程做成了数据结构.

所以搜索就没给分,把状压调到了最低档,希望康康蛙能给出奇怪的搜索做法.

其实有个强一点的样例,不过在我笔记本上所以就用了原先的一个.

关于模数.

题目分析

solution0

这题好不可做啊!交个$ans=\sum_{i=1}^{n}a_i$跑路吧.

期望得分0.

solution1

写个诡异的状压,因为可以确定的是对于每一个书的集合都有一种最优情况来放,记录当前书堆在最优情况下最多还能放几本即可.

期望得分30.

solution2

首先有一个贪心的模型:如果放了一本书在最底层,只用再在下面加上一本$b$比它大的书,状态仍然合法,但答案更优.

所以把能放书最多的书$i$放上去,然后把剩下的书$j$的$b[j]$改成$\min(b[j],b[i]-1)$,然后按$b$为第一关键字排序,$a$为第二关键字排序,找到第一个,一直循环即可.

期望得分60.

另外这里的$a_i \leq 10^3$只是拿来唬人的不会真的有人去想吧 (

solution3

solution2修改的过程考虑使用数据结构维护,把$b_i$相同的书放在一个堆,堆内维护$a$,因为每次是取最大的$b$,所以$\min(b[i],maxb-1)$这个操作仅会影响最大的$b$对应的堆,然后这个堆的$b$改变到和第二大的相同了就合并这两个堆.

不断地取出最大的$b$对应的堆的堆顶,再合并即可.

所以需要用到一种支持合并的堆,std用到了左偏树,参考.

期望得分100.

solution4

赛后才知道把$b$序列排序后倒着插入一个普通的堆就能做了,因为在合并之前在最大值之前的$b$是无效的,所以在减到的时候再插入就可以了…

代码

见下发文件.

T3 「MZOI2020」遗传因子

杂谈

周五早上lyc把”橙队”打成”成对”我还以为泄题了 (

数据可能有点水,因为要让串长尽量长短不一产生答案.

第一档分防爆零,不过先为大王默哀三秒…

题目分析

首先我们将模型简化一下,将$|p|+|q|$视为$1$来做.

那就是求字符串集中一个串作为其他串的子串出现的次数.

考虑使用AC自动机解决这个问题,由AC自动机的性质可得,trie树上的一个点对应一个串的前缀,反构的fail树上的一个点对应了后缀的关系,也就是一个点的父亲代表的节点都是它的后缀.

先在反构的fail树上进行一次递归,求得一个点的父亲中有多少个点有end标记,存入cnt数组.

然后在trie树上进行递归,递归地累加上之前求得的cnt数组,到有end标记的点就加进答案,就求出了一个点的前缀中包含了多少个有end标记的后缀,就是这个点代表的串包含的其他子串的出现个数了.

注意这里说的是出现次数,比如串aa在串aaabb中出现了2次.

然后考虑算上$|p|+|q|$怎么更新答案,发现就是两个串长度的差值,所以我们在记录cnt时,顺带记录一个有end标记的点的长度和leng,然后递归trie树时同样发生累加,更新答案时用当前串的长度乘上包含的子串的出现个数减去累加得的长度和即可.

期望得分100.

代码

见下发文件.