題意

有n張有序的卡片，每張卡片上恰有[1,m]中的每一個數(shù)，數(shù)字寫在正面或反面。每次詢問區(qū)間[l,r]，你可以將卡片上下顛倒，問區(qū)間中數(shù)字在卡片上方的并的平方和最大是多少。q,n*m≤1,000,000。

---

?

思考

一個很重要的性質，若區(qū)間長度≥log m+1,則答案為12+22+33+...+m2。

為什么?可以動態(tài)地觀察。對于沒有出現(xiàn)的數(shù)字集合，當前卡片上的數(shù)字至少有一半的數(shù)字出現(xiàn)在正面或者是反面，因此每次你可以將未出現(xiàn)的數(shù)字的數(shù)量至少減少一半。每次重復上次操作。

對于長度很小的，我們暴力初始化答案。可以發(fā)現(xiàn)，若我們強制不選某一個數(shù)字，則一定只有一種方法，即每張卡片有它的均朝下。

因此最多只有m種方案（可能有重復的）。同時，若區(qū)間中的方案數(shù)＜pow(2,區(qū)間長度)，必然有方法使得所有數(shù)字都至少有一個在上方。

---

?

不需要代碼的代碼

1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long int ll; 4 const ll maxn=1E6+5; 5 ll min(ll x,ll y){return x<y?x:y;} 6 ll n,m,q,x,y,g,f[maxn][20],vis[maxn],ti,sum[maxn],v[maxn],bel[maxn]; 7 vector<int>a[maxn]; 8 int main() 9 { 10 ios::sync_with_stdio(false); 11 cin>>n>>m>>q; 12 for(int i=1;i<=m;++i)g+=i*i; 13 for(int i=1;i<=n;++i) 14 { 15 cin>>x; 16 for(int j=0;j<=m;++j)a[i].push_back(0); 17 for(int j=1;j<=x;++j) 18 { 19 cin>>y; 20 a[i][y]=1; 21 } 22 } 23 for(int l=1;l<=n;++l) 24 { 25 for(int i=1;i<=m;++i)bel[i]=0; 26 for(int r=l;r<=min(n,l+19);++r) 27 { 28 ++ti; 29 if(l!=r&&f[l][r-l]==g){f[l][r-l+1]=g;continue;} 30 int cur=1<<(r-l+1); 31 for(int i=1;i<=m;++i) 32 { 33 if(a[r][i])bel[i]|=1<<(r-l);//1或0其實是等價的 34 if(vis[bel[i]]!=ti) 35 { 36 vis[bel[i]]=ti; 37 sum[bel[i]]=0; 38 --cur; 39 } 40 } 41 if(cur>0)f[l][r-l+1]=g; 42 else 43 { 44 for(int i=1;i<=m;++i)sum[bel[i]]+=i*i; 45 for(int i=1;i<=m;++i)f[l][r-l+1]=max(f[l][r-l+1],g-sum[bel[i]]); 46 } 47 } 48 } 49 while(q--) 50 { 51 cin>>x>>y; 52 if(x>y)swap(x,y); 53 if(y-x+1>=20)cout<<g<<endl; 54 else cout<<f[x][y-x+1]<<endl; 55 } 56 return 0; 57 } View Code

?

轉載于:https://www.cnblogs.com/GreenDuck/p/10601539.html

總結

以上是生活随笔為你收集整理的19_03_26校内训练[魔法卡片]的全部內容，希望文章能夠幫你解決所遇到的問題。

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