12.16模拟赛总结

说是模拟赛,其实就是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掉~
-------------------------------------------------------------