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

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

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

题意：判断一张图是否是简单电路，简单电路的定义是仅包含串并联。

题解：如果一个点的度数为 $2$ ，那么这个节点一定是一条边用作入边，另一条边用作出边。

于是我们可以一次把所有度数为 $2$ 的点全部缩掉。

可以发现，缩掉所有度数为 $2$ 的点可以把并联的一条链变成开头和结尾两个点；

继续缩度数为 $2$ 的点，可以把所有的并联变成两个点和一条边组成的点对。

于是最后能缩为点对的是 yes ，否则是 no 。

Problem F

Solved by Kilo_5723. 01:37(+)

题意：找到一个构造方案，初始状态什么都没有，每次可以用现有的两棵叶节点数量差至多为 $1$ 的二叉树树加一个根合并出一棵新二叉树，或用两个空节点合并出一个只有根的二叉树。树可以重复利用，要构造一颗含有 $n$ 个节点的二叉树，至多合并 $k$ 次。

题解：看似是构造，实则是拆解。要构造每一个树，显然，两棵子树的节点数量都是确定的，因此这个问题本质上只有唯一解，只要重复构造出相同叶节点数量的树就可以了。

因此，对于 $n$ 反复拆解去重来确定一共需要哪些节点数量的树，再按节点数量从小到大合并出来即可。

Problem G

Unsolved.

Problem H

Solved by Xiejiadong. 00:42(+)

题意：求范围内满足要求的分数。

题解：最简分数分子分母都在范围$1000$内，暴力枚举最简分数，直接就算出来了。

Problem I

Solved by Weaver_zhu && Kilo_5723. 01:56(+2)

题意：一个n个点凸多边形，两人轮流每次连两个点形成一条线（不得和前面的线相交），先连不了的人输，会使得另一个人一定先连出凸包，因为剩下的边一定是偶数。给定n求先手是否能胜

题解：连对角线会形成两个子游戏，连相邻的点会使，所以可以用sg函数搞。sg(0)=sg(1)=0, 表示先手必输，sg(2)=1，剩下的就是$O(n^2)$枚举连线方案，预处理答案了。

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Solved by Weaver_zhu. 01:11(+)

题意：求把数列分成尽量多的单调递增或严格递减的部分（取决于哪个会使子区间的长度更大），规定小数列的最小长度，求子数列的数量和违反单调性的数目

题解：并查集搞出最右递增和严格递减的界限，然后直接暴力跑出，复杂度是调和级数求和$O(nlogn)$