【学习笔记】阶段测试1

Menci 的序列

二进制 + 构造 + 贪心

第一眼是 dp 。想了 1.5h ，想不出来状态。

我会乱搞 ！乱搞 80pts 。

首先把原序列改造一下。注意到 1000=010

这样构造后连续的 + 不超过 2 个

然后我们从高往低位贪心 。

显然是要用最少的 + 来构造。

因此最高位尽量不进位 。

不难想到贪心方案：从左往右遍历连续的 + 段，对于每一段连续的 + 只取一个，每一段连续的 * 也只取一个，这样前缀一定是 1111…

如果遇到后缀 * 不足的情况，那么这一段 * 的个数一定 >=2 ，足以隔断后面的选择对前面的影响（换句话说不可能进位了），那么我们只需让后面的 + 对答案贡献尽可能大 。

可以用两个二进制数相加来理解 。

Submission

你要问这个贪心怎么想到的，我也不知道 ，可能是感觉吧。

排序

膜拜 idsy …

这题第一感暴搜。

当然这题如果只能暴搜就太没意思了。

比如 Limak and Shooting Points 堪称搜索神题 。

其实正解挺显然啊 。

考虑 <=i 的操作都用了，那么对于长度为 $2^{i-1}$ 的块内部顺序已定，毋宁看作一个整体 。

如果每一段都合法，则不执行操作；如果有一段不合法，则交换前后；如果有两段不合法，则分类讨论，最多有 $2$ 种交换方法 。

这样可能的情况 $2^n$ 种，总复杂度 $O(4^n)$ 。

注意别忘了乘阶乘 。