2018-2019 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2018)

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Unsolved.

Problem B

Solved by oxx1108. 01:36:04(+)

Problem C

Solved by dreamcloud. 01:46:40(+)

Problem D

Unsolved.

Problem E

Solved by dreamcloud. 00:27:45(+)

Problem F

Solved by Xiejiadong. 02:47:35(+)

题意:每次修改可以把一整段变成整段的max或者min,求一个方案,在$\le 2n$的次数里,变成目标串。

题解:首先贪心配对,把下面一个串按照相同且连续的切成一段一段,与上面最前且不交叉的连线配对。

然后就是怎么找到修改方案。方案的修改不难想,把两边的置成max或者min,把中间的通过两次max和min变成全段即可。

从前往后修改,但是可能前面的修改会对后面的产生影响,这时候应该要先修改右边的,直接用递归来实现修改。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by oxx1108. 03:47:14(+)

题意:求一个图中有多少点集,满足两两之间的点都无边,且无法再加入更多的点使得集合满足上一个性质。图的构建是特殊的,先生成一个$n$的排列,然后就是逆序对之间连边。

题解:首先,图中要找的点集,就是反图里最大团的个数。

利用逆序对的性质,如果$a$向$b$有边、$b$向$c$有边、$c$向$d$有边,那么,$a$、$b$、$c$、$d$就是一个团。

这样的话,找最大团的个数,就变成了数最长链的个数。

试图在DAG上跑dp,要注意重边的影响,数据范围很小,暴力去掉它。

Problem J

Unsolved.

Problem K

Unsolved.