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

由于选题人的失误这场没有配置题解，也没有相应的 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 知道之后至少有几个比自己小的，数据结构维护。