2019-team11/0004

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 2019.05.30 2016 Multi-University Training Contest 4 总结 By 1em0n Team ===

=== Part 1 流水账 ===

=== Part 2 队员总结 ===

=== 孔畅 ===

=== 夏天鑫 ===

=== 黄彦玮 ===



=== 补题 ===
|| Contest Name                                                                                            || A || B || C || D || E || F || G || H || I || J || K || L || M ||
|| 2016 Multi-University Training Contest 4                          || O || . || . || . || O || Ø || . || . || Ø || O || O || O || X ||
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的

=== 题解 ===
F：给定字符c和一个串，问有多少个本质不同的子串含c。————后缀数组，答案为/sum (i=0 to len-1) len-max(nxt[sa[i]],height[i]+sa[i])，其中nxt[i]是i位置之后离i最近的c的位置，画个图还是很好理解的。

I：题意太长，做法是根据w矩阵在i,j之间连边，原串中n个点每个点的权值为-a[s[i]]，每个字符建一个点权为a[i]-b[i]的点，转化成最大权闭合子图，跑一个网络流。

2019.05.30 2016 Multi-University Training Contest 4 总结 By 1em0n Team

Part 1 流水账

Part 2 队员总结

孔畅

夏天鑫

黄彦玮

补题

Contest Name

A

B

C

D

E

F

G

H

I

J

K

L

M

2016 Multi-University Training Contest 4

O

.

.

.

O

Ø

.

.

Ø

O

O

O

X

O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的

题解

F：给定字符c和一个串，问有多少个本质不同的子串含c。————后缀数组，答案为/sum (i=0 to len-1) len-max(nxt[sa[i]],height[i]+sa[i])，其中nxt[i]是i位置之后离i最近的c的位置，画个图还是很好理解的。

I：题意太长，做法是根据w矩阵在i,j之间连边，原串中n个点每个点的权值为-a[s[i]]，每个字符建一个点权为a[i]-b[i]的点，转化成最大权闭合子图，跑一个网络流。