CF888E Maximum Subsequence 题解

题目链接：CF888E Maximum Subsequence

题意：

给定N个数，第i个数的值为Ai，你现在可以从中选择一些数字，问选出数字的和模P最大为多少。
输入第一行为N,P
第二行为N个数，第i个数字为Ai

1<=n<=35,1<=P<=1e9,0<=Ai<=1e9

模拟赛合并复杂度寄了，特写此篇题解

这个 $n\le 35$ 就很明显是折半搜索

我们用 $p,q$ 两个数组记录两部分搜索出来的所有可能的数

$2^{17}=131072$ ，因此数组完全够

关键在于如何合并两部分的答案

直接两层循环枚举那么复杂度依旧是 $O(2^n)$ （我就是这么寄的）

注意到 $p,q$ 满足 $0\le p_i,q_j<m$

因此对于每个 $p_i$ 我们只要找到最大的一个 $q_j$ 满足

$$p_i+q_j<m$$

正确性显然。

这样只要排个序然后维护双指针就好了

时间复杂度 $O(2^{n/2}\log 2^{n/2})$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(3e5+15)

int k,t,n,m,b,a[45],p[N],q[N];
void dfs1(int i,int sum)
{
    if(i==b){p[++k]=sum,p[++k]=(sum+a[b])%m; return;}
    dfs1(i+1,sum); dfs1(i+1,(sum+a[i])%m);
}
void dfs2(int i,int sum)
{
    if(i==n){q[++t]=sum,q[++t]=(sum+a[n])%m; return;}
    dfs2(i+1,sum); dfs2(i+1,(sum+a[i])%m);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;b=n>>1;
    for(int i=1; i<=n; i++) cin >> a[i];
    if(n==1) return cout << a[1]%m,0;
    dfs1(1,0);dfs2(b+1,0);
    int i=0,j=t,res=0;
    sort(p+1,p+1+k);sort(q+1,q+1+t);
    for(; i<=k; i++)
    {
        while(p[i]+q[j]>=m)--j;
        res=max(res,p[i]+q[j]);
    }
    res=max(res,(p[k]+q[t])%m);
    cout << res << '\n';
    return 0;
}