Difference between revisions of "XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Siberia"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 42: | Line 42: | ||
Solved by Xiejiadong && Kilo_5723. 3:50 (+) | Solved by Xiejiadong && Kilo_5723. 3:50 (+) | ||
+ | |||
+ | 题意: | ||
+ | |||
+ | 题解:题目转换以后变成求一个长度为 $3k$ 的区间中按照 $b_i-a_i$ 作为关键词,最大的 $k$ 个数和 + 次大的 $k$ 个数的和 * 0.5 + 所有 $a_i$ 的和。 | ||
+ | |||
+ | 利用主席树维护。需要多加一个区间和的信息。 | ||
+ | |||
+ | 线段树上二分,支持询问区间最大的 $k$ 个数的和即可。 | ||
== Problem I == | == Problem I == |
Revision as of 12:22, 26 May 2019
Problem A
Solved by Kilo_5723. 0:18 (+2)
Problem B
Unsolved.
Problem C
Unsolved.
Problem D
Solved by Weaver_zhu && Kilo_5723. 4:26 (+4)
Problem E
Solved by Xiejiadong. 2:20 (+2)
题意:给出一些直线的信息,直线本身是垂直于 $x$ 轴或者 $y$ 轴,两条直线之间是平行或者垂直。
题解:通过两两直线的关系连边可以得到一些独立的联通块。
对于每一个联通块,从本身有信息的点开始验证是否矛盾,并进行其他信息的填充。
如果一个联通块没有任何本身的信息,随便给其中一个点一个信息,判断是否冲突。
对于极大的删除量,每一个联通块只需要保留一个本身的信息和保证联通的树上边信息,其余全部删去。
对于原来整个联通块都没有本身信息的,不需要存在一个本身信息。
Problem F
Unsolved.
Problem G
Unsolved.
Problem H
Solved by Xiejiadong && Kilo_5723. 3:50 (+)
题意:
题解:题目转换以后变成求一个长度为 $3k$ 的区间中按照 $b_i-a_i$ 作为关键词,最大的 $k$ 个数和 + 次大的 $k$ 个数的和 * 0.5 + 所有 $a_i$ 的和。
利用主席树维护。需要多加一个区间和的信息。
线段树上二分,支持询问区间最大的 $k$ 个数的和即可。
Problem I
Solved by Kilo_5723. 1:33 (+3)
Problem J
Solved by Xiejiadong. 0:05 (+)
温暖的签到。
Problem K
Unsolved.
Problem L
Solved by Xiejiadong. 0:38 (+)
题意:询问是否存在对于两个模式串的匹配在母串中是不想交的。
题解:用 KMP 跑出两个串的所有匹配结果,比较两个串中匹配位置最前和最后的是否相交即可。