CF1450G. Communism（状压DP）
题面
有一个字符串
s
\tt s
s 和一个有理数
k
\tt k
k，可以进行如下操作任意次：
选一个当前串中存在的字符
x
\tt x
x ，令
i
1
,
i
2
,
.
.
.
,
i
m
\tt i_1,i_2,…,i_m
i1,i2,…,im 为字符
x
\tt x
x 存在的
m
\tt m
m 个位置。如果满足
k
⋅
(
i
m
−
i
1
+
1
)
≤
m
\tt k\cdot(i_m-i_1+1)\leq m
k⋅(im−i1+1)≤m ，那么可以再选一种不同的当前串中存在的字符
y
\tt y
y ，把所有字符
x
\tt x
x 变成字符
y
\tt y
y 。
不论进行多少次操作，最终要求整个字符串只存在一种字符
z
\tt z
z 。求所有可能的
z
\tt z
z 。
Input
第一行三个整数
n
,
a
,
b
\tt n,a,b
n,a,b ，其中
a
b
=
k
\tt \frac{a}{b}=k
ba=k 。
第二行一个长为
n
\tt n
n 的由小写字母组成的字符串
s
\tt s
s ，串中不包含 ‘t’,‘r’,‘y’,‘g’,‘u’,‘b’ 六种字符 。
范围
1
≤
n
≤
5
000
,
1
≤
a
≤
b
≤
100
000
\tt 1\leq n\leq 5\,000,1\leq a\leq b\leq100\,000
1≤n≤5000,1≤a≤b≤100000
1500
m
s
,
32
m
b
\tt 1500\,ms,32\,mb
1500ms,32mb .
题解
经历了前面几道黑题的洗礼，一看到这题的样例及解释，就有种不会做的感觉。
我们细读一遍题，慢慢理一下思路。
首先，在
26
\tt26
26 种字母之中，排除了
6
\tt6
6 种，剩下了
20
\tt20
20 种，刚好是可以做状压的数据范围。
会不会这么巧呢？我们不妨试试。
不难发现，一种字符只能操作一次。
既然最终只有一种字符
z
\tt z
z，那么上一步，就是把另一种字符的所有位置进行操作，而这些位置原本是除了
z
\tt z
z 以外的其它字符位置的并集。倒推回去，中间状态就是把一个字符集
S
\tt S
S 进行操作，此时字符集
S
\tt S
S 中所有字符的所有原先位置上，都有着相同的字符（该字符是什么不重要）。
不妨设
l
e
n
g
t
h
S
\tt length_S
lengthS 为字符集
S
\tt S
S 最右边的位置 - 最左边的位置 + 1，
c
n
t
S
\tt cnt_S
cntS 为
S
\tt S
S 占据的位置数量。
那么我们定义一个
D
P
\tt DP
DP ，
d
p
[
i
]
\tt dp[i]
dp[i](bool) 表示字符集
i
\tt i
i 是/否能被操作，那么有如下性质：
d
p
[
0
]
=
1
\tt dp[0]=1
dp[0]=1 。
当
i
=
{
x
}
\tt i=\{x\}
i={x} 时，如果字符
x
\tt x
x 一开始就能被操作，也就是说
k
⋅
l
e
n
g
t
h
x
≤
c
n
t
x
\tt k\cdot length_x\leq cnt_x
k⋅lengthx≤cntx ，那么
d
p
[
i
]
=
1
\tt dp[i]=1
dp[i]=1，这可以当作一种边界情况处理。
对于一种字符
x
\tt x
x ，一开始的
x
\tt x
x 是不能被操作的，但是能够让集合
i
−
x
\tt i-x
i−x 的字符被操作、变成字符
x
\tt x
x，然后整体又能被操作了，那么
d
p
[
i
]
=
1
\tt dp[i]=1
dp[i]=1。也就是说，如果存在
x
∈
i
\tt x\in i
x∈i ，满足
d
p
[
i
−
x
]
=
1
,
k
⋅
l
e
n
g
t
h
i
−
x
≤
c
n
t
i
−
x
\tt dp[i-x]=1,k\cdot length_{i-x}\leq cnt_{i-x}
dp[i−x]=1,k⋅lengthi−x≤cnti−x 且
k
⋅
l
e
n
g
t
h
i
≤
c
n
t
i
\tt k\cdot length_{i}\leq cnt_{i}
k⋅lengthi≤cnti ，那么
d
p
[
i
]
=
1
\tt dp[i]=1
dp[i]=1 。
当
i
=
S
1
∪
S
2
\tt i=S_1\cup S_2
i=S1∪S2，且
S
1
∩
S
2
=
∅
,
d
p
[
S
1
]
=
1
,
d
p
[
S
2
]
=
1
\tt S_1\cap S_2=\empty,dp[S_1]=1,dp[S_2]=1
S1∩S2=∅,dp[S1]=1,dp[S2]=1 时，即两个不相交的字符集分别能被操作。相当于它们的并集也能被操作了，于是
d
p
[
i
]
=
1
\tt dp[i]=1
dp[i]=1 。
某个字符
z
\tt z
z 能成为最终字符，就意味着
d
p
[
U
−
z
]
=
1
\tt dp[U-z]=1
dp[U−z]=1 ，在最后一步，除了
z
\tt z
z 以外的字符能全部变成
z
\tt z
z。
此时的复杂度是
Θ
(
3
∣
C
∣
)
\tt \Theta(3^{|C|})
Θ(3∣C∣) 级别的，达不到需求。瓶颈就在第四条性质，也就是第二条转移上。
我们可以找个性质优化一下。我们发现对于第二种转移，找
i
\tt i
i 的子集
S
1
\tt S_1
S1，
S
2
\tt S_2
S2 ，如果字符集
S
1
\tt S_1
S1 的右端点小于
S
2
\tt S_2
S2 的左端点，或
S
1
\tt S_1
S1 的左端点大于
S
2
\tt S_2
S2 的右端点，这样的转移才需要考虑。否则的话，可以把
S
1
\tt S_1
S1 进行操作，变成
S
2
\tt S_2
S2 的一些字符，最终把
S
2
\tt S_2
S2 “吞”掉，表现为第一种转移。
原因在于，一个字符集能被操作的本质是，在它的最小被覆盖区间内，它自己的浓度大于等于
k
\tt k
k 。如果两种字符集分别能被操作，且彼此有交的话，一个吞掉另一个后，浓度只会增大。浓度增大后，就更能被操作了，这个不难理解。
因此，我们把每种字符按照最左位置排序，选
i
\tt i
i 的子集时，就只选前缀，这样就把复杂度降成了
Θ
(
∣
C
∣
2
∣
C
∣
)
\tt \Theta(|C|2^{|C|})
Θ(∣C∣2∣C∣) 。
CODE
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 5005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
char ss[MAXN];
int a[MAXN];
char denote[30];
int pos[257];
short ll[1<<20|5],rr[1<<20|5],cnt[1<<20|5];
bool dp[1<<20|5];
int b[30];
bool cmp(int a,int b) {
return ll[1<<a] < ll[1<<b];
}
int main() {
n = read();
LL ka = read(),kb = read();
int tool_0_cnt = -1;
for(char i = 'a';i <= 'z';i ++) {
if(i != 't' && i != 'r' && i != 'y' && i != 'g' && i != 'u' && i != 'b') {
pos[i] = ++ tool_0_cnt;
denote[tool_0_cnt] = i;
b[tool_0_cnt] = tool_0_cnt;
}
}
for(int i = 0;i < 20;i ++) ll[1<<i] = n+1;
scanf("%s",ss + 1);
for(int i = 1;i <= n;i ++) a[i] = pos[ss[i]];
int ALL = 0;
for(int i = 1;i <= n;i ++) {
ll[1<<a[i]] = min(ll[1<<a[i]],(short)i);
rr[1<<a[i]] = i; cnt[1<<a[i]] ++;
ALL |= (1<<a[i]);
}
sort(b,b + 20,cmp);
int tp = 1<<20;
for(int i = 1;i < tp;i ++) {
if(i-lowbit(i)) {
ll[i] = min(ll[i-lowbit(i)],ll[lowbit(i)]);
rr[i] = max(rr[i-lowbit(i)],rr[lowbit(i)]);
cnt[i] = cnt[i-lowbit(i)] + cnt[lowbit(i)];
}
}
dp[0] = 1;
for(int i = 1;i < tp;i ++) {
if((rr[i]-ll[i]+1) * ka <= cnt[i] * kb && (i&ALL) == i) {
if(i == lowbit(i)) {
dp[i] = 1;
}
else {
for(int j = 0;j < 20;j ++) {
if(i & (1<<j)) dp[i] |= dp[i^(1<<j)];
}
}
}
if((i&ALL) == i) {
if(i ^ lowbit(i)) {
int S = 0;
for(int j = 0;j < 20;j ++) {
S = (S|(1<<b[j])) & i;
if(S != i && S) dp[i] |= dp[i^S] & dp[S];
}
}
}
}
int as = 0;
for(int i = 0;i < 20;i ++) if(dp[ALL^(1<<i)]) as ++;
printf("%d",as);
for(int i = 0;i < 20;i ++) if(dp[ALL^(1<<i)]) printf(" %c",denote[i]);
ENDL;
return 0;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章