Difference between revisions of "Moscow Pre-Finals Workshop 2016. Japanese School OI Team Selection."
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "== Problem A == Solvde by Kilo_5723. 0:43 (+) == Problem B == Unsolved. == Problem C == Solved by Xiejiadong. 1:29 (+1) == Problem D == Solved by Weaver_zhu. 3:55 (+2)...") |
Xiejiadong (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 10: | Line 10: | ||
Solved by Xiejiadong. 1:29 (+1) | Solved by Xiejiadong. 1:29 (+1) | ||
+ | |||
+ | 题意:要求支持两个操作: | ||
+ | |||
+ | * 查询所有高度 $\ge x$ 的连续的有几段; | ||
+ | * 修改某一个高度。 | ||
+ | |||
+ | 题解:考虑修改一个高度的时候,根据旁边两个的高度分情况讨论可能出现的联通块改变。 | ||
+ | |||
+ | 用树状数组维护所有高度 $\ge x$ 的联通块数量。 | ||
== Problem D == | == Problem D == | ||
Line 30: | Line 39: | ||
Solved by Xiejiadong. 2:06 (+1) | Solved by Xiejiadong. 2:06 (+1) | ||
+ | |||
+ | 题意:每次选择一个方向走到底(直到遇到冰块),每次出发的位置会变成冰块,求从起点到终点至少走多少路。 | ||
+ | |||
+ | 题解:考虑有两种走法: | ||
+ | |||
+ | * 从当前位置开始,选择一个方向走到底,代价为 $1$ ; | ||
+ | |||
+ | * 从当前位置走到相邻位置,代价为 $2$ (选择一个方向走到底再回来)。 | ||
+ | |||
+ | 建图以后跑最短路即可。 | ||
== Problem I == | == Problem I == | ||
Solved by Weaver_zhu. 2:48 (+2) | Solved by Weaver_zhu. 2:48 (+2) |
Latest revision as of 09:18, 15 March 2020
Problem A
Solvde by Kilo_5723. 0:43 (+)
Problem B
Unsolved.
Problem C
Solved by Xiejiadong. 1:29 (+1)
题意:要求支持两个操作:
- 查询所有高度 $\ge x$ 的连续的有几段;
- 修改某一个高度。
题解:考虑修改一个高度的时候,根据旁边两个的高度分情况讨论可能出现的联通块改变。
用树状数组维护所有高度 $\ge x$ 的联通块数量。
Problem D
Solved by Weaver_zhu. 3:55 (+2)
Problem E
Solved by Weaver_zhu. 2:38 (+)
Problem F
Unsolved.
Problem G
Solved by Weaver_zhu. 1:18 (+)
Problem H
Solved by Xiejiadong. 2:06 (+1)
题意:每次选择一个方向走到底(直到遇到冰块),每次出发的位置会变成冰块,求从起点到终点至少走多少路。
题解:考虑有两种走法:
- 从当前位置开始,选择一个方向走到底,代价为 $1$ ;
- 从当前位置走到相邻位置,代价为 $2$ (选择一个方向走到底再回来)。
建图以后跑最短路即可。
Problem I
Solved by Weaver_zhu. 2:48 (+2)