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

题意：有 $n$ 场比赛，有胜负平三种可能，每场胜负平的概率已知。有 $k$ 张选票，第 $i$ 张选票能对 $n$ 个赌局中的 $a_i$ 个填一个选项，$b_i$ 个填两个选项，$c_i$ 个填三个选项，如果每场比赛的结果都被一张选票填选了，可以获得 $k$ 的利润，每张选票有一个价格，资金有限，求最大总利润的期望值。资金与利润无关。

题解：本题有两部分。第一部分是对每张选票求出赌中全部比赛的可能性，第二部分是对每张选票的价格和胜率求出最大总利润。第一部分是一个三维背包，三维分别表示当前填取一个，两个，三个选项的次数。第二部分则是一个普通的背包问题。

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.

题意：给出一个 $n\times n$ 的矩阵，其中 $n$ 个元素出线了恰好一次，剩下所有元素都出现了恰好两次，用最少的交换次数将其变成对称矩阵。

题解：先对对角线上的每个元素依次处理：

• 如果它只出现了一次，跳过。

• 如果它第二次也出现在了对角线上，记录下来并跳过。

• 否则，将它的位置和第二次出现的对称位置上的数交换，继续。

接下来，对矩阵中所有和对称位置上的数不相等的数进行如下操作：

• 如果它和它对称位置上的数都只出现了一次，将这两个数分别与之前记录的某个数出现的两个位置交换。

• 否则对于它和它对称位置上出现了两次的某个数，将另一个数于该数出现的另一个位置交换。

Problem K

Solved by Weaver_zhu. 0:50 (+1)

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

题解：树型换根dp