Chenyao

TJOI2015 day2 题解报告

Posted at — May 14, 2015

BZOJ上的题号分别为3999,4000,4001;COGS上的题号为1978,1979,1980

[TJOI2015] 旅游 给定一棵树,询问操作为求两点u->v路径上两点a,b,$V_b-V_a$的最大值,要求a距离u较近,b距离v较近。直接用树链剖分来做,维护每个区间的最大值、最小值、左边点减右边点的最大值,右边点减左边点的最大值。似乎用LCT代码量可以少一些,不过感觉自己LCT可能虚掉就去敲树链剖分了。

[TJOI2015] 棋盘 题面有些坑其实是自己傻逼读错题。可以发现如果两个棋子会产生冲突那么距离不会超过一行,s为二进制位表示一行每个点是否被放棋子,$f_i,s$表示第$i$行状态为$s$的方案数,预处理转移方案,用矩阵乘法优化。

[TJOI2015] 概率论 萌帝说可以找规律,但是我还是没有看出来。以下萌帝的做法:用$g_i$表示$i$个点的二叉树有多少种同构方式,用$f_i$表示$i$个点的二叉树所有不同构的树的叶子数量和。接着发现$g$其实是卡特兰数。继续打表,发现$fi=i*g{i-1}$。卡特兰数的通项式为$g_i=\frac{\tbinom{2n}{n}}{n+1}$,所以可以得到答案为$\frac{n^2(n+1)}{2n(2n-1)}$。在网上找到了证明,但是没有看懂QAQ 。