B 题解————2019.10.16

相信他说的话，但不要当真

【题目描述】
有一个长度为 n 的自然数序列 a，要求将这个序列恰好分成至少 m 个连续子
段。每个子段的价值为该子段的所有数的按位异或。要使所有子段的价值按位与
的结果最大，输出这个最大值。
【输入描述】
第一行一个正整数 q，表示询问组数。
接下来 q 组输入，每组输入两行：
第一行两个正整数 n,m。
第二行 n 个正整数，描述序列 a。
【输出描述】
一行一个正整数，表示答案。
【输入样例】
1
5 3
1 2 3 4 5
【输出样例】
1
【数据范围】
20%的数据：n<=20
40%的数据：n<=100,ai<256
60%的数据：n<=100
100%的数据：1<=q<=12,1<=m<=n<=1000,0<=ai<2^30

题意：

q组数据。
给你一个长为n的非负数序列a。
定义一个区间的权值为区间的异或和。
定义一个划分的权值为分出的区间的权值的按位与的值。
要求至少把序列分成m个非空字段,求满足条件的划分的最大权值。

题解：
因为异或运算具有交换律且（x异或x = 0）,所以区间异或和可以由两个前缀异或和异或得到。
考虑从高位到低位确定答案的二进制位,然后考虑判断是否能分成至少m段。
如何判断是否能分成至少m段?
"能分成至少m段"与"最多能分成的段数>=m"等价。
令dp[i] = "a[1..i]这一段数最多能分成多少段"
转移就是直接枚举上一段的末尾j,如果[j+1,i]可以组成一段,那么就把dp[i] = max(dp[i],dp[j] + 1);
这样DP的复杂度是O(n^2)。
总复杂度就是O(q * log(值域) * DP) = O(30qn^2) ≈ 3.6 * 10^8,因为常数较小可以过。

值得一提的是,直接O(N^3)DP是错误的。因为它不满足最优子结构。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

int q,n,m,ans,x,s[1005],f[1005];

int rd(){
    int re=0,f=1;char c=getchar();
    while ((c<'0')||(c>'9')) {if (c=='-') f=-f;c=getchar();}
    while ((c>='0')&&(c<='9')) {re=re*10+c-'0';c=getchar();}
    return re*f;
}

int Max(int x,int y){
    return ((x>y)?x:y);
}

int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    q=rd();
    for (;q>0;--q){
        n=rd();m=rd();
        s[0]=0;
        for (int i=1;i<=n;++i){
            x=rd();s[i]=s[i-1]^x;
        }
        
        ans=0;
        for (int i=29;i>=0;--i){
            memset(f,0,sizeof(f));
            f[0]=1;
            for (int j=1;j<=n;++j){
                for (int k=0;k<j;++k) if (f[k]>0){
                    x=s[j]^s[k];
                    if (((ans&x)>=ans)&&((x&(1<<i))>0))
                        f[j]=Max(f[k]+1,f[j]);
                }
            }
            if (f[n]>m) ans|=(1<<i);
        }
        
        cout<<ans<<'\n';
    }
    return 0;
}

View Code

B 题解————2019.10.16

推荐阅读