2018-2019 XIX Open Cup, Grand Prix of Korea

ECNU F0RE1GNERS

ultmaster：依然是签到选手 U。

Problem A

Solved by zerol. 03:42 (+2)

题意：给一棵有根树，要求支持如下操作。将一个结点到根的路径染成颜色 c，询问有多少种颜色恰好染了 k 条边。

题解：LCT 裸题。每一条链的颜色都是一样的，可以批量修改。access 的时候维护一下每种颜色染过的边数即可。

zerol: 以为出灵异事件了，其实是自己 SB，把不改删的代码给删了，出现了未定义行为。

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by kblack. 01:00 (+)

题意：问一个电阻电路，能否选取起点终点使其为简单电路（只有串并联，没有桥什么的）。

题解：多校的原题，多校要求这个图的最大匹配方案数。我们用 set 存图，不断缩掉度数为 2 的点，并去除重边，最后能够得到 1 个单点与原问题等价。

Problem F

Solved by zerol. 01:13 (+)

题意：让你构建一棵好的且恰好有 n 个结点的树。只有叶子有权重。好的数满足左右子树都是好的树，且左右子树的权重相等或者左比右大 1。仅有叶子称为好的树。子树可以重用（就像函数式数据结构，左右子树可以指向同一棵子树）。

题解：啰嗦了一堆，当你发现只有叶子上有权重，而且左右要平衡，那么不就是线段树嘛。当然还需要证明一下不同形态的子树不会太多，如果左右子树大小分别是 x+1 和 x，那么下一层的子树大小就会形如 b, a, a, a，其中 b=a+1，于是最后需要的不同子树不超过 $2\log(n)$ 种。

Problem G

Solved by kblack. 04:48 (+2)

Upsolved by ultmaster.

ultmaster: 后半场一直在做这个题。结果还是依靠稳健的 kblack 才过了这题。

我的思路（经过反复的修改以后）是这样的：为了方便考虑先把路灯的位置放到最右边。f[i][j][k][x] 表示到 i 为止，i-x 已经完全被覆盖（也就意味着 i-x 上面一定放了路灯），已经捐了 j 盏路灯，已经免费用了 k 盏路灯的最小代价。那么答案就是 min(f[n][k][k][0], f[n+1][k][k][0], f[n+1][k][k][1]) 对于 $1 \le k \le K$。考虑转移：

• 对于 $x>0$，f[i][j][k][x] 可以从 f[i-1][j][k][x-1] 转移而来（表示当前位置不放路灯）；也可以从 f[i-1][j-1][k][x-1]+w[i] 转移而来（表示把当前位置的路灯捐掉）；
• 对于 $x=0$，f[i][j][k][0] 可以从 f[i][j][k][1], f[i][j][k][2], f[i][j][k][3] 转移而来（把路灯放在“当前位置不放路灯”的状态之上，同时允许把当前位置的路灯捐掉）；最后一种是路灯给自己用，注意，如果当前位置的路灯要立即使用的话，就不能把当前位置的路灯捐掉了（否则会偷税（zerol: 愉悦），我也没想清楚），所以是从 f[i-1][j][k][0], f[i-1][j][k][1], f[i-1][j][k][2] 转移而来。
• 把 w[1] 初始化成 $\infty$，f[0][x][x][x] 除了 f[0][0][0][x] 初始化成 $\infty$。

我从赛中搞到赛后，搞了起码三个小时才写对。这题过的人还特别多。。。

kblack: 把路灯放到右边的操作一样，建立状态 f[i][j][k] 表示照亮前 i 个，准备了 j 个小路灯，假装用了 k 个大路灯，且第 i 个位置的路灯是大路灯或直接用的路灯，然后枚举下一个路灯的位置，枚举中间的路灯当作小路灯，下一盏是大路灯还是小路灯进行转移，常数优化，好了。

Problem H

Solved by zerol. 00:35 (+)

题意：求有多少个分数，分子和分母分别在给定区间范围内，且约分后分子和分母之和小于 1000。

题解：枚举约分后的结果即可，不需要容斥。

Problem I

Solved by ultmaster. 00:40 (+1)

刚开始不会博弈，以为要 SG 函数。

好不容易会博弈了，发现根本不需要 SG 函数。

然后 WA 了，仔细一看题，发现还是需要 SG 函数。

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Solved by kblack. 00:24 (+)

温暖的调和级数签到。

Problem M

Unsolved.

_

Problem A

Solved by zerol. 03:42 (+2)

题意：给一棵有根树，要求支持如下操作。将一个结点到根的路径染成颜色 c，询问有多少种颜色恰好染了 k 条边。

题解：LCT 裸题。每一条链的颜色都是一样的，可以批量修改。access 的时候维护一下每种颜色染过的边数即可。

zerol: 以为出灵异事件了，其实是自己 SB，把不改删的代码给删了，出现了未定义行为。

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by kblack. 01:00 (+)

题意：问一个电阻电路，能否选取起点终点使其为简单电路（只有串并联，没有桥什么的）。

题解：多校的原题，多校要求这个图的最大匹配方案数。我们用 set 存图，不断缩掉度数为 2 的点，并去除重边，最后能够得到 1 个单点与原问题等价。

Problem F

Solved by zerol. 01:13 (+)

题意：让你构建一棵好的且恰好有 n 个结点的树。只有叶子有权重。好的数满足左右子树都是好的树，且左右子树的权重相等或者左比右大 1。仅有叶子称为好的树。子树可以重用（就像函数式数据结构，左右子树可以指向同一棵子树）。

题解：啰嗦了一堆，当你发现只有叶子上有权重，而且左右要平衡，那么不就是线段树嘛。当然还需要证明一下不同形态的子树不会太多，如果左右子树大小分别是 x+1 和 x，那么下一层的子树大小就会形如 b, a, a, a，其中 b=a+1，于是最后需要的不同子树不超过 $2\log(n)$ 种。

Problem G

Solved by kblack. 04:48 (+2)

Upsolved by ultmaster.

ultmaster: 后半场一直在做这个题。结果还是依靠稳健的 kblack 才过了这题。

我的思路（经过反复的修改以后）是这样的：为了方便考虑先把路灯的位置放到最右边。f[i][j][k][x] 表示到 i 为止，i-x 已经完全被覆盖（也就意味着 i-x 上面一定放了路灯），已经捐了 j 盏路灯，已经免费用了 k 盏路灯的最小代价。那么答案就是 min(f[n][k][k][0], f[n+1][k][k][0], f[n+1][k][k][1]) 对于 $1 \le k \le K$。考虑转移：

• 对于 $x>0$，f[i][j][k][x] 可以从 f[i-1][j][k][x-1] 转移而来（表示当前位置不放路灯）；也可以从 f[i-1][j-1][k][x-1]+w[i] 转移而来（表示把当前位置的路灯捐掉）；
• 对于 $x=0$，f[i][j][k][0] 可以从 f[i][j][k][1], f[i][j][k][2], f[i][j][k][3] 转移而来（把路灯放在“当前位置不放路灯”的状态之上，同时允许把当前位置的路灯捐掉）；最后一种是路灯给自己用，注意，如果当前位置的路灯要立即使用的话，就不能把当前位置的路灯捐掉了（否则会偷税（zerol: 愉悦），我也没想清楚），所以是从 f[i-1][j][k][0], f[i-1][j][k][1], f[i-1][j][k][2] 转移而来。
• 把 w[1] 初始化成 $\infty$，f[0][x][x][x] 除了 f[0][0][0][x] 初始化成 $\infty$。

我从赛中搞到赛后，搞了起码三个小时才写对。这题过的人还特别多。。。

kblack: 把路灯放到右边的操作一样，建立状态 f[i][j][k] 表示照亮前 i 个，准备了 j 个小路灯，假装用了 k 个大路灯，且第 i 个位置的路灯是大路灯或直接用的路灯，然后枚举下一个路灯的位置，枚举中间的路灯当作小路灯，下一盏是大路灯还是小路灯进行转移，常数优化，好了。

Problem H

Solved by zerol. 00:35 (+)

题意：求有多少个分数，分子和分母分别在给定区间范围内，且约分后分子和分母之和小于 1000。

题解：枚举约分后的结果即可，不需要容斥。

Problem I

Solved by ultmaster. 00:40 (+1)

刚开始不会博弈，以为要 SG 函数。

好不容易会博弈了，发现根本不需要 SG 函数。

然后 WA 了，仔细一看题，发现还是需要 SG 函数。

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Solved by kblack. 00:24 (+)

温暖的调和级数签到。