传送门
总结 APIO 2015
争取今天做完一套 QAQ。
T1 我最多之能想到从高位向低位做,然后就完全不会了;T2 我想到了分情况讨论,但是没有建图成功;T3 首先
k=1
k
=
1
的特例我是解决了的,
k=2
k
=
2
也想到了枚举分割点的方法,但是排序想错了……
唉,太弱啦!
思路
唉,我太弱了,什么都不会,完全做不来。
我们可以从高位向低位贪心,在满足高位最小的前提下尝试让低位为
0
0
,用 DP 解决这个问题。
我们设当前答案为 ans,一开始答案全是
1
1
。设 fp,i,j 表示在保证前
p−1
p
−
1
位为
ans
a
n
s
的前
p−1
p
−
1
位的前提下,把前
i
i
个数分成 j 组能否让第
p
p
位为零。转移要满足三个条件:一是要保证转移的新区间对应位为 0,二是要保证前面的状态为 true
,三要保证新区间的前
p−1
p
−
1
位为
1
1
的位在 ans 中不能为
0
0
,否则会让 ans 变大。换句话说,转移不能使
ans
a
n
s
变大。边界情况的答案类似。如果最后
fp,i,a∼b
f
p
,
i
,
a
∼
b
中存在 true
,则这一位可以为
0
0
,我们将 ans 进行更新;否则我们不对
ans
a
n
s
进行更新。
显然
p
p
是不用保存的,所以我们只需要保存 fi,j。算法的时间复杂度为
O(40n3)
O
(
40
n
3
)
,可以通过前面的所有测试点。
最后一个测试点
a=1
a
=
1
,显然这是一个 Special Instance,我们对其特殊考虑。发现,我们只需要求出满足某一位为
0
0
的最小段数就可以了,所以我们设 fp,i 表示在保证前
p−1
p
−
1
为
ans
a
n
s
的前
p−1
p
−
1
位的前提下,把前
i
i
个数分成若干段使得第 p 位为
0
0
的最小段数。转移条件与前面的类似,时间复杂度降为 O(40n2)。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
const int maxn = 2005;
int n, a, b, bitlen;
LL y[maxn];
#define RunInstance(x) delete new x
struct work1
{
static const int maxN = 105;
LL ans;
bool f[maxN][maxN];
work1() : ans()
{
for (int i = 0; i <= bitlen; i++)
ans |= LL(1) << i;
for (int i = bitlen; ~i; i--)
{
memset(f, 0, sizeof(f));
for (int j = 1; j <= n; j++)
{
f[j][1] = ((y[j] | ans) <= ans) && !(y[j] & (LL(1) << i));
for (int k = 2, to = std::min(j, b); k <= to; k++)
{
for (int s = k - 1; s < j; s++)
{
LL delta = y[j] - y[s];
if ((delta | ans) <= ans && !(delta & (LL(1) << i)))
f[j][k] |= f[s][k - 1];
}
}
}
bool bOk = false;
for (int j = a; j <= b; j++)
if (f[n][j])
{
bOk = true;
break;
}
if (bOk)
ans ^= LL(1) << i;
}
printOut(ans);
}
};
struct work2
{
LL ans;
int INF;
int f[maxn];
work2() : ans()
{
memset(&INF, 0x3f, sizeof(INF));
for (int i = 0; i <= bitlen; i++)
ans |= LL(1) << i;
for (int i = bitlen; ~i; i--)
{
memset(f, 0x3f, sizeof(f));
f[0] = 0;
if ((y[1] | ans) <= ans && !(y[1] & (LL(1) << i)))
f[1] = 1;
for (int j = 2; j <= n; j++)
for (int k = 0; k < j; k++)
{
LL delta = y[j] - y[k];
if ((delta | ans) <= ans && !(delta & (LL(1) << i)))
f[j] = std::min(f[j], f[k] + 1);
}
if (f[n] <= b)
ans ^= LL(1) << i;
}
printOut(ans);
}
};
void run()
{
n = readIn();
a = readIn();
b = readIn();
for (int i = 1; i <= n; i++)
y[i] = readIn();
for (int i = 2; i <= n; i++)
y[i] += y[i - 1];
bitlen = 63;
while (bitlen && !(y[n] & (LL(1) << bitlen)))
bitlen--;
if (a != 1)
RunInstance(work1);
else
RunInstance(work2);
}
int main()
{
run();
return 0;
}
总结
唉,我太弱了,调了一下午,终于过了。
这道题是按位贪心,利用 DP 确定答案。DP 的状态有些猎奇(千万不要忽视 DP 状态的定语),这种“在满足指定条件时才能转移”的方法应该是一种新思路吧。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)