I love max and multiply HDU - 6971

題意：

數組a和b，現在構造一個數組c，使得c[k]=max(a[i] * b[j]) , i&j>=k
求數組c的和

題解：

我們可以考慮求出所有Dk=max(Ai * Bj)并滿足i&j=k，然后再從后向前取，但是i&j=k不好求，那就改成Dk=max(Ai * Bj),滿足k∈i&j
k∈i&j，我們可以分別求k∈i和k∈j的情況
就比如：
k = 1010，k∈i&j，
i&j可以是：
1010
1011
1110
1111
那么我們就讓i和j分別取這幾個值求最大值，因為題目中存在負數，負數乘負數可能值更大，所以我們同時記錄Ai和Bj的最大值和最小值
在代碼實現中，當我們循環到1010，我們就將其值賦給其子集，這樣就實現了k屬于i&j
最后記得從后向前取最大(為什么還要這步呢？就比如k=1010，我們當前得到的最大值是1010所屬于的集合，但是有些集合大于k但是k不屬于，如果i<j,那么j的集合一定大于i，所以j的集合也是滿足i的條件的，反之不一定，所以倒著賦值)

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=998244353,INF=0x3f3f3f3f; const double eps=1e-6;int n; int a[N],b[N]; LL mx1[N],mx2[N],mi1[N],mi2[N],c[N]; void solve(){scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&a[i]);for(int i=0;i<n;i++) scanf("%d",&b[i]);int all=(int)log2(n)+1;for(int i=0;i<1<<all;i++) {mx1[i]=mx2[i]=-INF;mi1[i]=mi2[i]=INF;c[i]=-1e18;}for(int i=0;i<n;i++) mx1[i]=mi1[i]=a[i];for(int i=0;i<n;i++) mx2[i]=mi2[i]=b[i];for(int i=0;i<all;i++) {for(int j=0;j<1<<all;j++) {if(j>>i&1) {mx1[j^(1<<i)]=max(mx1[j^(1<<i)],mx1[j]);}}}for(int i=0;i<all;i++) {for(int j=0;j<1<<all;j++) {if(j>>i&1) {mi1[j^(1<<i)]=min(mx1[j^(1<<i)],mx1[j]);}}}for(int i=0;i<all;i++) {for(int j=0;j<1<<all;j++) {if(j>>i&1) {mx2[j^(1<<i)]=max(mx2[j^(1<<i)],mx2[j]);}}}for(int i=0;i<all;i++) {for(int j=0;j<1<<all;j++) {if(j>>i&1) {mi2[j^(1<<i)]=min(mi2[j^(1<<i)],mi2[j]);}}}LL now=1ll*INF*INF;for(int i=0;i<n;i++) {if(mx1[i]!=INF&&mx2[i]!=INF) c[i]=max(c[i],mx1[i]*mx2[i]);if(mi1[i]!=-INF&&mi2[i]!=-INF) c[i]=max(c[i],mi1[i]*mi2[i]); if(mx1[i]!=INF&&mi2[i]!=-INF) c[i]=max(c[i],mx1[i]*mi2[i]);if(mi1[i]!=-INF&&mx2[i]!=INF) c[i]=max(c[i],mi1[i]*mx2[i]);}for(int i=n-2;i>=0;i--) c[i]=max(c[i],c[i+1]);LL ans=0;for(int i=0;i<n;i++) ans+=c[i]%mod,ans+=mod,ans%=mod;printf("%lld\n",ans); } int main() {int T; scanf("%d",&T);while(T--) {solve(); }return 0; }

總結

以上是生活随笔為你收集整理的I love max and multiply HDU - 6971（详细解答）的全部內容，希望文章能夠幫你解決所遇到的問題。

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