先来屯的题吧
[2009国家集训队]小Z的袜子(hose):这题坑死我了，可以分块搞，但通用解法是MMST+莫队算法，我的那个生成树部分似乎有问题。Code:b2038
UPD:[HNOI2008]GT考试:弱渣就是弱，DP都不会。。。 Code:b1009
做几道大原题：1588 1500 1208 1901 1061 1016 1004 1018 1834 1031 1019其实1067还没完成
UPD:【2014.1.1】上一批题处理完了。。。
[SCOI2007]降雨量:很恶心的数据结构题，情况太多了，不过1A了。Code:b1067
[HNOI2008]明明的烦恼:树的prufer编码，然后排列组合+高精度。Code:b1005
[JSOI2008]魔兽地图DotR:树形DP，我只会很弱的解法 Code:b1017
[Noi2013]矩阵游戏:这题虽是NOI的题，但其实难度不高 首先推公式 f[1]=x,f[i]=af[i-1]+b 它的通项公式为f[m]=a^(m-1)*x+a^(m-2)*b+a^(m-1)*b+…+a^0+b＝＞f[m]=a^(m-1)*x+(a^(m-1)-1)/(a-1) *b 我们发现后面是常数,设后面的东西为T，则可以推出题目中f[i][1]的公式 f[i][1]=c*f[i-1][m]+d 而f[i-1][m]=a^(m-1)*f[i-1][1]+T，所以f[i][1]=c*(a^(m-1)*f[i-1][1]+T)+d 展开得 f[i][1]=c*a^(m-1)*f[i-1][1]+cT+d 然后把c*a^(m-1)看成a，把后面的常数cT+d看成是b，又可以用基本公式了。 Code:b3240
[JSOI2009]火星藏宝图：注意到A能转移到B，B能转移到C的话，显然不会用A来更新C(因为a^2+b^2<=(a+b)^2)所以这样就可以优化复杂度了 Code:b1560
[ZJOI2008]树的统计Count:裸的树链剖分 Code:b1036
Views:
482
|
Added by:
dhy0077
|
Date:
12.28.2013