Difference between revisions of "2017-2018 ACM-ICPC East Central North America Regional Contest (ECNA 2017)"
(Created page with "== Problem A == Solved by ultmaster. 04:33 (+) == Problem B == Solved by kblack. 03:18 (+1) == Problem C == Solved by zerol. 00:09 (+) == Problem D == Solved by kblack....") |
|||
(10 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
Solved by ultmaster. 04:33 (+) | Solved by ultmaster. 04:33 (+) | ||
+ | |||
+ | 题意:求多个简单多边形的并。 | ||
+ | |||
+ | 题解(伪):以多边形的点和多边形与多边形的交点作为关键 $x$ 点进行离散化。然后算出每一段区间内的关键 $y$ 点扫描线即可。 | ||
+ | |||
+ | 貌似可以随便卡掉?但是一下子就 AC 了啊? | ||
+ | |||
+ | ultmaster: 卡了。可能有点惨烈。而且答案并不能保证是对的(不过至少有三票啊?) | ||
+ | |||
+ | [[File:Screen Shot 2018-11-22 at 8.54.37 PM.png|800px]] | ||
+ | |||
+ | 本题 std 已死。 | ||
+ | |||
+ | Hack 数据已传至 EOJ 3657。 | ||
== Problem B == | == Problem B == | ||
Solved by kblack. 03:18 (+1) | Solved by kblack. 03:18 (+1) | ||
+ | |||
+ | 题意:给定 $N$ 个圆,求包围图形的最小周长。 | ||
+ | |||
+ | 题解:类似凸包的 $O(nh)$ 算法,每次寻找包围图形上下一个点,通过角度的变化计算弧线的长度,注意处理圆包含等情况。 | ||
== Problem C == | == Problem C == | ||
Solved by zerol. 00:09 (+) | Solved by zerol. 00:09 (+) | ||
+ | |||
+ | 温暖的签到。 | ||
== Problem D == | == Problem D == | ||
Solved by kblack. 00:21 (+) | Solved by kblack. 00:21 (+) | ||
+ | |||
+ | 温暖的签到。 | ||
== Problem E == | == Problem E == | ||
Solved by ultmaster. 01:09 (+3) | Solved by ultmaster. 01:09 (+3) | ||
+ | |||
+ | 题意:有一堆类的 is-a 和 has-a 关系,询问若干关系能否被推导出来。 | ||
+ | |||
+ | 题解:建边。is-a 是 0 类型边,has-a 是 1 类型边。询问 A is-a B 的时候,看 A 能否通过一系列 0 类型边到达 B;询问 A has-a B 是看 A 能否通过一系列 0 类型边和至少一条 1 类型边到达 B。暴力即可。 | ||
+ | |||
+ | 写错背锅。题意不清也有责任。 | ||
== Problem F == | == Problem F == | ||
Solved by kblack. 01:04 (+) | Solved by kblack. 01:04 (+) | ||
+ | |||
+ | 温暖的树形签到。 | ||
== Problem G == | == Problem G == | ||
Solved by kblack. 01:31 (+) | Solved by kblack. 01:31 (+) | ||
+ | |||
+ | 温暖的 DP 签到。 | ||
== Problem H == | == Problem H == | ||
Solved by zerol. 00:17 (+) | Solved by zerol. 00:17 (+) | ||
+ | |||
+ | 温暖的签到。 | ||
== Problem I == | == Problem I == | ||
Solved by ultmaster. 02:17 (+) | Solved by ultmaster. 02:17 (+) | ||
+ | |||
+ | 题意:4 个数凑 24 点。允许交换顺序(代价为 2),允许加括号(代价为 1),求最小代价。 | ||
+ | |||
+ | 题解:枚举排列,然后 DFS 表达式树的生成过程。出了点奇怪的问题,自闭了一会儿。 | ||
== Problem J == | == Problem J == | ||
Solved by zerol. 01:22 (+) | Solved by zerol. 01:22 (+) | ||
+ | |||
+ | 题意:给 10 个装置,每个装置都有人使用休息循环。问有个人装置一个个用过来使用休息循环共三轮,如果发现别人在用或刚开始用就要等待,反过来也要等待,问完成时间。 | ||
+ | |||
+ | 题解:模拟。 |
Latest revision as of 13:06, 22 November 2018
Problem A
Solved by ultmaster. 04:33 (+)
题意:求多个简单多边形的并。
题解(伪):以多边形的点和多边形与多边形的交点作为关键 $x$ 点进行离散化。然后算出每一段区间内的关键 $y$ 点扫描线即可。
貌似可以随便卡掉?但是一下子就 AC 了啊?
ultmaster: 卡了。可能有点惨烈。而且答案并不能保证是对的(不过至少有三票啊?)
本题 std 已死。
Hack 数据已传至 EOJ 3657。
Problem B
Solved by kblack. 03:18 (+1)
题意:给定 $N$ 个圆,求包围图形的最小周长。
题解:类似凸包的 $O(nh)$ 算法,每次寻找包围图形上下一个点,通过角度的变化计算弧线的长度,注意处理圆包含等情况。
Problem C
Solved by zerol. 00:09 (+)
温暖的签到。
Problem D
Solved by kblack. 00:21 (+)
温暖的签到。
Problem E
Solved by ultmaster. 01:09 (+3)
题意:有一堆类的 is-a 和 has-a 关系,询问若干关系能否被推导出来。
题解:建边。is-a 是 0 类型边,has-a 是 1 类型边。询问 A is-a B 的时候,看 A 能否通过一系列 0 类型边到达 B;询问 A has-a B 是看 A 能否通过一系列 0 类型边和至少一条 1 类型边到达 B。暴力即可。
写错背锅。题意不清也有责任。
Problem F
Solved by kblack. 01:04 (+)
温暖的树形签到。
Problem G
Solved by kblack. 01:31 (+)
温暖的 DP 签到。
Problem H
Solved by zerol. 00:17 (+)
温暖的签到。
Problem I
Solved by ultmaster. 02:17 (+)
题意:4 个数凑 24 点。允许交换顺序(代价为 2),允许加括号(代价为 1),求最小代价。
题解:枚举排列,然后 DFS 表达式树的生成过程。出了点奇怪的问题,自闭了一会儿。
Problem J
Solved by zerol. 01:22 (+)
题意:给 10 个装置,每个装置都有人使用休息循环。问有个人装置一个个用过来使用休息循环共三轮,如果发现别人在用或刚开始用就要等待,反过来也要等待,问完成时间。
题解:模拟。