CF2136B Like the Bitset题解

DoctorRyan · 2025-12-14 10:18:26 · 题解

CF2136BLike the Bitset题解

题目描述

给定一个长度为 n 的二进制字符串 s，以及一个整数 k。

Aquawave 想要构造一个长度为 n 的排列 p，使得对于所有 1 \le i \le n 且 s_i = \mathtt{1} 的下标 i，满足如下条件：

• 对于每一个长度不少于 k 的区间 [l, r]（即 r - l + 1 \geq k）且覆盖位置 i（即 l \leq i \leq r），该区间内的最大元素 p_l, p_{l+1}, \ldots, p_r 中，最大值不能等于 p_i。

请你找出这样一个排列，或者判断不存在这样的排列。

题目思路

如果有 k 个连续的 1 ，那么肯定无法满足条件（至于为什么就不用我说了吧）

如果没有，那么将 1 的位置都赋值为最小的那些数，其余位置（0的位置）赋值为最大的那些数即可

总结

这是一道比较简单的题，如果代码按照题目思路写就可以了。如果还是不会，可以私信我一对一辅导。