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

Problem A

Solved by Kilo_5723. 0:09 (+)

Problem B

Unsolved.

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)