当前位置：首页 > news >正文

状态压缩 + CF_Round_1039

news 2025/11/7 14:27:49

状态压缩算法

状压 DP 这个词语是不陌生的。久而久之，这就让我们产生了一个思维的刻板印象，认为状态压缩总是跟 DP 一起出现的，实则不然。状态压缩，顾名思义，就是对不容易形式化存储（例如一张地图、一种选多个的选择方案等）进行“压缩”存储方式。这里，主要是利用有关 Hash 的思想。Hash 告诉我们：如果一个东西不太能进行一定的有限制性的存储，那么我们不妨通过一定的方法使其变成另一种可存储的形式，且保证这种形式对于不同状态下的唯一性或近似唯一性。

状态压缩相关的算法一般都会将压缩后能唯一代表状态的那个数字用下标表示，即数组的编号。所以，这反而能倒退回状态压缩使用相关的条件性质，帮助我们快速判断。例如当我们在一道题中看到类似于 \(1\leq n\leq 16\)，或者 \(1\leq m\leq 10\) 等等的存在，并且推断出这题有关于状态的东西，那么除了暴力搜索，我们不妨向状态压缩的方向考虑。

状态压缩相关常用位运算。分析完题目，形式化题面后，你大概就会知道你想把什么状态（\(x\)）变成什么状态（\(y\)）。但是，有的时候分析如何位运算是一件令人头疼的事情。~~（不排除我练的太少了）~~ 所以，也许我们可以明确一下步骤，让思路清晰点。

\(\bf{首先，明确目标。}\)明确我们想要什么，例如把状态 \(x\) 第 \(i\) 位进行

\[\begin{aligned} &(x_i)_2 \&1(\text{or } 0),\\ &(x_i)_2 \| 1(\text{or } 0),\\ &(x_i)_2 \oplus 1(\text{or } 0),\\ &\overline{x_i}. \end{aligned} \]
等等。
\(\bf{其次，寻找规律，利用特性解决问题。}\)这里拿与和或来举例。与有一个特性，就是如果想要变成 \(1\) 必须用 \(1 \& 1\)。所以，这就显然让我们想到了如果想最终结果是 \(0\)，那么我们就可以用 \(0\) 去与。至于其他位置，则用 \(1\) 代替。因为 \(0\&1=0,1\&1=1\)，不变。同样地，对于或也是如此，我们用 \(1\) 去或，其他位置用 \(0\) 代替。有的时候遇到一些难以解决的问题，还可以用 \(+1,-1\) 等策略。
\(\bf{注意检查，其他位置为 1 必警惕。}\)刚刚我们提到了其他位置用 \(1\) 去代替的方案，但是请别忘了，除了 \(0\) 后面有 \(1\)， \(0\) 前面也是有 \(1\) 存在的。所以，我们除了要有 \((1<<i)-1\) ，还要有 \((1<<n)-1\)。这两个东西有机结合起来就是 \((1<<n)-(1<<i)-1\)。

尽管如此，可能还是有些题目比较难转移，这就要求我们十分熟悉位运算相关知识。

CF Round 1039

怎么说呢，先说一下比赛情况。第一题卡了半个小时，第二题也卡了半个小时。众所周知，一二题都是最简单的题，所以心态直接炸掉，打算后面的题慢慢写~~浑水摸鱼~~。第三题、第四题看了一下，然后直接看第五题，因为有个括号内部是 Easy Version。结果，第五题看了半天，突然想到了二分打法，于是开始打。代码打完后，发现总是出问题。于是我通过片面的调试发现这好像是玄学错误，等比赛结束后，却发现这不是玄学错误，是 check 函数打错了。

具体地，对每道题总结一下吧。

\(\text{\bf{第一题，考虑不全面。}}\)对于这类有点像模拟题，又有点像思维题的题目来说，只有考虑问题考虑全面，每一种情况都有所涉及，且能在样例以及自造数据中过去的代码，才有可能 AC。所以，这道题上来给到的时候，就不能心怀侥幸，而是要踏踏实实思考、踏踏实实写代码。
\(\text{\bf{第二题，注意审题及任意题目条件可能带来的特殊性质。}}\)这道题在写的时候，并没有注意到 \(a\) 数组的长度为 \(n\) 的情况下数字 \(1\) 到 \(n\) 各出现了一遍。也就由而推理不出最后的结论。当然，在审清题目的基础上，我们不妨对题目的部分特殊性质进行大胆猜测，根据时间复杂度的计算来缩小解法思考范围，从而不断去逼近正确答案。
\(\text{\bf{第三题，注意性质。}}\)虽然赛时没打出来，但是最终发现代码却异常简单。有的时候性质确实很难发现，但是不要急，我们需要冷静下来，通过多举例子、多用数据来发现规律、从特殊到一般的方法，尝试解决。
\(\text{\bf{第五题（Easy version），需要我们对问题进行转化。}}\)不论怎样，如果题目给一个特别离谱的要求，要么就是有特别离谱的解决方案，要么就是可以把离谱的问题转化成一个常见问题。可以从题目条件和题目要求入手。对于这题，我们要找最大的中位数，“最大”字眼就提示我们可以二分（逼近法）。接下来，一步一步展开就行了。
\(\text{\bf{对于任意的题目，敲代码时一定要思路清晰。}}\)有的时候，发现了解法可能就会开始疯狂敲代码，在这个过程中极容易犯低级错误，这是不可取的。也就是说，如果我们突然会了一道题灵光乍现，我们可以用笔记录在草稿纸上，然后开始思考如何构建这道题的代码。当所有代码全部构思完毕后再开始着手写，这样就会好很多，低级错误（尤其是难调的）也能规避不少。写完代码后不要立即运行，看看自己有没有什么不会报错的写法错误，例如 == 写成 = 等。