印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。

在这条主干道上一共有 NN 座雕塑,为方便起见,我们把这些雕塑从 11NN 连续地进行标号,其中第 ii 座雕塑的年龄是 YiYi 年。为了使这条路的环境更加优美,政府想把这些雕塑分成若干组,并通过在组与组之间种上一些树,来吸引更多的游客来巴厘岛。

下面是将雕塑分组的规则:

  • 这些雕塑必须被分为恰好 XX 组,其中 AXBA≤X≤B ,每组必须含有至少一个雕塑,每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。
  • 当雕塑被分好组后,对于每个组,我们首先计算出该组所有雕塑的年龄和。
  • 计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。

请问政府能得到的最小的最终优美度是多少?

备注:将两个非负数 PPQQ 按位取或是这样进行计算的:

  • 首先把 PPQQ 转换成二进制。
  • nPnPPP 的二进制位数,nQnQQQ 的二进制位数,MMnPnPnQnQ 中的最大值。PP 的二进制表示为 pM1pM2p1p0pM−1pM−2…p1p0QQ 的二进制表示为 qM1qM2q1q0qM−1qM−2…q1q0 ,其中 pipiqiqi 分别是 PPQQ 二进制表示下的第 ii 位,第 M1M−1 位是数的最高位,第 00 位是数的最低位。
  • PPQQ 按位取或后的结果是: (pM1ORqM1)(pM2ORqM2)(p1ORq1)(p0ORq0)(pM−1ORqM−1)(pM−2ORqM−2)…(p1ORq1)(p0ORq0) 。其中:
    • 0OR0=00OR0=0
    • 0OR1=10OR1=1
    • 1OR0=11OR0=1
    • 1OR1=11OR1=1

输入格式

输入的第一行包含三个用空格分开的整数 N,A,BN,A,B

第二行包含 NN 个用空格分开的整数 Y1,Y2,,YNY1,Y2,…,YN

输出格式

输出一行一个数,表示最小的最终优美度。

样例一

input

output

explanation

将这些雕塑分为 22 组,(8,1,2)(8,1,2)(1,5,4)(1,5,4) ,它们的和是 (11)(11)(10)(10) ,最终优美度是 (11OR10)=11(11OR10)=11 。(不难验证,这也是最终优美度的最小值。)

子任务

  • 子任务 1 (9 分)
    • 1N201≤N≤20
    • 1ABN1≤A≤B≤N
    • 0Yi10000000000≤Yi≤1000000000
  • 子任务 2 (16 分)
    • 1N501≤N≤50
    • 1ABmin{20,N}1≤A≤B≤min{20,N}
    • 0Yi100≤Yi≤10
  • 子任务 3 (21 分)
    • 1N1001≤N≤100
    • A=1A=1
    • 1BN1≤B≤N
    • 0Yi200≤Yi≤20
  • 子任务 4 (25 分)
    • 1N1001≤N≤100
    • 1ABN1≤A≤B≤N
    • 0Yi10000000000≤Yi≤1000000000
  • 子任务 5 (29 分)
    • 1N20001≤N≤2000
    • A=1A=1
    • 1BN1≤B≤N
    • 0Yi10000000000≤Yi≤1000000000

时间限制1s1s

空间限制64MB

 

第一次写数位dp

一开始第一眼想到dp 但是没想到数位dp 如果朴素的写dp 方程那么我不能保证每次or的最小就能使后面的or小

于是在leoly的介绍下,学习了数位dp

一共这些数加起来是2000*10^9

我们对于他的每一个二进制位去dp 然后贪心的从最高位开始做

那么前5个子任务 中的四个是100以内的

我们定义方程f[i][j]表示前1~i个间分j组 能否满足条件

这个满足条件的含义很多就是我现在这个数位能否是0

f[i][j]表示1~i分成j个,当前数位可以是0  tmp用来储存我此前已经确定了的最优值,每回做的时候我先认为这个地方可以是0 那么tmp这一位就需要+1 然后每次用位运算去判断能否满足条件

时间复杂度:100^3*log2(和最大)

那么这种复杂度显然子任务5是做不了的,观察到子任务5  A的范围就是1说明我们只要看满足条件(最优分法)的组数是否超过了B

 

样例的二进制

01000

00001

00010

00001

00101

00100    每次都是一个数位从上往下 注意小细节:如1LL<<  以及可能存在全是0的情况

 

 

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

2 条评论

enor2017 · 2018年3月19日 15:17

变量tmp的含义是什么?没看明白

    elijahqi · 2018年3月21日 15:46

    tmp的这个二进制为1时表示当前这个二进制位可以为0 位与位之间可以分开讨论 我前几位确定哪些可以为0的位置 就体现在tmp中是这个二进制位可以为1
    相当于是记得答案 但其实答案是tmp取反即可

发表评论