2017-2018 Southeastern European Regional Programming Contest (SEERC 2017)

From EOJ Wiki
Revision as of 05:39, 2 May 2018 by Kblack (talk | contribs) (→‎Problem K)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

由于选题人的失误这场没有配置题解,也没有相应的 wiki。可能要当第一个。(似乎本 wiki 根本没有被搜索引擎收录,凉凉。)

这场有一半的题是 kblack 做的。ultmaster 只做了一个签到题。之所以能贡献这一个签到题似乎是因为数据炸了。

Problem A

Solved by ultmaster. 02:22 (+2)

题意:求一个串有多少种方案成为另一个串的子序列。在每一个字母出现后,后 $b_h$ 个字母不能选。$b_h$ 是一个字母的函数。

题解:大概乱 DP 一下就好了。$dp(i,j)$ 表示第 $i$ 场必须在第 $j$ 天听有多少种方案。然后向后转移的时候要把可能可以转移的地方标记好,由于标记的是一段,所以要用差分。

Problem D

Solved by zerol. 02:53 (+)

题意:给一个每列有且只有 2 个 1 的 $\mathbb{ Z }_2$ 意义下的矩阵,求秩。

题解:看做无向图,答案就是行数与联通块个数之差。(简单证明:大小为 n 的联通块,显然秩不超过 n - 1,但秩不到 n - 1 的话就没法联通了。不同联通块的秩显然可以累加。)

Problem F

Solved by kblack. 02:38 (+)

题意:要求把一个 01 串变成另一个 01 串的最小代价。每个 bit 都有一个代价,翻转一位的代价定义为翻转后所有值为 1 的 bit 的代价和。

题解:肯定是先把一堆 1 变 0,代价大的先,然后再把 0 变 1,代价小的先,需要保留为 1 的 bit 可能会需要变成 0 一次,如果需要变,用代价大的一定更好,枚举从 1 变 0 再变 1 的个数。

Problem G

Solved by kblack. 01:50 (+3)

题意:一堆有加速度和加速时间的加速器,问过程结束后最大位移是多少。

题解:先用加速度大的肯定好,现场找了不一样的比较公式(化简后其实一样),代码疯狂写假,导致了巨大罚时。

Problem J

Solved by zerol. 04:37 (+2)

题意:Nim 游戏,但是后手可以操作两次。

题解:打表找规律。

zerol: 规律竟然还能看漏,背锅背锅。能打表的博弈先打表,肯定比手推来得稳。

Problem K

Solved by kblack. 01:23 (+)

题意:构造一个字典序最小的排列,使得排列的 LIS 序列为指定序列。

题解:从前往后贪心即可,根据 LIS 知道之后至少有几个比自己小的,数据结构维护。