12.16模拟赛总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
说是模拟赛，其实就是TJOI2015...
BZOJP3999~4001
-------------------------------------------------------------
T1:
线段树+树链剖分
挺难写的
大家都说是树链剖分裸题，但为什么我觉得是日狗线段树题啊？？
考场上调了很久，结果看起来对拍没有问题，其实有一个小Bug
然后就没有然后了
-------------------------------------------------------------
T2:
状态压缩,DP
预处理得到can[i][j]表示上一行是状态i，下一行是状态j，可不可以（为1表示不会互相攻击到,为0表示会）
然后就有DP：f[i][j]表示前i行，当前状态是j
f[0][0] = 1
f[i][s1] = ∑(s2) can[s1][s2] * f[i-1][s2]
暴力转移会T(其实因为数据很水所以优化一下常数也能过~不要问我怎么知道的)，可以用矩乘加速转移
-------------------------------------------------------------
T3:
很容易得到一个DP方程f(x)表示节点数为x的同构数，g(x)表示节点数为x的所有同构的总叶子数
显然答案是g(x)/f(x)
甚至可以用矩乘来递推到10^9项
但是，精度不够啊,爆long long了啊
某czh勇士用long double强行拿了70分
然后，打表发现规律:
答案r=(n*(n+1)/2)/(2*n-1)
成功A掉~
-------------------------------------------------------------
评论 (0)
