1.20测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
最近总挂零..
-------------------------------------------------------
这次考的是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
-------------------------------------------------------
评论 (0)
