2020-2021:teams:farmer_john:jjleo:codeforces_round_646_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_646_div._2 [2020/06/06 23:53] jjleo [D] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_646_div._2 [2020/06/25 23:34] (当前版本) jjleo ↷ 链接因页面移动而自动修正 |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| * 题意:交互题。给定一个长度为$n$的序列$a$和$k$个两两没有交集的非空下标集合，每个集合有一个权值，等于除了该集合中下标对应的序列$a$中的元素以外$a$中其它元素的最大值。给出这$k$个集合，你可以询问不超过$12$次，每次询问$a$中任意个指定元素的最大值。最后要给出$k$个集合对应的权值。$(2 \leq n \leq 1000, 1 \leq k \leq n)$ | * 题意:交互题。给定一个长度为$n$的序列$a$和$k$个两两没有交集的非空下标集合，每个集合有一个权值，等于除了该集合中下标对应的序列$a$中的元素以外$a$中其它元素的最大值。给出这$k$个集合，你可以询问不超过$12$次，每次询问$a$中任意个指定元素的最大值。最后要给出$k$个集合对应的权值。$(2 \leq n \leq 1000, 1 \leq k \leq n)$ | ||
| * 题解:可以发现只有一个集合包含了全局最大值的下标（如果有多个最大值，随意挑一个当作全局最大值），那么其它集合对应的权值就是这个全局最大值。我们只需要二分出这个全局最大值的下标，然后询问一下对应的集合的最大值。正好全局$(1)$+二分$(10)$+最后询问一次$(1)$正好$12$次。需要注意不保证所有下标都出现在集合中，因此有可能全局最大值对应的下标不属于任何一个集合，这个时候所有权值就都是这个全局最大值了。 | * 题解:可以发现只有一个集合包含了全局最大值的下标（如果有多个最大值，随意挑一个当作全局最大值），那么其它集合对应的权值就是这个全局最大值。我们只需要二分出这个全局最大值的下标，然后询问一下对应的集合的最大值。正好全局$(1)$+二分$(10)$+最后询问一次$(1)$正好$12$次。需要注意不保证所有下标都出现在集合中，因此有可能全局最大值对应的下标不属于任何一个集合，这个时候所有权值就都是这个全局最大值了。 | ||
| - | * 和这题很像 [[Educational Codeforces Round 87 (Rated for Div. 2) Virtual participation|G题]] | + | * 和这题很像 [[2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_87_rated_for_div._2_virtual_participation|G题]] |
| =====E===== | =====E===== | ||
2020-2021/teams/farmer_john/jjleo/codeforces_round_646_div._2.1591458805.txt.gz · 最后更改: 2020/06/06 23:53 由 jjleo
