E. A Bit Similar

代碼抄的這份題解

找到一個長度為k的串使得在s長度為k的子串中，對于所有子串答案串都至少有一位相同。也就是如果將s長度為k的子串全部按位取反，那么答案串不能與這些反串匹配。

現在問題轉化成，找到一個答案串（字典序最小），不能和$n?k+1$個串匹配。

對于二進制位來說，由于$n?k+1<2^{20}$，也就是我們只需要20位就一定能過找到一個和那些串都不同的串，因此可以直接暴力枚舉后面20位（k-20位都填0）

對于找到一個不與$n?k+1$匹配的串，也可以把他們哈希，然后用map記錄下來，答案還是枚舉，但是感覺寫起來有點麻煩，就沒寫（不太會寫）

下面有個很巧妙的做法，如果$n?k+1$個串中前面$k?20$位存在1就不用管，因為我們枚舉的答案串前面$k?20$位都是0，于是一個數組就可以記錄那些東西出現過（轉化為二進制）

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<bitset> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,int> pli; typedef pair<int,int> pii; const ll mod=1e9+7; const int N=1000010; bool ban[N]; int pre[N]; int main() {IO;int T=1;cin>>T;while(T--){int n,k;string s;cin>>n>>k>>s;int m=0;while(m<k&&(1<<m)<=n) m++;for(int i=0;i<=n&&i<(1<<m);i++) ban[i]=0;for(int i=0;i<n;i++) pre[i+1]=pre[i]+(int)(s[i]=='0');for(int i=0;i+k-1<n;i++){if(pre[i]!=pre[i+k-m]) continue;int mask=0;for(int j=0;j<m;j++)if(s[i+k-1-j]=='0')mask^=1<<j;if(mask<=n) ban[mask]=1;}int ans=0;while(ans<(1<<m)&&ban[ans]) ans++;if(ans==(1<<m)) cout<<"NO\n";else{cout<<"YES\n";for(int i=0;i<k-m;i++) cout<<0;for(int i=m-1;i>=0;i--) cout<<(int)((ans>>i)&1);cout<<'\n';}}return 0; }

總結：對于至少1個考慮容斥轉化
要加油哦~

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的codeforces1469 E. A Bit Similar的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。