2.27测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------------------
题面可能可以在SuperOj上找到(P1295~1297)
--------------------------------------------------------------------
T1:
考完之后我和神犇LCR讨论了一下，后来得到了和标算同样的算法，这里说一下心路历程好了
可以看成是求∑(i=1,n)i*A[p[i]]
一根解是一个排列p
所有比p劣的解中最优的那个一定是由p交换两个相邻元素得到的
所以有一个naive的想法：
首先p入堆，每次从堆中取出答案最小者，把他的最优的儿子入堆，把他的父亲的没入过堆的最优的儿子入堆
这里儿子定义为交换p的两个元素得到的比p劣的解
容易知道前k个出堆的元素就是答案
且不考虑怎么得到更劣的解，这个算法有一个问题就是会有大量的冲突（也就是通过不同的交换序列得到的同样的解）
因此考虑把交换两个元素的操作排序，方法是操作一个位置后就不能在这个位置之前操作了，因此设一个固定位数t，表示这个状态的前t位
已经被固定，不能有转移发生在前t个元素上
但是排序之后有一个问题：有某些解得不到了（具体的，是交换两个不相邻元素得到的解）
因此每次转移除了可以把两个相邻元素交换之外，还可以交换两个不相邻元素
而对于某一个位置，把他和更远的元素交换坑定不如和更近的元素交换优。
因此维护一个堆，s(i)表示目前以i为左端点应该交换哪个元素（初始为i+1），w(i)表示目前交换(i,s(i))对答案的贡献
把s(i)入堆，按w(i)排序
每次从堆中取出最小者t，转移，然后令s(t)=s(t)+1,再把他入堆
这样下次再询问得到的就是次优的解了
然后因为要固定位数，一旦操作了元素i，元素[1,i]就不能操作了
因此用一个区间线段树来代替堆，每次询问最小值，每次做完后把一个前缀赋为+∞
每转移一次，w(i)一定只会修改一个点和一个前缀区间
因此是可以可持久化的
s(i)只会修改一个点，同样可以可持久化
然后答案啊固定位数啊都是可以维护的
另外最多出堆k次
因此时间复杂度O(klogn)
可持久化那一步相当难写，如果暴力搞就是O(n*k*log)的，有80分
--------------------------------------------------------------------
T2:
首先差分，要把整个序列弄成大于零的
每个操作可以看做是n个二元组(i,j)，表示把i这个位置减1，把j这个位置加1
有个很重要的性质是减一一定是不如不减（废话）
因此原来是负数的，最后一定是0（如果加了的话，就一定有另一个减了，但一定是不优的）
考虑费用流建模
每个点，如果是正的，那么他有a[i]的可以“花出去”的流量
如果是负的，那么需要“得到”-a[i]的流量
因此源点向权值为正的点连边流量为a[i]，费用为0
权值为负的点向汇点向连边流量为-a[i]，费用为0
一个操作(i,j)表示i把一个权值“给”j
i向j连边，流量为+∞，费用为c[i]
跑最小费用最大流
最后判断一下是不是所有连向汇点的边都流满了，没有的话表示有些人没有得到应该得到的权值，输出-1，否则输出最小费用
--------------------------------------------------------------------
T3:
看题解只看懂了80分的orz
首先把质数分为大质数（>n^0.5)和小质数（<=n^0.5)
大质数在某个数的质因数分解里面最多只会出现一次
因此对于某一个只由小质数构成的数x，对答案的贡献是f(x)*(1+∑(p<=[n/x])（p+d))其中p是某个质数，[]表示取下整，f是题里面定义的
那个函数
设g(x)=(1+∑(p<=x)p)
因此答案是∑(x)f(x)*g([n/x])
因为[n/x]只有n^0.5种
首先考虑对[n/x]相同的f(x)求和
设h(m)是[n/x]=m的f(x)的和
那么有h(m)=h(m/(p^c))*p^c，其中p是某个质数
但是要保证每个数不重不漏地刚好被算一遍，因此需要特殊的枚举顺序
设r(i)表示[n/x]去重后的的第i小数，大小是|r|
伪代码如下
sum(n)=1
for p = primes that <= n^0.5
c = p
while c <= n
for i = 1 to |r|
sum(i/(p^c)) = sum(i) * a
end
c = c * c
end
end
（话说，题解说这是背包...我也不知道为什么是背包）
时间复杂是O(n*log(log)/log)的
然后考虑算大质数的个数以及和
设F(i,j)表示1~j中不含质数p1~pi的数的个数
设G(i,j)表示1~j中不含质数p1~pi的数的和
枚举j，枚举i，有转移：
F(i,j) = F(i-1,j) − 1
G(i,j) = G(i-1,j) − pi
(pi > j^0.5)
F(i,j) = F(i-1,j) − F(i,[j/pi])
G(i,j) = G(i-1,j) − G(i,[j/pi]) * pi
(pi <= j^0.5)
对于每个j（只会有n^0.5个j），只需枚举小于等于j^0.5的质数来转移
对于大于j^0.5的质数，只需要找到第一个小于等于j^0.5的质数，算一下中间质数个数以及和，可以二分答案
对于j<=n^0.5的比较少
对于j>n^0.5的
复杂度是∑(i=1,n^0.5)[n/i]^0.5
积分一下发现是O(n^0.75)的（这里算的时候为了方便，认为质数个数是O(n)的，实际上是O(n/log)的，因此实际复杂度还要低一点）
然后这个算法被前面那个背包卡成O(n)了，只能拿80分
另外还有一个100分的打表算法
对于每个数，质因子个数不会超过10个
因此把表达式暴力展开后，d的次数也不会超过10
分块对答案的d的每个次项的系数打个表就可以了
--------------------------------------------------------------------
评论 (0)
