XX Open Cup named after E.V. Pankratiev. Grand Prix of Siberia, Division 1.

Problem A

Solved by Kilo_5723. 0:09 (+)

题意：给定一个 $1/2$ 的矩阵，重新上色尽可能少的格子使得任意两点之间都有一条 $1,2$ 相间的路径。

题解：根据路径长度的奇偶性质，两点之间的曼哈顿距离如果是奇数则颜色不同，否则颜色相同，也就是说最终矩阵会像棋盘一样染色。两种染色方法取改动较少的。

Problem B

Upsolved by Weaver_zhu.

题意：给出一个nxm 迷宫 x 不能走 . 能走 ? 待定，求一种方案填满问号之后能走的格子最多。且满足每个能走的格子有且仅有一条路径走到最后一行或一列。同时走路径只能向下或向右走

题解：插头dp，记录状态并不需要 $nm2^{m}$，因为只需要记录行和行之间的 bitmask 转移就行了，加上滚动数组就不会mle了

Problem C

Unsolved.

Problem D

Solved by Weaver_zhu. 4:32 (+7)

题意：O(log) 求整系数一元三次方程的整数解

题解：卡精度的毒瘤题，先求导求零点求出单调区间，然后二分出一个整数解，然后再因式分解出二次方程再求另两个。坑点是所有操作都得用Int128，二分单调的时候要缩小范围+特判极值点才能保证整数的二分是正确的，并且试出来的解要是整数才行

Problem E

Solved by Xiejiadong. 0:07 (+)

题意：可以将数列的每一个数变成当前数的倍数，要求数列满足递增。

题解：将每一个数尽可能小的变成大于前一个数，而且是当前数的倍数即可。

Problem F

Solved by Kilo_5723. 1:05 (+)

Problem G

Solved by Xiejiadong. 2:41 (+1)

题意：每次可以去掉 $1\times k$ 的区间里的石头，询问去掉 $1$ 到 $n$ 行中，$[l,r]$ 列里面的石头至少需要几次操作。

题解：显然对于每一行，可以单独考虑。

考虑每一行的每一列作为开头的时候，操作 $1$ 次，最多可以处理到第几列（需要跳过本来就为空的位置）。

之后就可以用倍增的方式得到，从每一个行的每一列开始处理 $2^k$ 次，可以处理到第几列。

对于每次询问，考虑每一行所需要的次数，用预处理出来的结果进行逼近即可得到。

Problem H

Solved by Xiejiadong && Kilo_5723. 0:41 (+)

题意：每次可以询问两个数的大小，需要通过不多余 $n+20$ 次询问，询问出 $n$ 个数中的次大值。

题解：考虑分治的方法求最小值的时候，会选择左边的最小值和右边的最小值比较得到更小的。

而显然次小值，一定是在和最小值做比较的时候被淘汰的，于是考虑，保存下很每一个数比较的时候淘汰的数，得到最小值以后，通过这个数淘汰的数中选择最小的，显然就是次小值。

显然，被淘汰的数，由分治的层数决定，不会超过 $log_2n$ 个。

Problem I

Unsolved.

Problem J

Upsolved by Kilo_5723.

Problem K

Solved by Weaver_zhu. 0:50 (+1)

题意：一棵树，每个边上有流量和容量，求以每个点为根的情况下，叶子节点为多个源头，根为终点的最大流

题解：树型换根dp