12.28测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
BJOI2015 Day1..
-----------------------------------------------------------
T1:
线段树套桶随意水过..
不过这个方法空间比较大,要用short
也可以套个BST或者线段树什么的..
-----------------------------------------------------------
T2:
乱搞一下水过了
乱搞的方法是枚举每个节点作为根，搜索一遍得到每个节点的size,深度，外加每个节点的度数
把所有节点按size为第一关键字,深度为第二关键字,度数为第三关键字排序
然后比较两棵树是不是同构的时候，先枚举根，然后看在这个根下上面说的那个序列，每一个对应位置的size，深度，度数是不是都一样，都一样就判断为同构
标算好像是异或哈希什么的（写了标算的强哥一脸这个证明留作练习的表情）
-----------------------------------------------------------
T3:
首先假设一行有s种选法，那显然最后答案就是C(s,n)*(n!) = (s!)/((s-n)!) = π(i=s-n+1,s)i，如果算出了s，那么这个可以暴力算出来
现在看怎么求s
首先想了个显然的DP:设前i个位置，最后一个位置是j，那么有f(i,j) = Σ(k=1,j)f(i-1,k)且s = f(m,k)
这个转移方程等价于:f(i,j) = f(i-1,j) + f(i,j-1)（到这一步，有40分，不要问我怎么知道的）
插板法得f(i,j) = C(i+j-1,i)
因此s就是C(m+k-1,m) = ((m+k-1)!)/((m!)((k-1)!)) = (π(i=k,m+k-1)i)/(m!)
发现上面只有m项，下面只有m项
因此暴力上下分解质因数
最后下面一定会被消掉
上面剩下的质因数乘起来就得到了s
-----------------------------------------------------------
评论 (0)
