12.28测试总结

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
-----------------------------------------------------------