Loading...

11月3日NOIP模拟赛部分题解

check评论:0 条 remove_red_eye浏览量:385 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-11-03

题目见下方文件,这里只说明第二题的做法

60分我不知道怎么做的

$80$的话,我们考虑$dp$,即$f[i][j][0/1][0/1]$代表第$i$个数,种类为$j$,前面是否出现过三个连续一样的,和上一个是否相等

然后枚举这一次和上一次的种类进行转移即可,时间复杂度$O(LS^2)$

然后观察数据范围,发现正解肯定是$O(L)$的

我们想办法去掉枚举字符集

如果你输出的$dp$数组的部分答案,你会发现,对于每一种字符,最终状态的答案是一样的,那我们直接推出一个答案然后乘$S-1$不就好了吗?

前面的转移就改为$f[i][0/1][0/1]$,代表的意义不变,我们在对于不同字符的转移时将$ans$乘上$S-1$就好了

可以用滚动数组将空间复杂度优化,数组只用开$f[2][2][2]$

就不发代码了qaq

考试文件

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名