2016.2.19总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------
照样先说题意：
T1:给定一张图，每次询问如果删掉某条边，最小生成树的大小（各询问独立），树的大小n<=5*10^5,边数m和询问数q<=10^6
T2:给定一个长度为n的整数序列，其中每个数在[1,10]内,对于所有子序列,求每个元素减这个子序列平均数的平方，精度越高分越高，和,n<=10000，20组询问
T3:提答题,你有n个英雄,每个人有3项属性,你可以任意排他们的位置，现在你可以花费一定代价提升某个人的某项属性,你要使得每个人的各项属性都大于等于前面的人的这项属性,输出花费最小的排列,越优分越高
--------------------------------------------------------
T1:
首先可以知道断掉一条边后,如果这个边不在MST上，那么答案不变,否则答案是MST大小减去这条边加上这两个点之间某条路径的某条边，满足这条边最小且不是树边
考场上想了个n*log*log的，然而并没有写出来..（其实写出来估计也要T...）：
考虑树形DP:
f(x)表示断掉MST上x这个点和他父亲的连边后的答案
那么容易知道f(x)是x这个子树所有的点向外连的边的最小值
对每个节点维护一个splay,初始为其所连的所有节点，按DFS序排序，另有一个边权，并且对边权维护一个区间最小值
转移的时候，合并这个点和他所有儿子的splay，指向相同的的点的保留较小者
一个子树的DFS一定是一段连续的区间
可以知道f(x)就是除了这段区间之外的最小值，可以在splay中询问出来
有一个细节，在x这个节点合并他与儿子的splay之前，应该把他的父亲从是splay中删去，以实现断开他与父亲的连边
时间复杂度O(n*log*log)两个log来源于splay启发式合并
然而上面那个算法并没有什么卵用...标算是O(n*log)的而且常数超小
首先考虑另一种n*log*log的算法：
枚举每一条非树边，用他的边权去更新他所连的两点间的路径上所有点的f，用树链剖分+线段树维护
现在考虑优化：可以把非树边排序，依次更新，这样保证每个点第一次被更新的就是最优的，因此更新过的点就不用更新了，于是用并查集维护一下，每次把当前更新的点和他的父亲并起来，并且保证并查集中作为根的点是最浅点
复杂度O(n*log)来源于排序
--------------------------------------------------------
T2:
考场上搞了好久，化了好多式子，但是都感觉没法求...
感觉最靠谱的是这个：
答案=A-∑(i=1,n)∑(j=i,n)(sj-s(i-1))/(j-i+1)
其中si表示前i个元素之和
A=∑(i=1,n)∑(j=i,n)∑(k=l,r)ak^2
其中ak表示原序列第k个元素...
这样是(n^2)/2的，总赶脚优化下能过（然而并不能）
顺便，有一种优化是每k个分一组，枚举所有可能的分组,组内答案处理出来,然后枚举两个组,视为相邻，答案求出来，然后化一下式子发现两个组相邻一定元素的答案可以用视为两个相邻的情况下的一些计算结果O(k)算出来
然后枚举每个组，累加组内答案,然后枚举两个组，用之前处理出来的结果搞，这样是((n^2)/(2*k))+10^k的
update:
哇靠我发现n^2的能过而且比标算快...smg...
标算：
第一部分和第二部分都可以线性时间内求出来，第三部分把s数组复制一遍，翻转，然后FFT即可（具体怎么回事可以自己yy一下）（我考试的时候就卡在第三部分上了...）
--------------------------------------------------------
T3:
爬山法可拿30分左右...
我考试的时候random_shuffle拿了12分...
标算等我弄懂了再加...
--------------------------------------------------------
评论 (0)
