Difference between revisions of "ICPC 2019 Nanchang Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
Line 16: Line 16:
  
 
Solved by Xiejiadong. 04:52 (+)
 
Solved by Xiejiadong. 04:52 (+)
 +
 +
题意:求删掉最小的字符,使得包含子串 $9102$ 而不包含子串 $8102$ 。
 +
 +
题解:倒过来处理比较方便处理末位的情况。
 +
 +
维护每一个区间内的转移。区间内的转移为 $f[i][j]$ ,表示状态 $i$ 到状态 $j$ 所需要删除的最少字符数量。
 +
 +
状态一共五个,分别是空和依次 $2$ 、 $20$ 、 $201$ 、 $2019$ 。
 +
 +
用线段树维护区间,每次合并区间的时候,可以发现是矩阵乘法。
 +
 +
线段树支持区间查询即可。
  
 
== Problem D ==
 
== Problem D ==

Revision as of 10:13, 8 September 2019

Problem A

Solved by Kilo_5723. 02:26 (+1)

Problem B

Solved by Xiejiadong. 01:06 (+)

题意:求一个点到其他点的最大距离 $/C$ 和好多个点到其他所有点最大距离比较。

题解:多源最短路,合并路径 max 即可。

注意不要去除 $C$ ,会发生各种问题,用多个点的距离乘 $C$ 即可。

Problem C

Solved by Xiejiadong. 04:52 (+)

题意:求删掉最小的字符,使得包含子串 $9102$ 而不包含子串 $8102$ 。

题解:倒过来处理比较方便处理末位的情况。

维护每一个区间内的转移。区间内的转移为 $f[i][j]$ ,表示状态 $i$ 到状态 $j$ 所需要删除的最少字符数量。

状态一共五个,分别是空和依次 $2$ 、 $20$ 、 $201$ 、 $2019$ 。

用线段树维护区间,每次合并区间的时候,可以发现是矩阵乘法。

线段树支持区间查询即可。

Problem D

Solved by Weaver_zhu. 04:25 (+2)

Problem E

Solved by Xiejiadong && Kilo_5723. 02:33 (+)

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 00:06 (+)

温暖的签到。

Problem H

Solved by Weaver_zhu. 01:34 (+)

Problem I

Unsolved.