Difference between revisions of "XX Open Cup named after E.V. Pankratiev. Grand Prix of Southeastern Europe"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "== Problem A == Unsolved. == Problem B == Upsolved by Kilo_5723. (-9) == Problem C == Unsolved. == Problem D == Solved by Kilo_5723. 01:38 (+6) == Problem E == Unsolv...") |
Xiejiadong (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 26: | Line 26: | ||
Solved by Xiejiadong. 02:41 (+1) | Solved by Xiejiadong. 02:41 (+1) | ||
+ | |||
+ | 题意:给出在 XoZ 和 YoZ 平面上的投影,求最多/最小的立方块数量。 | ||
+ | |||
+ | 题解:最多的立方块数量非常好处理,对于 XoYoZ 下的每一个方块,判断是否可以存在即可。 | ||
+ | |||
+ | 对于无解的判断,可以在上一部完成后,判断似乎存在某一个位置应该有投影的,但是没有方块即可。 | ||
+ | |||
+ | 对于最少需要的立方块数量,我们可以每层分开考虑,对于 X 和 Y 尽可能的配对,剩余的情况,因为需要保证字典序最小,分类讨论即可。 | ||
== Problem H == | == Problem H == | ||
Line 38: | Line 46: | ||
Solved by Xiejiadong. 01:56 (+) | Solved by Xiejiadong. 01:56 (+) | ||
+ | |||
+ | 题意:给一个完全图,可以讲图分割成好几个回路。回路经过的每一个点都有代价,代价是连接这个点的两条边中的较大值,现在可以安排回路使得回路代价的总和最小。 | ||
+ | |||
+ | 题解:可以发现对于每一个点,一定会有偶数次进出,一半的次数在进,一半的次数在出。 | ||
+ | |||
+ | 我们只需要决定了每一个节点的进出,因为是完全图,一定可以找到一种合法的回路。 | ||
+ | |||
+ | 于是问题就可以针对每一个点单独考虑。一进一出取最大值,最好的方案肯定是排序以后,从小到大两两组合。 | ||
+ | |||
+ | 于是针对每一个节点的权值排序计算即可。 | ||
== Problem K == | == Problem K == | ||
Unsolved. | Unsolved. |
Latest revision as of 06:28, 3 December 2019
Problem A
Unsolved.
Problem B
Upsolved by Kilo_5723. (-9)
Problem C
Unsolved.
Problem D
Solved by Kilo_5723. 01:38 (+6)
Problem E
Unsolved.
Problem F
Unsolved. (-3)
Problem G
Solved by Xiejiadong. 02:41 (+1)
题意:给出在 XoZ 和 YoZ 平面上的投影,求最多/最小的立方块数量。
题解:最多的立方块数量非常好处理,对于 XoYoZ 下的每一个方块,判断是否可以存在即可。
对于无解的判断,可以在上一部完成后,判断似乎存在某一个位置应该有投影的,但是没有方块即可。
对于最少需要的立方块数量,我们可以每层分开考虑,对于 X 和 Y 尽可能的配对,剩余的情况,因为需要保证字典序最小,分类讨论即可。
Problem H
Unsolved.
Problem I
Solved by Kilo_5723. 00:32 (+2)
Problem J
Solved by Xiejiadong. 01:56 (+)
题意:给一个完全图,可以讲图分割成好几个回路。回路经过的每一个点都有代价,代价是连接这个点的两条边中的较大值,现在可以安排回路使得回路代价的总和最小。
题解:可以发现对于每一个点,一定会有偶数次进出,一半的次数在进,一半的次数在出。
我们只需要决定了每一个节点的进出,因为是完全图,一定可以找到一种合法的回路。
于是问题就可以针对每一个点单独考虑。一进一出取最大值,最好的方案肯定是排序以后,从小到大两两组合。
于是针对每一个节点的权值排序计算即可。
Problem K
Unsolved.