【Bzoj4069】【Luogu3646】巴厘岛的雕塑

来源和评测点

Apio2015 Bali Sculptures
Bzoj4069
Luogu3646
Uoj110

题目

【题目大意】
给出一些有序的值,在连续的情况下进行分组,
并且a<=组的数量<=b
求最小的 所有(组的和)的按位或值。
【输入格式】
输入的第一行包含三个用空格分开的整数N,A,B
第二行包含N个用空格分开的整数。
【输出格式】
输出一行一个数,表示最小的按位或值。
【限定条件】
子任务1 (9 分)
1<=N<=20
1<=A<=B<=N
0<=Yi<=1000000000

子任务2 (16 分)
1<=N<=50
1<=A<=B<=min{20,N}
0<=Yi<=10

子任务3 (21 分)
1<=N<=100
A=1
1<=B<=N
0<=Yi<=20

子任务4 (25 分)
1<=N<=100
1<=A<=B<=N
0<=Yi<=1000000000

子任务5 (29 分)
1<=N<=2000
A=1
1<=B<=N
0<=Yi<=1000000000
【输入样例】
6 1 3
8 1 2 1 5 4
【输出样例】
11
【样例解释】
分为2组,(8,1,2)和(1,5,4),它们的和是 (11) 和 (10),
最终优美度是 (11 OR 10)=11,不难验证,这也是最终优美度的最小值。

刷题记录

1h

分析

请先思考后再展开

显然,直接写dp是不行的,因为区间小并不代表最终小。
既然是按位或,可以考虑数位dp。
然后区间静态求和,前缀和是不能少滴。

然后网上看到一句话:

对于数位极值问题,应该贪心地优先从高位开始考虑,
极小值优先0,极大值优先1

然后就可以愉快地考虑dp了:
假设现在在努力地把右数第k位变成0,
那么我们就要尽量让所有和的第k位为0。
并且前面的已经解决,用tmp表示现在已经能变成0的位置
(所以最后输出答案就是tot-tmp)

然后f[i][p]表示前面i个数分p段能否第k位是0(状压),然后n^2来常规dp即可
转移条件:( (sum[i]-sum[j])&tmp )==0 (也就是tmp为1的地方这一段的和必须是0,否则前功尽弃)
那么这个复杂度是O(60*n^3)的,而最后一个子任务是2000,会TLE
然后发现这一次,A=1,那么怎么利用这个条件呢?
考虑贪心一波:因为现在的限制只有B,那么当然是段数越小,成功率越高。
设g[i]表示前i个数最小分多少段能第k位是0
成功变成O(60*n^2)

upd 2019.3.29:
一年后回来看,发现这是一道sb题……把新的代码换了上去
值得一提的是,这份代码你把task2里面的check,包括return删除,可以得到82的好成绩qwq
也就是说每次都return了我希望的值,我也不知道为什么

代码

请先思考后再展开
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=1e1+2;
const ll MOD=1e13;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
int n,L,R;
ll a[2100],bin[50];
namespace task1
{
const int MAX_N=2100;
int f[MAX_N];
bool check(ll mask)
{
memset(f,0x3f,sizeof f);f[0]=0;
for(int i=1;i<=n;i++) for(int j=0;j<i;j++)
if( ((a[i]-a[j])&mask)==0 ) chmin(f[i],f[j]+1);
return f[n]<=R;
}
};
namespace task2
{
const int MAX_N=110;
bool f[MAX_N][MAX_N];
bool check(ll mask)
{
memset(f,0,sizeof f);f[0][0]=1;
for(int i=1;i<=n;i++) for(int k=1;k<=R;k++) for(int j=0;j<i;j++)
if( ((a[i]-a[j])&mask)==0 and f[j][k-1] ) {f[i][k]=1;break;}
for(int i=L;i<=R;i++) if(f[n][i]) return 1;
return 0;
}
};
void main()
{
bin[0]=1;for(int i=1;i<=41;i++) bin[i]=bin[i-1]<<1;
n=qread();L=qread();R=qread();
for(int i=1;i<=n;i++) a[i]=a[i-1]+qread();
ll ans=0;
for(int i=40;i>=0;i--)
{
if(L==1 and task1::check(ans|bin[i])) ans|=bin[i];
else if(L!=1 and task2::check(ans|bin[i])) ans|=bin[i];
}
write((bin[41]-1)^ans);
}
};
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a4aa.html
转载请注明出处,谢谢!