Difference between revisions of "2018-2019 XIX Open Cup, Grand Prix of Korea"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| (12 intermediate revisions by the same user not shown) | |||
| Line 117: | Line 117: | ||
Solved by Kilo_5723 && Xiejiadong. 02:48(+) | 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 == | == Problem H == | ||
| − | Solved by | + | Solved by Xiejiadong. 00:42(+) |
| − | + | 题意：求范围内满足要求的分数。 | |
| − | + | 题解：最简分数分子分母都在范围$1000$内，暴力枚举最简分数，直接就算出来了。 | |
== Problem I == | == Problem I == | ||
| − | Solved by | + | 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 == | == Problem J == | ||
| Line 171: | Line 169: | ||
== Problem L == | == Problem L == | ||
| − | Solved by | + | Solved by Weaver_zhu. 01:11(+) |
| + | |||
| + | 题意：求把数列分成尽量多的单调递增或严格递减的部分（取决于哪个会使子区间的长度更大），规定小数列的最小长度，求子数列的数量和违反单调性的数目 | ||
| − | + | 题解：并查集搞出最右递增和严格递减的界限，然后直接暴力跑出，复杂度是调和级数求和$O(nlogn)$ | |
== Problem M == | == Problem M == | ||
Latest revision as of 13:30, 3 April 2019
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)$