CodeForces888E Maximum Subsequence（折半枚举+two-pointers）

题意

给定一个包含$n$个数的序列$a$，在其中任选若干个数，使得他们的和对$m$取模后最大。（$n\leq 35$）

题解

显然，$2^n$的暴枚是不现实的...，于是我们想到了折半枚举，分成两部分暴枚，然后考虑合并，合并的时候用two-pointers思想扫一遍就行了。

其实这是一道折半枚举+Two-Pointers的很好的练手题

//最近CodeForces有点萎，可能会JudgementError，但已经评测过了，能AC，多交几次应该可以

#include <cstdio>

#include <algorithm>

using std::max;

using std::sort;

const int N = 40, K = 19;

int n, m, k, ans, totx, toty;

long long a[N], x[1 << K], y[1 << K];

template <typename T>

inline void read(T &x) {

    x = 0; char ch = getchar();

    while (ch < '0' || ch > '9') ch = getchar();

    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();

}

void dfsx (int i, long long sum) {

    if (i > k) { x[++totx] = sum % m; return ; }

    dfsx (i + 1, sum + a[i]);

    dfsx (i + 1, sum);

}

void dfsy (int i, long long sum) {

    if (i > n) { y[++toty] = sum % m; return ; }

    dfsy (i + 1, sum + a[i]);

    dfsy (i + 1, sum);

}

int main () {

    read(n), read(m), k = n >> 1;

    for (int i = 1; i <= n; ++i) read(a[i]);

    dfsx(1, 0), dfsy(k + 1, 0);

    sort(&x[1], &x[totx + 1]), sort(&y[1], &y[toty + 1]);

    int l = 1, r = toty;

    while (l <= totx) {

        while (r && x[l] + y[r] >= m) --r; if(!r) break;

        ans = max(ans, int((x[l] + y[r]) % m)), ++l;

    }

    printf ("%d\n", ans);

    return 0;

}

巴特西

CodeForces888E Maximum Subsequence（折半枚举+two-pointers）

题意

题解

最新文章

热门文章