1.20测试总结

最近总挂零..
-------------------------------------------------------
 
这次考的是wc2010,还是说下题意..
T1:求树上长度在[L,R]以内的链最大平均权值,n<=50000,时间4s
T2:有n个粒子,每个粒子有m,c两个属性,结合任意两个粒子产生的贡献是m1*m2*(c1-c2)(是有序的),两个问,第一个问问任意两个粒子结合产生的最大贡献,第二个问让选一个环,首尾相接,且负贡献必须连续,问最大贡献,n<=50000
T3:提答题,给出1~n的一个排列和m个轮换,求用这些轮换把那个排列弄有序的方案,步数越少分越高
-------------------------------------------------------
T1:
二分答案,得到mid
把每个边减去mid,验证是否有长度在[L,R]内权值大于等于0的边
因此问题转换成了求树上最长链
点分,对于某个点v,每个子树求一个f(i),表示这个子树内长度为i的最大权值(一条到根的链)
保存一个g(i),表示以前的表示长度为i的到根的链的最大权值
记一个r表示过根的长度为[L,R]之间的最大权值的链
考虑合并f和g,有r=max{r,max{f(i)+g(j) | L<=i+j<=R}}
枚举f(i),要用L-i<=j<=R-i的g(j)去更新r
发现i递减,g(j)每次是一个递增的定长区间,因此可以用单调队列维护
然后最后要用f更新g
另外这题卡常数
-------------------------------------------------------
T2:
展开,贡献是m1c1m2 - m2c2m1
设fi=mici
第一问:
发现要最大化fimj-fjmi
考虑枚举i
设K=fi/mi=ci
X=mj
Y=fj
B=(fimj-fjmi)/mi
那么就是要最大化B,满足Y=KX-B,最后用B*mi来更新答案
排个序维护个凸壳搞一搞就好了
第二问:
设xi=fi,yi=mi
因此要求连续的xiyj-xjyi
发现是叉积,也就是有向面积
负权要连续,因此面积是不可能被重复计算的
因此求个凸包就行了
-------------------------------------------------------
T3:
数据很有规律
前三个点轮换大小大于一,但是数据很小,可以搜索
后面的点轮换大小都是2,可以建一个图,那么相当于每次交换一条边连着的两个点,要让编号为i的点变为i
第四个点是个链,因此每次可以交换相邻的两个点,冒泡排序即可
第五个点是个完全图,每次可以交换任意两个点,随便怎么排下序就可以了
第六,七个点所有点都和1相连,还是排序,只不过每次代价是三步
第八,九,十个点都是树,还是排序,只不过每次交换的代价是到LCA的代价,然后发现这三个点都是完全二叉树,因此到LCA的代价不会超过log
-------------------------------------------------------