Educational Codeforces Round 38 (Rated for Div. 2)
F. Erasing Substrings
- 最后剩下的答案长度是固定的
- 遍历答案的前缀 i,令 f[i][u] 代表 i 之前做的删除操作集合为 u 时能否达到最小前缀
- 递推时,f[i+1][u] 由所有合法的 f[i][v](v是u的子集)递推而来,这部分可以采用 sos dp
- 比较所有合法的 f[i+1][u] 得到的第 i+1 个字符,取最小的 c 即为答案的第 i+1 个字符,然后更新 f,能得到 c 的 f[i+1][u] 才为合法
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
|
import sys
from itertools import *
from collections import *
from heapq import *
from bisect import *
input = lambda: sys.stdin.readline().rstrip()
def II(base=10): return int(input(),base)
def LII(): return list(map(int,input().split()))
def LSII(): return [int(x)-1 for x in input().split()]
fmin = lambda x,y: x if x<y else y
fmax = lambda x,y: x if x>y else y
s = [ord(c)-ord('a') for c in input()]
n = len(s)
k = n.bit_length()-1
N = 1<<k
res = []
f = [1]*N
for i in range(n-N+1):
for u in range(N):
for j in range(k):
if u>>j&1:
f[u] |= f[u^1<<j]
mi = min(s[i+u] for u in range(N) if f[u])
res.append(mi)
f = [f[u] and s[i+u]==mi for u in range(N)]
print(''.join(chr(a+ord('a')) for a in res))
|
750 ms