CFR596

CFR596 div1

好题:CF1246C Rock Is Push、CF1246E To Make 1

比赛的时候C做了1h,导致没时间做D,其实还是很可做的

CF1246A p-binary

题意:给出$1 \le n \le 1e9和-1e3 \le p \le 1e3,问最小的t使得n为t个可以相同的【2^{非负}+p】之和$

请先思考后再展开

对于一个t,考虑如何判断是否可行;$n-tp<0$显然无解,然后至少是$__builtin_popcount(n-tp)$,至多是n-tp,而只要在这之内,肯定能用t个$2^{非负}表示出n-tp$;于是显然t没有必要超过logn,直接枚举t即可,code

CF1246B Power Products

题意:给出n个数$a_i$,统计$\sum_{i=1}^n \sum_{j=i+1}^n [\exists x^k=a_i*a_j ]$,$a_i,n \le 1e5$

请先思考后再展开

agc003D - Anticube有点像,把每个数分解质因数,指数模k,称得到的数为这个数的最简式(显然不大于),于是能和这个数匹配的最简式是唯一确定的,直接拿个东西计数,边输入边找即可

$O(分解质因数+nlogn)$,code

CF1246C Rock Is Push

题意:给出一个有石子的表格,n行m列($n,m \le 2e3$),要从$(1,1)到(n,m)$,然后像这样走,要求只能向右或下,石子不能被推出去,求方案数模1e9+7

请先思考后再展开

一脸dp计数的样子,而且因为只能向右或向下,你会发现向下的时候这一行的石子就没用了,向右的时候这一列也没用了,然后为了能准确得到例如正在向下时下面有多少石子,有点套路地每次强制【向右至少1次+向下至少1次】
$$
\\设从(a,b) \to (i,j),预处理出g[i][j]表示第i行中第j个后面的石子数,h[j][i]表示第j列中第i个后面的石子数
\\f(i,j) = \sum_{a<i} \sum_{b<j} f(a,b),能过来的充要条件明显是g[a][b+1] \le m-j,h[j][a+1] \le n-i
$$
因为g和h是单调的,决策集合明显是个区间,可以双指针维护,递增枚举列j,移动每行的b的双指针(当时写了二分)并记录这行的合法转移的f和,然后递增枚举行i并维护仅对于这一列的指针a,利用前面处理的f和求出能转移过来的总和fsum即可

$O(n^2)$,code

upd:其实没必要每次走两步来着,钦定转向也是可以的,就是多加入一维表示方向,代码复杂度的话可能不会差太多

CF1246D Tree Factory

题意:给出一个n个节点0为根的树(保证父亲标号比自己小),要求构造一条链并求出最小的k,在k步内将这条链变成这棵树并输出每一步;操作为选择一个有祖父的节点,然后将自己的父亲改为祖父;保证$n \le 1e5,操作数 \le 1e6$

请先思考后再展开

一脸贪心的样子,而且很明显倒过来想从树搞成链,每次选一个有兄弟的节点将父亲调整为兄弟(显然链的根还是0)

一开始的想法:从下往上考虑,对于x的每个孩子已经成链,现在要合并链,其实等价于n个数每次选两个合并成新数为其和,最后成一个,每步的代价为min,显然是贪心做,排序后从大往小合并,代价和=总代价和-最大数

冷静想想这并不是很对,考虑x的一个孩子y和孩子z,z的链应该先合到y最大链上,y最大链再往前

那其实修一修就好了,这其实等价于求长链剖分的长链长度,从下往上做排序即可

至于输出方案要正着输出,那么就是从下往上,同一个节点的孩子从小到大做,code

CF1246E To Make 1

题意:给出n个数$a_i$和一个常数K,保证初始n个数都不是k的倍数,做n-1次每次选两个数为其和,并将其中K的次幂除掉,构造方案(每次输出合并的两个值)或判断无解,$n \le 16,k,\sum a_i \le 2e3$

请先思考后再展开

考虑每个数在和中的系数,最后一定满足等式$1=\sum_{i=1}^n a_i*K^{-b_i}$
结论:任意满足上式的b,都能够构造出方案,可以用归纳+构造证明
当$n=1,肯定a_1=1,b_1=0$;对于长度为n的b,考虑得出对于这个局面第一步操作是什么,$B=max\ b_i$,一定存在至少两个$b_i=B$(反证只有一个,变形成$K^B=1+\sum_{i \ne one} a_i*K^{B-b_i>0}$,显然左边是K的倍数而右边不是)
将这个作为最后一次的操作,合并起来,$newb=B-times_of_k(a_i+a_j)$,然后剩下n-1个,继续给他们构造操作
$$
\\于是我们就能做一个较低复杂度的状压dp维护b了,倒推
\\f(S,now=\sum a_i*K^{-b_i}),f(\emptyset,0)=true
\\f(S|2^i,now+a_i)|=f(S,now);f(S,now)|=f(S,now*K)
\\第一种转移的复杂度为2^nn*sum/32,第二种为2^n*sum
$$

code

CF1246F Cursor Distance

咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6d278cf9.html
转载请注明出处,谢谢!