Difference between revisions of "2018 Multi-University Training Contest 10"
Jump to navigation
Jump to search
| (6 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
== Problem C == | == Problem C == | ||
| − | + | Unsolved. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Problem E == | == Problem E == | ||
| − | Solved | + | Solved. |
题意：对于树上的每个点，求 lca 恰好是这个点的点对中点权 gcd 的最大值。 | 题意：对于树上的每个点，求 lca 恰好是这个点的点对中点权 gcd 的最大值。 | ||
| Line 27: | Line 19: | ||
== Problem G == | == Problem G == | ||
| − | Solved by OEIS. | + | Solved by OEIS. |
== Problem H == | == Problem H == | ||
| − | Solved | + | Solved. |
| − | |||
| − | |||
| − | |||
| − | |||
== Problem I == | == Problem I == | ||
| − | Solved | + | Solved. |
| − | |||
| − | |||
| − | |||
| − | |||
== Problem J == | == Problem J == | ||
| − | Solved | + | Solved. |
题意：对于两个点集 S_1, S_2，求 $\max\{dist(x,y)+w_x+w_y | x\in S_1,y\in S_2\}$，距离为曼哈顿距离，最多五维。 | 题意：对于两个点集 S_1, S_2，求 $\max\{dist(x,y)+w_x+w_y | x\in S_1,y\in S_2\}$，距离为曼哈顿距离，最多五维。 | ||
| Line 57: | Line 41: | ||
== Problem L == | == Problem L == | ||
| − | Solved | + | Solved. |
题意：最多 $K$ 个人看电影，每个电影能拿钱，连续看相同类型的电影要罚钱，求最大获益。 | 题意：最多 $K$ 个人看电影，每个电影能拿钱，连续看相同类型的电影要罚钱，求最大获益。 | ||
题解：两排点表示在看那种电影，对于每个电影在两边对应时间连边，再连上发钱切换的边，费用流一下就好了。 | 题解：两排点表示在看那种电影，对于每个电影在两边对应时间连边，再连上发钱切换的边，费用流一下就好了。 | ||
Latest revision as of 07:15, 25 October 2018
Problem A
Unsolved.
Problem C
Unsolved.
Problem E
Solved.
题意：对于树上的每个点，求 lca 恰好是这个点的点对中点权 gcd 的最大值。
题解：对于树上每个点，求出一个 bitset 记录了子树中所有数的因数并，然后依次合并儿子以及自己本身，合并前取位与检查最高位的 1。（bitset._Find_first() 可以求出第一个 1 的位置。）
另解：线段树合并 / set 启发式合并。枚举 gcd 在更新在虚树上结点的答案（相邻两项 LCA）（由 CSL 友情提供）。
Problem G
Solved by OEIS.
Problem H
Solved.
Problem I
Solved.
Problem J
Solved.
题意：对于两个点集 S_1, S_2，求 $\max\{dist(x,y)+w_x+w_y | x\in S_1,y\in S_2\}$，距离为曼哈顿距离，最多五维。
题解：K-D Tree 暴力，要多加一些剪枝才能过。
正解：枚举每一维绝对值的正负，记录 $2^5$ 种可能的最大值，将另一个点集带入，取最大值即可。
Problem L
Solved.
题意：最多 $K$ 个人看电影，每个电影能拿钱，连续看相同类型的电影要罚钱，求最大获益。
题解：两排点表示在看那种电影，对于每个电影在两边对应时间连边，再连上发钱切换的边，费用流一下就好了。