题解：CF2136B Like the Bitset

__DATI_ghc__ · 2026-01-27 10:02:13 · 题解

CF2136B Like the Bitset 题解

我的第一篇题解，求赞

思路分析

本题要求构造一个长度为 n 的排列 p，满足对于所有 s[i]=1 的位置 i，其所在的所有长度不少于 k 的区间中，该位置的值不能是该区间的最大值。

从贪心的角度考虑：

对于每个 s[i] = 1 的位置，它所在的长度不少于 k 的区间中，不能有最大值等于 p[i]。

为了满足这个条件，我们可以将这些位置的值设为一个较小的数，比如 1。

但要注意，如果一个位置 i 被多个区间覆盖，那么我们不能简单地将所有这些位置都设为 1，因为这样会违反排列的唯一性。

更优的策略：

我们可以将所有 s[i]=1 的位置的值设为 1，然后将其他位置按顺序填入 2 到 n。

但这样可能仍然不满足条件，因为如果一个区间包含多个 s[i]=1 的位置，那么这些位置的值都为 1，而其他位置的值都大于 1，所以最大值不会是 1，满足条件。

做法

遍历字符串 s，找出所有 s[i]=1 的位置 对于这些位置，我们将其对应的排列值设为 1 其他位置按顺序填入 2 到 n。

AC Code

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int t;
    cin>>t;
    while(t--) 
    {
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int cnt=0;
        bool flag=true;
        for(int i=0; i<n; i++) 
        {
            if(s[i]=='1') 
            {
                cnt++;
                if(cnt==k) 
                {
                    flag=false;
                    break;
                }
            } 
            else cnt=0;
        }
        if(!flag) cout<<"NO"<<endl;
        else
        {
            cout<<"YES"<<endl;
            int l=1,r=n;
            for(int i=0; i<n; i++) 
            {
                if(s[i]=='0') cout<<r--<<" ";
                else  cout<<l++<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}

完结撒花！