题目描述
传送门
题目大意：将n个数分成若干段，求每段和按位或的最小值。段数限制在
[A,B]
题解
这道题的后两个子任务需要分开做。 子任务1：
1≤N≤100,1≤A≤B≤N,0≤Yi≤1000000000
按位或的最小值，位运算的每一位是互不影响的，那么我们可以从高位到低位，依次考虑当前位是否能是0，如果能上是0的话，自然当前位取零。 假设到当前位x现在的答案是ans,我们除了尽可能使当前位为0以外，还要是之前确定的位不发生变化。
f[i][j]
表示到第i个，分成了j组，当前位是0是否可以。 令
t=ans+mi[x]−1
,表示当前位是0，后面的位数0,1可以任选，都置1的话，进行或运算不影响结果。而且保证了前面确定的位不变。 如果
t|(sum[k]−sum[i])=ans
,那么
f[i][j+1]|=f[k][j]
最后判断
f[n][A−B]
中是否有可行的。
子任务2：
1≤N≤2000,A=1,1≤B≤N,0≤Yi≤1000000000
范围变大了，不能再用
O(n3)
的做法了。 发现
A=1
，也就是没有下界。那么只要到每个位置最小的分组数即可。如果最后
g[n]>B
,则不可行。 如果
t|(sum[k]−sum[i])=ans
, 那么
g[i]=min(g[k]+1,g[i])
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long
#define N 2003
using namespace std;
int A,B,f[
103][
103],g[N],n;
LL val[N],sum[N],mi[N];
void solve()
{
LL ans=
0;
for (
int t=
43;t>=
0;t--) {
ans+=(mi[t]-
1);
memset(f,
0,
sizeof(f));
f[
0][
0]=
1;
for (
int i=
1;i<=n;i++)
for (
int j=
0;j<i;j++)
for (
int k=
0;k<=j;k++)
if ((ans|(sum[i]-sum[j]))==ans)
f[i][k+
1]|=f[j][k];
bool pd=
false;
for (
int i=A;i<=B;i++) pd|=f[n][i];
if (pd) ans-=(mi[t]-
1);
else ans++;
}
printf(
"%lld\n",ans);
}
void solve2()
{
LL ans=
0;
for (
int t=
43;t>=
0;t--) {
ans+=mi[t]-
1;
memset(g,
127/
3,
sizeof(g));
g[
0]=
0;
for (
int i=
1;i<=n;i++)
for (
int j=
0;j<i;j++)
if ((ans|(sum[i]-sum[j]))==ans)
g[i]=min(g[j]+
1,g[i]);
if (g[n]<=B) ans-=(mi[t]-
1);
else ans++;
}
printf(
"%lld\n",ans);
}
int main()
{
scanf(
"%d%d%d",&n,&A,&B); mi[
0]=
1;
for (
int i=
1;i<=
63;i++) mi[i]=mi[i-
1]*
2;
for (
int i=
1;i<=n;i++)
scanf(
"%lld",&val[i]);
for (
int i=
1;i<=n;i++) sum[i]=sum[i-
1]+val[i];
if (A==
1) solve2();
else solve();
return 0;
}
