Luogu 3646 [APIO 2015] 巴厘岛的雕塑

传送门

总结 APIO 2015

  争取今天做完一套 QAQ。

  T1 我最多之能想到从高位向低位做，然后就完全不会了；T2 我想到了分情况讨论，但是没有建图成功；T3 首先 k=1 k = 1 $k = 1$ 的特例我是解决了的， k=2 k = 2 $k = 2$ 也想到了枚举分割点的方法，但是排序想错了……

  唉，太弱啦！

思路

  唉，我太弱了，什么都不会，完全做不来。

  我们可以从高位向低位贪心，在满足高位最小的前提下尝试让低位为 0 0 $0$，用 DP 解决这个问题。

  我们设当前答案为 ans$ans$$ans$，一开始答案全是 1 1 $1$。设 fp,i,j$f_{p,i,j}$$f_{p, i, j}$ 表示在保证前 p−1 p − 1 $p - 1$ 位为 ans a n s $ans$ 的前 p−1 p − 1 $p - 1$ 位的前提下，把前 i i $i$ 个数分成 j$j$$j$ 组能否让第 p p $p$ 位为零。转移要满足三个条件：一是要保证转移的新区间对应位为 0$0$$0$，二是要保证前面的状态为 true，三要保证新区间的前 p−1 p − 1 $p - 1$ 位为 1 1 $1$ 的位在 ans$ans$$ans$ 中不能为 0 0 $0$，否则会让 ans$ans$$ans$ 变大。换句话说，转移不能使 ans a n s $ans$ 变大。边界情况的答案类似。如果最后 fp,i,a∼b f p , i , a ∼ b $f_{p, i, a \sim b}$ 中存在 true，则这一位可以为 0 0 $0$，我们将 ans$ans$$ans$ 进行更新；否则我们不对 ans a n s $ans$ 进行更新。

  显然 p p $p$ 是不用保存的，所以我们只需要保存 fi,j$f_{i,j}$$f_{i, j}$。算法的时间复杂度为 O(40n3) O ( 40 n 3 ) $O(40 n^3)$，可以通过前面的所有测试点。

  最后一个测试点 a=1 a = 1 $a = 1$，显然这是一个 Special Instance，我们对其特殊考虑。发现，我们只需要求出满足某一位为 0 0 $0$ 的最小段数就可以了，所以我们设 fp,i$f_{p,i}$$f_{p, i}$ 表示在保证前 p−1 p − 1 $p - 1$ 为 ans a n s $ans$ 的前 p−1 p − 1 $p - 1$ 位的前提下，把前 i i $i$ 个数分成若干段使得第 p$p$$p$ 位为 0 0 $0$ 的最小段数。转移条件与前面的类似，时间复杂度降为 O(40n2)$O(40n^2)$$O(40 n^2)$。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int maxn = 2005;
int n, a, b, bitlen;
LL y[maxn];

#define RunInstance(x) delete new x
struct work1
{
    static const int maxN = 105;
    LL ans;
    bool f[maxN][maxN];
    work1() : ans()
    {
        for (int i = 0; i <= bitlen; i++)
            ans |= LL(1) << i;
        for (int i = bitlen; ~i; i--)
        {
            memset(f, 0, sizeof(f));
            for (int j = 1; j <= n; j++)
            {
                f[j][1] = ((y[j] | ans) <= ans) && !(y[j] & (LL(1) << i));
                for (int k = 2, to = std::min(j, b); k <= to; k++)
                {
                    for (int s = k - 1; s < j; s++)
                    {
                        LL delta = y[j] - y[s];
                        if ((delta | ans) <= ans && !(delta & (LL(1) << i)))
                            f[j][k] |= f[s][k - 1];
                    }
                }
            }
            bool bOk = false;
            for (int j = a; j <= b; j++)
                if (f[n][j])
                {
                    bOk = true;
                    break;
                }
            if (bOk)
                ans ^= LL(1) << i;
        }
        printOut(ans);
    }
};
struct work2
{
    LL ans;
    int INF;
    int f[maxn];

    work2() : ans()
    {
        memset(&INF, 0x3f, sizeof(INF));
        for (int i = 0; i <= bitlen; i++)
            ans |= LL(1) << i;
        for (int i = bitlen; ~i; i--)
        {
            memset(f, 0x3f, sizeof(f));
            f[0] = 0;
            if ((y[1] | ans) <= ans && !(y[1] & (LL(1) << i)))
                f[1] = 1;
            for (int j = 2; j <= n; j++)
                for (int k = 0; k < j; k++)
                {
                    LL delta = y[j] - y[k];
                    if ((delta | ans) <= ans && !(delta & (LL(1) << i)))
                        f[j] = std::min(f[j], f[k] + 1);
                }
            if (f[n] <= b)
                ans ^= LL(1) << i;
        }
        printOut(ans);
    }
};

void run()
{
    n = readIn();
    a = readIn();
    b = readIn();
    for (int i = 1; i <= n; i++)
        y[i] = readIn();
    for (int i = 2; i <= n; i++)
        y[i] += y[i - 1];
    bitlen = 63;
    while (bitlen && !(y[n] & (LL(1) << bitlen)))
        bitlen--;

    if (a != 1)
        RunInstance(work1);
    else
        RunInstance(work2);
}

int main()
{
    run();
    return 0;
}

总结

  唉，我太弱了，调了一下午，终于过了。

  这道题是按位贪心，利用 DP 确定答案。DP 的状态有些猎奇（千万不要忽视 DP 状态的定语），这种“在满足指定条件时才能转移”的方法应该是一种新思路吧。