蓝桥杯多校模拟赛G民间题解

我要写题解以做题人的身份讲讲我看到这题时是怎么处理的。希望能给大家提供帮助。如果还是对题目有问题，可以找我联系，我QQ：1557025615
首先我读完G题发现输出-1可以骗分
先思考如果我想把S变成一个指定的串的最优操作方式的贪心方式。这个贪心很典，我甚至之前见过 具体地，方式就是从左到右按位依次确定，每次确定都选局部次数最少的就能做到全局次数最少。

然后我跑去看部分分。我向来有先看部分分的习惯。
对于 的数据，我知道了可以暴力枚举0,1,2能拼出的全部情况，看合不合法，记录把原串变过去需要几步（是上述的贪心），时间复杂度

再看 的数据，我知道了当0的数量大于其他数的数量+1时候肯定无解。这时有解的情况只剩那一个，容易贪心地构造。

再看 的数据，400，这大概率是一个 的算法。根据我做题的经验来看应该是dp。我发现只有三个数，那么尝试先把这三个数设计进状态里面了。于是设 表示当答案的前1~d项被填满且d的位置填了op且填了i个0，j个1，k个2且合法时的最少移动次数。发现d=i+j+k，所以d这维直接干掉。

根据之前说的贪心的方式，我们知道当1到d的位置被填了固定个数的012后，d+1到n的位置剩的数的顺序是唯一的，不会因为前面填啥而改变。所以可知这样的状态设计没有后效性。可知转移时是给后面加数，可知全部情况都可以被到达。在保证了这两者之后，可以知晓状态设计能够正确找到答案。

到这一步，状态成功设计完了，且 只和 有关。所以可知能够O(1)转移（带有约20的常数）。可知题就做完了。（转移细节较多请自行思考）

这是我看到这题时的思考过程。希望能够对大家产生帮助qwq