CF 1469E A Bit Similar

抄完韩教代码感觉自己本来也应该想出这种方法的。。。

这道题搁置了有一段时间了

总结一下

本题给出字符串s，要求在其中截取长度为k的01串共n-k+1个，问能不能找出一个字典序最小的、长度也为k的01串，使得这个结果串与n-k+1中每一个串至少有一位相同。

其实答案也挺暴力的，但也有一定的特殊性。对于这n-k+1个串，如果题目中k的大小满足2 ^ k > n - k + 1则必定有解。

可以看出，如果我们把这长度为k的串以10进制形式表达，那么它的个数必定小于等于k位二进制数的个数，即2 ^ k个。因而严格大于才保证有解。

根据这一特性，因为题目中k <= 1e6，那么实际上n - k + 1也是近似1e6的规模，因而当k取到20就能解决本题的所有情况了。

对于k > 20的时候，我们需要补上前导0。

而对于其他情况，我们需要开个标记数组，将每个串的有效位（<=20）转为10进制加以标记，然后for一遍看有没有合法的。

如果有，我们补上前导0后再以二进制输出这个数就好了。如果没有就是NO。

 1 #include
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e6 + 10;
 5 
 6 int sum[N], vis[N << 1];
 7 
 8 int main(){
 9     ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
10     int t; cin >> t;
11     while(t--)
12     {
13         int n, k; cin >> n >> k;
14         string s; cin >> s;
15         for(int i = 1 ; i <= n ; i++){
16             sum[i] = sum[i - 1] + (s[i - 1] == '0');
17         }
18         int cnt = n - k + 1;
19         int bit;
20         for(int i = 20 ; i >= 0 ; i--){
21             if(cnt & (1 << i)){
22                 bit = i + 1;//多取一位，保证2 ^ bit > n - k + 1
23                 break;
24             }
25         }
26         bit = min(bit, k);
27         for(int i = 0 ; i <= n * 2 ; i++){//标记数组重置
28             vis[i] = 0;
29         }
30         
31         for(int i = n - bit + 1 ; i >= k - bit + 1 ; i--){//对于每个长为k的串，只看它的后bit位，i是串的头 
32             if(sum[i - 1] - sum[i - (k - bit) - 1])    continue;
33             int now = 0;
34             for(int j = i + bit - 1 ; j >= i ; j--){//j是串的尾巴，从后向前处理 
35                 if(s[j - 1] == '0'){
36                     now |= (1 << (i + bit - 1 - j));//把反着的标记，也即遇到0就在这一位或上1
37                 }
38             }
39             vis[now] = 1;
40         }
41         
42         int tag = 0;
43         for(int i = 0 ; i < (1 << bit) ; i++){
44             if(!vis[i]){//当前数字没有被标记过 
45                 tag = 1;
46                 cout << "YES" << endl;
47                 for(int j = 1 ; j <= k - bit ; j++){
48                     cout << "0";
49                 }//k - b个0
50                 for(int j = bit - 1 ; j >= 0 ; j--){
51                     if(i & (1 << j)){
52                         cout << "1";
53                     }else{
54                         cout << "0";
55                     }
56                 }
57                 cout << endl;
58                 break;
59             }
60         }
61         if(!tag)    cout << "NO" << endl;
62     }
63 
64     return 0;
65 }