Luogu P3646 [APIO2015]巴厘岛的雕塑

时间:2024-08-15 15:35:44

深夜写题解系列,话说这题暑假的时候就在LOJ上做掉了,然后今天看到Luogu上有就去交了一下,发现没写过题解,赶紧来补一下

说句题外话APIO2015的题目好水啊

首先考虑按位取或的过程,很显然要从二进制位从高到低贪心,尽量地让这一位能取\(0\),那么就是考虑怎么判断这一位能否取到\(0\)的过程了

考虑直接设一个状态\(f_{i,j}\)表示把前\(i\)个数分成\(j\)段是否满足条件,最后看一下\(f_{n,i}(i\in [A,B])\)是否有\(1\)即可

那么转移也很简单,记录一下前缀和,然后向前枚举一个点转移,那么这段区间和在这一位上必须是\(0\)同时选择这一段不能使答案变大,这个详见代码的转移

因此我们现在有了一个\(O(n^3\log \sum Y_i)\)的做法,可以通过前4个Subtask

那么再看一下第5个Subtask有什么特殊之处,仔细一看会发现它的\(A=1\)!

那么很显然之前的DP之所以会慢就是因为考虑了答案的下界,但现在我们不用考虑了,直接考虑求出分开的最少段数,判断是否小于\(B\)即可,同样转移的方法和上面类似

所以这部分的复杂度是\(O(n^2\log \sum Y_i)\)的,两者综合即可通过此题

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int R=40,N=2005;
int n,l,r,a[N]; long long ans;
namespace Case1 //n<=100 solver
{
const int MN=105;
bool f[MN][MN];
inline bool check(CI idx)
{
RI i,j,k; memset(f,0,sizeof(f));
for (f[0][0]=i=1;i<=n;++i) for (j=1;j<=i;++j)
{
long long sum=a[i]; for (k=i-1;~k;--k)
f[i][j]|=f[k][j-1]&&(!((sum>>idx)&1))&&((((sum>>idx)<<idx)|ans)==ans),sum+=a[k];
}
bool flag=0; for (i=l;i<=r;++i) flag|=f[n][i]; return flag;
}
};
namespace Case2 //l=1 solver
{
int f[N];
inline bool check(CI idx)
{
RI i,j; for (memset(f,127,sizeof(f)),f[0]=0,i=1;i<=n;++i)
{
long long sum=a[i]; for (j=i-1;~j;--j)
{
if ((!((sum>>idx)&1))&&((((sum>>idx)<<idx)|ans)==ans))
f[i]=min(f[i],f[j]+1); sum+=a[j];
}
}
return f[n]<=r;
}
};
int main()
{
RI i; for (scanf("%d%d%d",&n,&l,&r),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=40;~i;--i) if (!(n<=100?Case1::check(i):Case2::check(i))) ans|=(1LL<<i);
return printf("%lld",ans),0;
}