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

Problem A

Solved by Kilo_5723. 0:18 (+2)

题意：给定两个矩阵，求两者间位置关系。

题解：判断 in 和 seperate 的情况，都没判到就是 intersect。

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 && Weaver_zhu. 1:33 (+3)

题意：给定 $q,n$，求 $q^n-1$ 在所有 $q_i-1(0 \le i<n)$ 中没出现过的 $\le 10^7$ 的素因子。

题解：可以证明 $\frac{q^x-1}{q-1}|\frac{q^y-1}{q-1} (x|y)$，以及 $gcd(\frac{q^x-1}{q-1},\frac{q^y-1}{q-1})=1 (gcd(x,y)=1)$。也就是说只有 $q^x-1 (x|n)$ 才会和 $q^n-1$ 有除 $q-1$ 的重复素因子。又因为第一个性质，我们只要对 $x=\frac{n}{p_i}$ 进行检测就能保证枚举到了所有可能重复的素因子（其中 $p_i$ 是 $n$ 的每一个素因子）。这样的 $p_i$ 的数量是小于 $10$ 的，直接对 $10^7$ 以内的每一个素数进行检测即可。

Problem J

Solved by Xiejiadong. 0:05 (+)

温暖的签到。

Problem K

Unsolved.

Problem L

Solved by Xiejiadong. 0:38 (+)

题意：询问是否存在对于两个模式串的匹配在母串中是不想交的。

题解：用 KMP 跑出两个串的所有匹配结果，比较两个串中匹配位置最前和最后的是否相交即可。