E. Maximum Subsequence(折半搜索,状态压缩)

$折半搜索$

$记得今年新生赛的时候就考了这题,当时一脸懵逼,现在依然是这样...$

$不过确实很巧妙啊$

$一个一个搜索,有2^{35}种可能$

$但如果分成两个集合分别搜索$

$然后对于第一个集合,在第二个集合里去二分找最优$

$复杂度却只有2^{18},真厉害呐$

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=3e5+10; ll a[maxn],b[maxn],c[maxn],top1,top2,n,m,ans; void dfs(int u,int end,ll s[],ll &top,ll sumn) { if(u==end+1) { s[++top]=sumn; ans=max(ans,sumn);//单独拼成的答案可能也是最优的 return; } dfs(u+1,end,s,top,(sumn+a[u])%m ); dfs(u+1,end,s,top,sumn); } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]%=m; } dfs((ll)1,n/2,b,top1,(ll)0); dfs(n/2+1,n,c,top2,(ll)0); sort(c+1,c+1+top2); for(int i=1;i<=top1;i++) { int primt = m-b[i]-1;//最优的 int l=1,r=top2,mid,index=0; while(r>=l) { mid = l+r>>1; if(c[mid]<=primt) l=mid+1,index=mid; else r=mid-1; } ans=max(ans,(b[i]+c[index])%m); } cout<<ans; }