XX Open Cup named after E.V. Pankratiev. Grand Prix of Siberia, Division 1.
Problem A
Solved by Kilo_5723. 0:09 (+)
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