TJOI2015 Day2解题报告

旅游:

在一棵N<=10^5的树上要求支持:①从a点走到b点,求最大的value[j]-value[i],其中i,j是点,i在路径中出现的位置先于j。②将a~b路径上每个点的value加上v。

自然可以用树链剖分/LCT做。每一段区间存四个数:①“后减前”型的最大值fmx,②“前减后”型的最大值bmx(这是由于有时候区间可能会被翻转),③最大值mx,④最小值mn。合并时的思路是这样的:合并区间的fmx要么是max(a.fmx,b.fmx),要么是b.mx-a.mn。它们分别对应于没有跨越mid和跨越了mid这两种情况。bmx同理。

树链剖分的具体细节十分复杂,调了半天。

棋盘:

这道题的题面比较坑:它是从0开始编号的,也就是说棋子是站在中间那一行,能打到上面那一行和下面那一行。所以某一行的棋子放置只和相邻行有关。而每一行一共至多2^M(不超过64)种放法,也就是说可以预处理出来转移矩阵:D[i][j]=1代表上一行为i时下一行可以为j。然后用矩阵快速幂搞即可。

概率论:

先写个N^2的70分暴力。算出两个数组:statesum[i]代表有i个节点的树共有多少种,sonsum[i]代表所有不同情况中的叶子节点个数之和。那么i个节点的树的答案自然就是sonsum[i]/statesum[i]。把暴力打的表全部输出,可以发现statesum[i]就是卡特兰数C[i],而sonsum[i]一定是i的倍数。多少倍呢?也是卡特兰数,确切的讲是C[i-1]。那么n个节点的树,答案就是n*C[n-1]/C[n]。把卡特兰数的通项公式代进去,答案就是n*(n+1)/(2*(2n-1))。

具体的证明十分复杂,需要求出生成函数,然后用广义二项式定理求系数,然后再用积分求另外一个系数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注