Difference between revisions of "XX Open Cup named after E.V. Pankratiev. Grand Prix of Siberia, Division 1."
Line 68: | Line 68: | ||
Solved by Weaver_zhu. 0:50 (+1) | Solved by Weaver_zhu. 0:50 (+1) | ||
+ | |||
+ | 题意:一棵树,每个边上有流量和容量,求以每个点为根的情况下,叶子节点为多个源头,根为终点的最大流 | ||
+ | |||
+ | 题解:树型换根dp |
Revision as of 07:51, 19 February 2020
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)
题意:一棵树,每个边上有流量和容量,求以每个点为根的情况下,叶子节点为多个源头,根为终点的最大流
题解:树型换根dp