Difference between revisions of "2019-2020 ICPC, Asia Jakarta Regional Contest"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 46: | Line 46: | ||
Solved by Xiejiadong. 00:34 (+) | Solved by Xiejiadong. 00:34 (+) | ||
+ | |||
+ | 题意:要在一个建筑群中放下两个一摸一样的矩形,求矩形的最大面积。 | ||
+ | |||
+ | 题解:分类讨论: | ||
+ | |||
+ | * 在同一个矩形中放入两个,显然面积就是同一个 $/2$ ; | ||
+ | |||
+ | * 在不同的矩形中放入,考虑把对矩阵的长排序,枚举每一个矩阵的宽作为矩阵宽的情况,用一个 set 维护一下就好了。 | ||
== Problem I == | == Problem I == | ||
Line 54: | Line 62: | ||
Solved by Xiejiadong. 04:49 (+7) | Solved by Xiejiadong. 04:49 (+7) | ||
+ | |||
+ | 题意:将一个 $1 \times n$ 的布满 `.` 或者 `#` 的格子用三种方式来填充,每一种方式的填充都能获得相应的单位价值,第一种填充有数量限制。 | ||
+ | |||
+ | 题解:先不考虑第一种填充方式,可以发现,因为最多有 $50$ 个 `#` ,所以第三种填充最多不会超过 $50$ 个。 | ||
+ | |||
+ | 于是考虑先用 dp 处理出只考虑第二种和第三种填充的时候能获得的最大价值。 | ||
+ | |||
+ | 然后对于每一个状态,首先可以在空余的 `.` 位置中填入第一种,然后考虑用第一种方式去替换前两种方式,直接贪心即可。需要关注一些边界情况。 | ||
== Problem K == | == Problem K == |
Latest revision as of 12:12, 6 November 2019
Problem A
Solved by Xiejiadong. 00:06 (+)
温暖的签到。
直接输出 $n+1-a_i$ 即可。
Problem B
Solved by Kilo_5723. 04:17 (+2)
Problem C
Solved by Weaver_zhu. 00:25 (+)
Problem D
Unsolved.
Problem E
Unsolved. (-8)
Problem F
Unsolved.
Problem G
Solved by Xiejiadong. 02:33 (+1)
题意:每个阶段都会淘汰排名最低的几位,每个人的表现都是固定的,每个阶段在淘汰以后会有新的人加入,每次修改一次淘汰时候新加入的人的表现,判断第一个人是否会在某个时刻被淘汰。
题解:分析一下就不难发现,如果在某一时刻发生了修改,这个修改的值,只和第一个人的相对大小相关。
再具体分析一下,可以发现,如果一个本来表现比第一个人差的人被换成表现比他好的人,那个这个人从当前淘汰开始,之后的每一次排名顺位 ++ 。
于是,我们可以考虑维护这个人的排名,初始的时候,就是最开始在所有人中的排名,然后对于每一次加入的表现比他好的人,他在之后顺位 ++ ,相当于做一次区间 $+1$ 。
同理,之后的修改,本来表现比他好的人变差了,也可以通过区间 $-1$ 维护。
如果让每一个位置,初始的时候减去在当前轮会被淘汰的人数,只需要判断所有位置是否存在 $\le 0$ 的数就能判断这个人是否被淘汰了。
Problem H
Solved by Xiejiadong. 00:34 (+)
题意:要在一个建筑群中放下两个一摸一样的矩形,求矩形的最大面积。
题解:分类讨论:
- 在同一个矩形中放入两个,显然面积就是同一个 $/2$ ;
- 在不同的矩形中放入,考虑把对矩阵的长排序,枚举每一个矩阵的宽作为矩阵宽的情况,用一个 set 维护一下就好了。
Problem I
Unsolved.
Problem J
Solved by Xiejiadong. 04:49 (+7)
题意:将一个 $1 \times n$ 的布满 `.` 或者 `#` 的格子用三种方式来填充,每一种方式的填充都能获得相应的单位价值,第一种填充有数量限制。
题解:先不考虑第一种填充方式,可以发现,因为最多有 $50$ 个 `#` ,所以第三种填充最多不会超过 $50$ 个。
于是考虑先用 dp 处理出只考虑第二种和第三种填充的时候能获得的最大价值。
然后对于每一个状态,首先可以在空余的 `.` 位置中填入第一种,然后考虑用第一种方式去替换前两种方式,直接贪心即可。需要关注一些边界情况。
Problem K
Solved by Kilo_5723. 01:43 (+2)
Problem L
Unsolved.