XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Siberia

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 (+)

题意：给定两个数列 $\{a_i\}.\{b_i\}$，每次询问一个区间，可以对其中 $\frac{1}{3}$ 的位置取 $a_i$，另外 $\frac{1}{3}$ 的位置取 $b_i$，剩下 $\frac{1}{3}$ 的位置取 $\frac{a_i+b_i}{2}$，求每次能取的最大值。

题解：题目转换以后变成求一个长度为 $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 跑出两个串的所有匹配结果，比较两个串中匹配位置最前和最后的是否相交即可。