很久没打了，明显手生，AB一共WA了四发，CD切的很快，E毫无思路。
接下来一是应该复习算法并且能裸写，减少对模板的依赖；二是加强对div1C左右难度题目的训练。
题意
定义两个串$a$,$b$有点相似如下：$a$与$b$长度相等，且至少存在一个位置$i$，使得$a_i = b_i$。
$q$组测试，每组第一行两个整数$n$与$k$，第二行给你一个长度为$n$的$01$串$s$。
要求构造一个长度为$k$的01串，使得$t$与$s$中的每一个长度为$k$的子串都有点相似，若存在多个合法答案则$t$为字典序最小的。
若存在答案，则在第一行输出”YES”并在第二行输出$t$，否则打印”NO”。
思路
对于两个长度相同的01串$a$与$b$，只有一种情况两个不有点相似：两个每一位都不同，即$a$按位取反得到$b$。
$s$的子串一共有$n-k+1$个，最多$10^6$个，$10^6<2^{20}=1048576$。
所以当位数达到20时，一定能找到一种合法方案。从小到大枚举，前面的$k-20$位输出0即可。
若$k$小于20位，暴力枚举，否则将每个串的最后20位取反并插入字典树并枚举。
若$k>20$时，如果某一个子串前$k-20$位存在0，因为构造的$t$串前$k-20$一直保持为0，则该子串可以忽略掉。否则将每个子串的后20位插入字典树。
用$int$枚举$2^{20}$即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=3e6+5,inf=0x3f3f3f3f,mod=1000000007;
signed main(signed argc, char const *argv[])
{
int t,n,k;
string s;
cin>>t;
while(t--)
{
cin>>n>>k>>s;
for(int i=0;i<s.length();i++)
s[i]=(s[i]=='0'?'1':'0');
bool ok=0;
int ans=0,len=min(20,k);
int mask=(1<<len)-1,now=0,pre1=-inf;
for(int i=0;i<k-1;i++)
{
now<<=1;
now+=(s[i]=='1');
now&=mask;
if(k>20&&i<k-20&&s[i]=='1')
pre1=i;
}
vector<bool>mp(maxn,0);
for(int i=k-1;i<n;i++)
{
if(k>20&&i>=20&&(now&(1<<(19))))
pre1=i-20;
now<<=1;
now+=(s[i]=='1');
now&=mask;
if(k<=20||(k>20&&(pre1<=i-k)))
mp[now]=1;
}
while(ans<(1ll<<len)&&mp[ans])
ans++;
if(ans<(1ll<<len))
{
cout<<"YES"<<'\n';
for(int i=0;i<k-len;i++)
cout<<0;
for(int i=len-1;i>=0;i--)
cout<<((ans&(1ll<<i))?'1':'0');
cout<<endl;
}
else
cout<<"NO"<<endl;
}
return 0;
}
|