20191031模拟-akc

akc的场

CF750G New Year and Binary Tree Paths

题意:无限大二叉树以二叉堆式编号,给出$S \le 1e15$,统计多少条路径(无方向)的编号和为S

请先思考后再展开

很自然的想法是在lca处计算贡献,枚举左孩子链长L1(边数),右孩子的链长L2,那么考虑每次是向左还是向右,(不妨设$L1 \ge L2$,另一种情况类似)发现满足:

$LCA*(2^{L1+1}+2^{L2+1}-3)+(2^{L2}-1) \le S \le LCA*(2^{L1+1}+2^{L2+1}-3)+(2^{L2}-1)+(2^{L1}+2^{L2}-L1-L2-2)$,发现枚举L1和L2的话,合法的LCA只有$O(1)$个,枚举每个来判断即可

接下来等价于,初始值是$LCA*(2^{L1+1}+2^{L2+1}-3)+(2^{L2}-1)$,然后$k \in [1,L2-1],可以选0/1/2个2^k-1,其中选一个的话权值为2;k \in [L2,L1-1],可以选0/1个2^k-1$

要求拼出S,很明显可以枚举最后总计做了cnt次-1,然后就不会了……

其实也不难来着,主要是不要被上面一车东西搞得有点晕(当时想到了从低位开始处理,但想dp的时候还以为进位会很多),每个位置最大才3不会滚雪球……

总结:枚举L1、L2、做了$cnt \le L1+L2$次-1,然后现在要拼出$S-LCA*(2^{L1+1}+2^{L2+1}-3)-(2^{L2}-1)+cnt$,设$dp(i,cnt,0/1)$=从低到高处理到第i位,目前做了cnt次-1,然后进位是0/1的带权方案数,$O(log_2^5S)$

code

CF715D Create a Maze

题意:只给出$T \le 1e18$,构造一个$n,m \le 50$的表格,相邻格间可以放木板(共$k \le 300$)个,使得$(1,1) \to (n,m)$的方案数恰为T

请先思考后再展开

一个比较好想的是二进制分解,就是通过log行,在最后一行凑出$1,2,4,8,16….$,这样m也是log级别,k是log方级别,感兴趣可见code

注意到这样搞完全没有合理利用到表格特性,是单纯地往一侧推的;更加高妙的方法是使用3进制,然后有两条路径分别求和;

于是边长、障碍点都是$O(log_3n)$的

CF713D Animals and Puzzle

这里

「SDOI2019」连续子序列

做不来,告辞

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