[NOI2022] 移除石子

发布时间 2023-06-28 11:55:53作者: PYD1

看错题以为操作一删恰好 \(2\) 个卡了好久=_=。虽然看对之后还是不会做。~

这种神秘的条件让你计数,要么发挥人类智慧找神秘充要条件之类的,要么直接设计判断合法的自动机然后 dp 套 dp。后者稍微靠谱一些,所以我先想的后面的。

一个简单的人类观察是操作二不会重复进行,否则我们换成一。

另一个简单的人类观察是操作二的长度不超过 \(5\),否则我们可以拆。

先考虑只有操作二,我们做一个类似插头的东西,考虑记录目前长度为 \(1,2,\ge 3\) 的有多少个,转移的时候就优先匹配长度为 \(1,2\) 的(不匹配上就活不下去了),匹配完之后还有剩的就找 \(\ge 3\),还有剩的就只能新开长度为 \(1\) 的。

但是你发现加上操作一之后会有一些问题,我们可能遇到如下困境:到底是少匹配一个 \(\ge 3\) 的还是多一个长度为 \(1\) 的。你发现这两种都有对应的反例可以构造,这很坏。当然我们不坚持只有一个转移(DFA)可以轻松解决(反正我卡了一会觉得想不出来一个转移怎么做),那我们考虑改成一种一般的 DP。

具体来说,设 \(dp_{i,j,k,w}\),你发现这个状态数是 \(jkw\le 27\) 的,太逊了,根本没办法继续往上再套 dp。考虑动用人类智慧。你发现这个 DP 自由度很高啊,我们考虑把一部分状态平衡到转移上去。你考虑事先枚举那些 \(\ge 3\) 的段会不会继续走,这样可以降一维。然后通过对拍 查阅题解 发现 \(j,k\le 2\) 也是正确的。这很好。

考虑 \(k\) 的限制,可以多记一维代表还有多少个石子没有放,发现状态数爆炸,不会写了。

考虑放松限制,好奇什么情况下加更多的石子会变劣。你发现首先比 \(p\) 多很多是没意义的,我们可以全丢到一堆里用操作一。我们考虑比 \(p\)\(1\),如果此时序列当中没有可以延伸的 \(2\) 操作你发现就寄了。你发现只有 \(a_i=1\)\(n=3,a_1=a_2=a_3=1\) 不行。特判掉。

剩下的就很简单了,我们记 \(f_{i,j,k}\) 表示让 \(dp_{i,j,k}=0\) 至少要多少石子。

把内部的 \(f_{i,*,*}\) 压成状态 \(st\),套上外层 DP,你猜测某个位置放较多的石子都是等价的,对于阈值 \(m\) 分讨转移即可。发现 \(m=6\),状态数 \(S=8765\)

复杂度 \(O(nS)\)