題目鏈接：點(diǎn)擊查看

題目大意：給出 $n$ 個(gè) $01$ 序列表示二進(jìn)制狀態(tài)，問選擇至少 $?\frac{n}{2}?$ 個(gè)狀態(tài)進(jìn)行位運(yùn)算的與運(yùn)算后得到的答案中，$1$ 的位數(shù)最多的答案

題目分析：考慮最后需要求得的答案，一定是 $?\frac{n}{2}?$ 個(gè)狀態(tài)中，其中一個(gè)狀態(tài)的子集，于是我們就可以去枚舉然后統(tǒng)計(jì)答案

考慮隨機(jī)數(shù)，每隨機(jī)抽一個(gè)狀態(tài)，不在最后 $?\frac{n}{2}?$ 個(gè)數(shù)的概率為 $\frac{1}{2}$，我們可以抽 $50$ 次甚至更多，抽不中的概率就是 $(\frac{1}{2}{)}^{50}$，這個(gè)概率以及近似無限接近百分百了

現(xiàn)在的問題就轉(zhuǎn)換為了，給定一個(gè)狀態(tài)，如何快速枚舉其子集并統(tǒng)計(jì)其出現(xiàn)的個(gè)數(shù)

最樸素的做法就是，對于每個(gè)狀態(tài)狀壓枚舉其子集，然后維護(hù)一個(gè) $cnt$ 數(shù)組計(jì)數(shù)，這個(gè)復(fù)雜度是 $O(n?2^p)$ 的

所以考慮用狀壓 $dp$ 去維護(hù)前綴和的思想，假設(shè)現(xiàn)在有兩個(gè)狀態(tài) $i,j$，滿足 $i$ 是 $j$ 的一個(gè)子集，即 $i\&j=j$，則根據(jù)前綴和的思想，可以有 $cn{t}_j+=cn{t}_i$

利用以上的優(yōu)化，我們可以 $O(np)$ 處理出初始的 $cnt$ 數(shù)組，然后 $O(p?2^p)$ 狀壓 $dp$ 維護(hù)一下前綴和就好了

剩下的 $O(p?2^p)$ 再枚舉一下答案更新就可以了

代碼：

// Problem: D. Love-Hate // Contest: Codeforces - Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2) // URL: https://codeforces.com/contest/1523/problem/D // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; mt19937_64 eng(time(NULL)); LL s[N]; int cnt[(1<<15)+100]; int a[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m,p;read(n),read(m),read(p);for(int i=1;i<=n;i++) {string str;cin>>str;for(int j=0;j<m;j++) {if(str[j]=='1') {s[i]|=(1LL<<j);}}}iota(a+1,a+1+n,1);shuffle(a+1,a+1+n,eng);int ans=-1;string res;for(int t=1;t<=min(50,n);t++) {memset(cnt,0,sizeof(cnt));int p=a[t];vector<int>bits;for(int j=0;j<m;j++) {if((s[p]>>j)&1) {bits.push_back(j);}}int sz=bits.size();for(int i=1;i<=n;i++) {//n*pint state=0;for(int j=0;j<sz;j++) {if((s[i]>>bits[j])&1) {state|=(1<<j);}}cnt[state]++;}for(int j=0;j<sz;j++) {//p*2^pfor(int i=0;i<1<<sz;i++) {if(((i>>j)&1)==0) {cnt[i]+=cnt[i|(1<<j)];}}}for(int i=0;i<1<<sz;i++) {if(cnt[i]>=(n+1)/2&&__builtin_popcount(i)>ans) {ans=__builtin_popcount(i);res=string(m,'0');for(int j=0;j<sz;j++) {if((i>>j)&1) {res[bits[j]]='1';}}}}}cout<<res<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1523D Love-Hate(随机数+状压dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。