题解：P16233 [蓝桥杯 2026 省 B] 双碳战略

· · 题解

P16233 双碳战略

第一次写题解，如有纰漏请指出。

提示

提示 A

如果给你一种情况，你可以快速地确定大致需要几步才可以到达这个排列吗？

提示 B

有一些情况是对称的，也就是对于两种情况 a, b 而言，对于每一个 i，有 a_i = \overline{b_i}。无论 i 是奇数还是偶数，这种转移都只用消耗 1 次操作，而且它们的数量是相等的。

提示 C

确定了以上问题之后，你可以找出每一种情况的最小步数有什么规律吗？

提示 D

使用隔板法。

题解

我们计灯光打开的状态为 1，关闭的状态为 0，可以得到一个 01 数组。

我们计数组中联通块的个数为出现连续 0 或 1 的块数，不难发现对于有 i 个联通块的数组 a，最少需要操作 i-1 次或 i 次，由于这两种操作对称，所以问题转化为如何求出 a 的个数。

我们不妨考虑操作 i-1 次的情况。如果数组中有 i 个联通块，那么这种情况的个数我们可以用隔板法计算。也就是有 i-1 个隔板把这些联通块分隔。易得对于有 i 个联通块的情况而言，数组的个数为 C^{i-1}_{n-1}，其中 C 为组合数。于是总操作次数为：

\boxed{\sum\limits_{i=1}^{n} {(2i-1) \cdot C^{i-1}_{n-1}}}

到这一步已经可以使用代码解决了（事实上我就是这么干的）。但我们尝试对公式继续化简。

通过变量代换 j = i-1，可化为：

\sum_{j=0}^{n-1} (2j+1) \cdot C^{j}_{n-1}

利用组合恒等式：

\sum_{j=0}^{m} C^{j}_{m} = 2^m,\quad \sum_{j=0}^{m} j \cdot C^{j}_{m} = m \cdot 2^{m-1}

其中 m = n-1，可得：

\sum_{j=0}^{m} (2j+1) \cdot C^{j}_{m} = 2m \cdot 2^{m-1} + 2^m = m \cdot 2^m + 2^m = (m+1)2^m = n \cdot 2^{n-1}

因此，原求和式的封闭形式为：

\boxed{n \cdot 2^{\,n-1}}