【训练记录】6.3 训练笔记

因为奇怪的问题,导致其实昨天第三场的 T3 写的复杂度并不对。于是今天就花了很多时间研究了一下正确的做法,导致只打了一场…(并且做完没睡好导致上午效率极低)。

不过有一说一,题目还是很赞的!感觉学到了很多。

A

给定两个长度分别为 $n,m$ 的串 $s,t$ 。求有多少个 $s$ 的本质不同的子串(起始位置不同)包含 $t$ 作为子序列。

$1\leq n\leq 10^5,1\leq m\leq 100$ 。

拿了一个比 std 更有技术含量的做法秒了这道题。大概是考虑可以先预处理出 $s$ 中有哪些极小的区间包含 $t$ 作为子序列,这部分可以用子序列自动机来实现。观察到 $m$ 比较小,就可以枚举每一个 $s_i=t_1$ 的位置 $i$ 开始在自动机上匹配直到结束。

这样最后一定是一堆区间。考虑如果一个区间被另一个区间完全包含,那么那个大区间就没用了,可以删掉。于是就可以对 vector 排个序用类似单调栈的方法做这个过程。之后考虑,对于相邻的两端区间 $[l_1,r_1],[l_2,r_2]$,$[l_2,r_2]$ 可以产生的部分贡献 $[l_1,r_1]$ 也产生了,不难发现这就是那些满足 $[l_2,r_2]\subset [l,r]$ 且 $l\leq l_1$ 的贡献,于是左端点就只取 $l_2-l_1$ 这些方案就好了。复杂度 $O(|\Sigma|\times n+nm)$ 。

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

ll ans ;
int n, m ;
char a[N] ;
char b[N] ;
int nxt[N][26] ;

vpint ant ;
vpint range ;

void build(char *s, int L){
for (int j = 0 ; j < 26 ; ++ j) nxt[L + 1][j] = L + 1 ;
for (int i = L ; i >= 1 ; -- i){
for (int j = 0 ; j < 26 ; ++ j)
nxt[i][j] = nxt[i + 1][j] ;
if (i < L)
nxt[i][s[i + 1] - 'a'] = i + 1 ;
}
}
void do_match(int p){
int q = 1, o = p ;
while (p < n + 1 && q < m)
++ q, p = nxt[p][b[q] - 'a'] ;
range.p_b(make_pair(o, p)) ;
}
bool comp(pint a, pint b){
return a.fr == b.fr ? a.sc > b.sc : a.fr < b.fr ;
}
bool r_include(pint a, pint b){
return a.fr <= b.fr && a.sc >= b.sc ;
}
int main(){
cin >> n >> m ;
scanf("%s", a + 1) ;
scanf("%s", b + 1) ; build(a, n) ;
for (int i = 1 ; i <= n ; ++ i)
if (a[i] == b[1]) do_match(i) ;
sort(range.begin(), range.end()) ;
for (int i = 0 ; i < range.size() ; ++ i){
for (int k = ant.size() - 1 ; ~k ; -- k)
if (r_include(ant[k], range[i])) ant.pop_back() ;
ant.push_back(range[i]) ;
}
int l = 0 ;
for (int i = 0 ; i < ant.size() ; ++ i)
ans += 1ll * (n - ant[i].sc + 1) * (ant[i].fr - l), l = ant[i].fr ;
cout << ans << '\n' ; return 0 ;
}

B

$1\leq m\leq 16$ 。

这题是真的神神神神神。然而自己打了暴力就跑了。

考虑找性质+分治。有这么几个找不出来的性质:

1、每个 $1\sim n$ 的数至少会在 $p_0\sim p_{2^m-1}$ 中出现一次。考虑对于某个 $a_i$ ,将其取反得到的 $rev(a_i)$一定也是 $[0,2^m-1]$ 之间的数,同时必然有 $a_i\operatorname{xor} rev(a_i)$ 最优,可以达到 $2^m-1$ 这个上界 。

2、考虑对 $p$ 按照二进制(当前)最高位是0/1进行分治。考虑分治到某个时刻的 $[l,r]$。考虑如果存在 $[l,mid]$ 和 $[mid+1,r]$ 的所有 $p_i$ 分别相同,那么说明当前这一位设成 $0$ 还是 $1$ 并没有什么什么影响,所以此时对答案会产生 $2$ 的贡献。并且由于左右区间相同,需要只分治一边。

3、如果不同,那么考虑如果 $[l,mid]$ 中的某个 $p_i$ 出现在了 $[mid+1,r]$ 里面,那么最后答案就是 $0$。原因是如果不满足当前最高位填 $0/1$ 都可以的话,就可以对这些数按照当前二进制位分组。而一个数字不可能存在二进制下某一位既是 $0$ 又是 $1$,所以无解。

4、否则分治到更小的二进制位去观察贡献。

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

ll ans ;
int n, m ;
int buc[N] ;
int base[N] ;

void solve(int l, int r){
//debug(l, ' '), debug(r) ;
if (l == r) return ;
int mid = (l + r) >> 1 ;
for (int i = l, j = mid + 1 ; i <= mid ; ++ i)
if (base[i] != base[j]) goto no_contribute ; else ++ j ;
(ans *= 2ll) %= P ; solve(l, mid) ; return ;
no_contribute : void() ;
for (int i = l ; i <= r ; ++ i) buc[base[i]] = 0 ;
for (int i = l ; i <= mid ; ++ i) buc[base[i]] ++ ;
for (int i = mid + 1 ; i <= r ; ++ i)
if (buc[base[i]]) puts("0"), exit(0) ;
solve(l, mid) ; solve(mid + 1, r) ;
}
int main(){
cin >> n >> m ; m = 1 << m ;
for (int i = 0 ; i < m ; ++ i)
buc[base[i] = qr()] += 1 ;
for (int i = 1 ; i <= n ; ++ i)
if (!buc[i]) goto fuck ;
ans = 1 ; solve(0, m - 1) ; /* */
cout << ans << '\n' ; return 0 ;
fuck : puts("0") ; return 0 ;
}

C

给定一个完全图。求该图的「最小 xq 生成树」的 xq。

定义一棵树的 xq为

其中具有最小的 xq 的那棵树被称为「最小 xq 生成树」。

$1\leq n\leq 15$ 。

比较有趣的 dp 吧…

自己一开始写了个特别弱智的错解。大概是对着每个点集跑一遍 Floyd,然后设 $f_s$ 表示集合 $s$ 中最小 xq 生成树的 xq 值。转移的时候枚举一个点进行转移。这样显而易见地就忽视了树的限制。于是考虑如何 dp 出一棵合理的树。

具体的,设 $f_{s,i}$ 表示以 $i$ 为根,树中的元素是集合 $s$ 的最小 xq 生成树的 xq 值。考虑怎么转移。转移的本质是枚举一个子问题,那么如果钦定了根是谁,就可以直接枚举怎么从根拆出一个子树来。更为具体的,有转移

也就是考虑删去的与根 $i$ 相连的某条边 $(i,j)$ 对总答案的贡献。那么就可以有一个 $O(3^n\times n^2)$ 的做法,可以通过 $n\le 13$ 。

之后考虑后面那部分好像很多余,因为后面那部分就本质上跟 $s\setminus t$ 无关了。具体的,对于每个集合 $s$ ,可以利用 $f_s$ 额外 dp 出一个 $g_{s,i}(i\notin s)$ 满足定义如下

于是转移就可以只拿 $g$ 转移了。复杂度 $O(3^n\times n+2^n\times n^2)$ 可以通过本题。

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
const int N = 15 ;

const int M = 100000 ;

int n, m ;

ll sz[M] ;
ll unsz[M] ;
ll A[N][N] ;

ll ans ;
ll g[M][N] ;
ll f[M][N] ;
//ll s[M][N] ;
//ll g[M][N][N] ;

void biout(int x){
while (x) cout << (x & 1), x >>= 1 ;
}

int main(){
cin >> n ;
m = (1 << n) - 1 ;
memset(g, 63, sizeof(g)) ;
memset(f, 63, sizeof(f)) ;
for (int i = 0 ; i < n ; ++ i)
f[1 << i][i] = g[1 << i][i] = 0 ;
for (int i = 0 ; i < n ; ++ i)
for (int j = i + 1 ; j < n ; ++ j)
A[i][j] = A[j][i] = qr() ; unsz[0] = n ;
for (int i = 1 ; i <= m ; ++ i)
sz[i] = sz[i ^ (i & (-i))] + 1, unsz[i] = n - sz[i] ;
// debug(sz, 1, m) ; debug(unsz, 1, m) ;
for (int s = 1 ; s <= m ; ++ s){
for (int t = s ; t ; t = (t - 1) & s)
for (int i = 0 ; i < n ; ++ i)
if (1 << i & t)
chkmin(f[s][i], f[t][i] + g[s ^ t][i]) ;
for (int i = 0 ; i < n ; ++ i){
if (1 << i & s) continue ;
for (int j = 0 ; j < n ; ++ j)
if (1 << j & s)
chkmin(g[s][i], f[s][j] + A[i][j] * sz[s] * unsz[s]) ;
}
}
ans = f[m][0] ;
// debug(f[m], 0, n) ;
for (int i = 1 ; i < n ; ++ i) chkmin(ans, f[m][i]) ;
cout << ans << '\n' ; return 0 ;
}

以下是 $65$ 分,注释起来的是翻车现场。

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
const int N = 15 ;

const int M = 100000 ;

int n, m ;
int sz[M] ;
int A[N][N] ;

ll ans ;
ll f[M][N] ;
//ll s[M][N] ;
//ll g[M][N][N] ;

void biout(int x){
while (x) cout << (x & 1), x >>= 1 ;
}

int main(){
cin >> n ;
memset(f, 63, sizeof(f)) ;
for (int i = 0 ; i < n ; ++ i)
f[1 << i][i] = 0 ; m = (1 << n) - 1 ;
for (int i = 0 ; i < n ; ++ i)
for (int j = i + 1 ; j < n ; ++ j)
A[i][j] = A[j][i] = qr() ;
for (int i = 1 ; i <= m ; ++ i)
sz[i] = sz[i ^ (i & (-i))] + 1 ;
for (int s = 1 ; s <= m ; ++ s)
for (int t = s ; t ; t = (t - 1) & s)
for (int i = 0 ; i < n ; ++ i)
if (1 << i & t)
for (int j = 0 ; j < n ; ++ j)
if (1 << j & (s ^ t))
chkmin(f[s][i], f[t][i] + f[s ^ t][j] + 1ll * A[i][j] * sz[s ^ t] * (n - sz[s ^ t])) ;
/*
for (int o = 0 ; o <= m ; ++ o){
int stk[20], cnt = 0 ;
for (int i = 0 ; i < n ; ++ i)
if (1 << i & o){
stk[++ cnt] = i ;
for (int j = 0 ; j < n ; ++ j)
if (1 << j & o)
g[o][i][j] = g[o][j][i] = A[i][j] ;
}
for (int k = 1 ; k <= cnt ; ++ k)
for (int i = 1 ; i <= cnt ; ++ i)
for (int j = 1 ; j <= cnt ; ++ j)
if ((i ^ j) && (j ^ k) && (i ^ k))
chkmin(g[o][stk[i]][stk[j]], g[o][stk[i]][stk[k]] + g[o][stk[k]][stk[j]]) ;
for (int i = 0 ; i < n ; ++ i)
if (1 << i & o)
for (int j = 0 ; j < n ; ++ j)
if (1 << j & o)
s[o][i] += g[o][i][j] ;
}
for (int i = 1 ; i <= m ; ++ i)
for (int j = 0 ; j < n ; ++ j){
if (!(1 << j & i)) continue ;
chkmin(f[i], f[i ^ (1 << j)] + s[i][j]) ;
}*/
/*
for (int i = 1 ; i <= m ; ++ i)
cout << i << " ", biout(i), cout << " " << f[i] << '\n' ;
*/
ans = f[m][0] ;
for (int i = 1 ; i < n ; ++ i) chkmin(ans, f[m][i]) ;
cout << ans << '\n' ; return 0 ;
}