2018-2019 XIX Open Cup, Grand Prix of Korea

From EOJ Wiki
Jump to navigation Jump to search

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)$

Problem M