题解 CF888E 【Maximum Subsequence】

· · 题解

Blog
早期作品，不喜轻喷。
切这道题用了好长时间，所以想发篇题解作为纪念
首先，我们认真观察题目数据（面向数据做题是个好习惯），发现题目的n竟然只有35，我们顿时感到打暴力的机会来了：

2^n枚举？

是个好办法。
只可惜我们发现2^{35}=34359738368,并不能过掉所有数据点，于是考虑优化。

分治：

考虑把这n个数分成两组（当然要尽量平均），对两组数据分别实施暴力，并把结果存起来（事实上是可以存下来的：2^{18}=262144)。

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);
}

这样一来，我们就得到了原序列分成两半的结果，这两个序列中的数两两组合就可以得到我们要的结果。
等等，两两组合？这样的复杂度不是和纯暴力一样吗？
这时候就需要我们贪心地看问题了：
我们发现：对于序列p中的每一个数p_i，在序列q中若能找到一个与之相加小于m的最大的数q_j,其他所有的与p_i的和小于m的数都不会比它更优,即q_j比序列q中所有比它小的数都更优。
对于q中的每一个数，满足相同条件的p_i也具有同样的性质。
我们想到一种对于p,q线性的算法：把p和q排一遍序，把指向p数组的指针i和指向q数组的指针j分别按上面所说的条件向右和向左移动，同时更新ans。
这时我们就只剩下p_i+q_j>m的情况了，由于在之前已经取过模，p_i+q_j必定小于2m，所以我们就只需要用p,q的最大值之和去更新一下ans就好了。
代码：

int main(){
    R int i,j,ans=0;
    n=read(),m=read(),b=n>>1;
    for(i=1;i<=n;++i) a[i]=read();
    if(n==1) printf("%d",a[1]%m),exit(0);
    dfs1(1,0),dfs2(b+1,0),i=0,j=t;
    sort(p+1,p+k+1),sort(q+1,q+t+1);
    while(i<=k){
        while(p[i]+q[j]>=m) --j;
        ans=max(ans,p[i]+q[j]),++i;
    }
    ans=max(ans,p[k]+q[t]-m);
    printf("%d",ans);
    return 0;
}

注意这里特判了一下n=1的情况，我被这个点坑了一次。
整段代码：

#include<bits/stdc++.h>
#define R register
#define S 300000
using namespace std;
int a[40],p[S],q[S],k,t,n,m,b;
inline int max(int x,int y){return x>y? x:y;}
inline int read(){
    R int f=0;  R char ch=getchar();
    while(ch<48||ch>57) ch=getchar();
    while(ch>47&&ch<58) f=(f<<3)+(f<<1)+(ch^48),ch=getchar();
    return f;
}
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);
}
int main(){
    R int i,j,ans=0;
    n=read(),m=read(),b=n>>1;
    for(i=1;i<=n;++i) a[i]=read();
    if(n==1) printf("%d",a[1]%m),exit(0);
    dfs1(1,0),dfs2(b+1,0),i=0,j=t;
    sort(p+1,p+k+1),sort(q+1,q+t+1);
    while(i<=k){
        while(p[i]+q[j]>=m) --j;
        ans=max(ans,p[i]+q[j]),++i;
    }
    ans=max(ans,p[k]+q[t]-m);
    printf("%d",ans);
    return 0;
}