2.27测试总结

--------------------------------------------------------------------
题面可能可以在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的每个次项的系数打个表就可以了
--------------------------------------------------------------------