CF-Avito Code Challenge 2018-D-Bookshelves

ACM模版

描述

题解

按位贪心， dp check d p   c h e c k 。

稍微详细点说，那就是按照二进制位从高位开始往低位贪心，贪心第 bit b i t 位时，检查是否可以达成分为 k k 堆，每堆和的第 bit $bit$ 位为 1 1 ，如果可以则累计。检查的时候用 dp $dp$ 进行检查，检查的复杂度是 O(n3) O ( n 3 ) ，加上贪心的复杂度，一共是 O(an3) O ( a n 3 ) ， a a 的大小和 n $n$ 差不多，所以总得复杂度约莫是 O(n4) O ( n 4 ) ，这里需要注意一下，最高位不能从 50 50 开始， 51 51 也不行，会被 hack h a c k （血淋淋的教训），最好大于 55 55 ，因为最糟糕的情况时，给定 50 50 个数，分为一堆，每个数都是 250−1 2 50 − 1 ，那么和就是 250∗50−50>250∗25 2 50 ∗ 50 − 50 > 2 50 ∗ 2 5 ，……，所以最好开大一些保险。

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

const int MAXN = 70;

int n, k;
ll a[MAXN];
ll s[MAXN];
ll dp[MAXN][MAXN];

int main(int argc, const char * argv[])
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    ll base_ = 0;
    for (int bit = 60; bit >= 0; bit--)
    {
        ll cnt = 1ll << bit;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;

        for (int i = 1; i <= k; i++)        // i 堆
        {
            for (int j = 1; j <= n; j++)    // 前 j 个数
            {
                for (int k = 0; k < j; k++) // 前 k < j 个数
                {
                    if (dp[i - 1][k] && ((s[j] - s[k]) & cnt) && (((s[j] - s[k]) & base_) == base_))
                    {
                        dp[i][j] = 1;
                    }
                }
            }
        }

        if (dp[k][n])
        {
            base_ += cnt;
        }
    }

    cout << base_ << '\n';

    return 0;
}