[LOJ 2886] [APIO2015]巴厘岛的雕塑

Posted on | In , | Views:

题目链接

LOJ 2886

做法

由于题目中要把每段的和或起来，所以我们考虑一位一位考虑。
很自然的想到用$f_{i,j}$表示前$i$个数分为$j$段的最小美观值，转移的话就枚举$t..i$为一段，$f_{i,j}=Min(f_{i,j},f_{t-1,j-1}|(sum_i-sum_{t-1}))$，用$sum_i$表示到$i$为止的前缀和。
最后取$f_{n,a..b}$的最小值。
但是这个$dp$会有问题，由于或的特性，只要你分出的这些段中有一段在二进制这位上为$1$，这个二进制位就会对答案产生贡献。
举个例子。
不管怎么分段，最后答案中二进制第三位一定为1，而你在上面的$dp$中，可能会认为$010$是比$100$更优的，导致最后答案中二进制的第二位也产生了贡献，而这实际上是可以避免的。
那么我们怎么做呢，其实上面叉掉$dp$的过程已经给我们提示了。
我们从二进制的高位向低位枚举，如果最后答案这一位上可以是$0$，那么我们一定让这一位为$0$，当然前提是不会对前面更高的二进制位产生影响。
对于$n\le 100$的$subtask$，我们先枚举目前二进制位从大到小做到第$i$位，用$f_{j,k}$表示在满足前$i-1$位的前提下，将前$j$个数分成$k$段能否使得二进制的第$i$位上为$0$，转移与上面的$dp$类似，枚举这一段从$t$开始，令$s=sum[j]-sum[t-1]$，$ans$表示前$i-1$位的答案。
$s$要满足下面几个性质，我们认为这一段是合法的
(1) $s$的前$i-1$位必须是$ans$的子集
(2) $s$的第$i-1$位为$0$
如果最后$f_{n,a..b}$有$dp$值为$1$的状态，说明$ans$这一位可以放$0$，否则必须放$1$
复杂度为$O(63*n^3)$
无法通过最后一个$n\le 2000$的$subtask$
但是注意到最后一个$subtask$中，$a=1$
同样还是从高到低枚举二进制位，但改变$dp$状态，用$g_i$表示将前$i$个数分成符合条件最少需要几段。
转移与上面的$dp$一样
最后判一下是否$g_n\le b$就能判断$ans$这一位上能不能放$0$了。
复杂度$O(63*n^2)$
你可能会问为什么下面这种做法为什么只有$a=1$时可行。
那是因为这个$dp$没有单调性，也就是说你分成$i$段可行并不代表所有大于$i$段的分法均可性，所以取最小的不一定正确。
把两个$dp$拼起来就能通过此题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (2005)
using namespace std;
int n,a,b;
int data[N]; 
LL now,ans;
LL sum[N];
bool f[N][N];
int g[N];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int main(){
    read(n),read(a),read(b);
    for (int i=1;i<=n;i++) read(data[i]);
    for (int i=1;i<=n;i++){
        sum[i]=sum[i-1]+data[i];
    }
    if (n<=100){
        for (int i=62;i>=0;i--){
            memset(f,0,sizeof(f));
            f[0][0]=1;
            for (int j=1;j<=n;j++){
                for (int k=1;k<=j;k++){
                    for (int t=1;t<=j;t++){
                        LL s=sum[j]-sum[t-1];
                        if (f[t-1][k-1]&&(s&now&ans)==(s&now)&&(!(s&(1ll<<i)))) f[j][k]=1;
                    }
                }
            }
            bool flag=1;
            for (int j=a;j<=b;j++){
                if (f[n][j]) flag=0;
            }
            if (flag) ans+=1ll<<i;
            now+=1ll<<i;
        }
        printf("%lld",ans);
        return 0;
    }
    for (int i=62;i>=0;i--){
        memset(g,127,sizeof(g));
        g[0]=0;
        for (int j=1;j<=n;j++){
            for (int t=1;t<=j;t++){
                LL s=sum[j]-sum[t-1];
                if ((s&now&ans)==(s&now)&&(!(s&1ll<<i))) g[j]=min(g[j],g[t-1]+1);
            }
        }
        if (g[n]>b) ans+=1ll<<i;
        now+=1ll<<i;
    }
    printf("%lld",ans);
    return 0;
}