NOIP集训-10.14总结

今天简直跪爽了啊...
 
--------------------------------------------------------------
Hello:SuperOj925
 
我考试的时候写的错误的贪心:(然而出题人并没有给我卡掉)
每次把剩下的最大的给Bob,如果有多个最大的,搜索。
(这个要卡WA或者卡成TLE都是可以的,最方便的就是所有数都出一样的,这个算法就变成暴力了..)
 
 
标算:
考虑DP:f(i,j)表示A选了i个,B选了j个
然后写一个n^2的转移就可以了...
 
--------------------------------------------------------------
Rect:SuperOj926
 
啊啊啊我考试的时候内存没开够...哭死(应该用map的..)
 
签到题一道..
 
发现每个子矩阵(a,b,c,d)(a,b,c,d分别为left,right,top,bottom)的和就是:
Σ(i=a,b)Σ(j=c,d) s(i)*s(j) 
= Σ(i=a,b)s(i) * Σ(j=c,d)s(j) 
= (Σ(i=a,b)s(i)) * (Σ(j=c,d)s(j))
= (sum(b) - sum(a-1)) * (sum(d) - sum(c-1))
其中sum表示前缀和
前缀和之差一共只有n^2个,可以吧它们全部预处理出来,放到map里(TAT),
然后对题目给的数a分解因数,对于一组因数a = p * q,每次到map里询问p和q的个数就可以了
另外要特判一下a = 0的情况
 
--------------------------------------------------------------
Half:SuperOj927
 
先说一下我考试时候写的算法(这个也是可以ac的,然而我写挂了...加了一点不必要的优化)
首先假设我们随机选了一个数,答案是这个数的约数的概率是1/2
因此可以枚举其所有约数,验证,更新答案
假设我们重复以上过程k次,时间复杂度O(n*约数个数*k),正确概率1-(2^-k)
 
标算对于验证一个数的某个约数是多少个数的约数的方法比较机智:
p一个约数a若是也数q的约数,那么一定有:a | gcd(p,q)
因此只需要求出p和所有数的gcd的的出现次数,先存起来,
(这里gcd会很大,但是一定等于p的某个约数,因此可以把p的所有约数预先离散化然后二分查找)
然后对于p的某个约数a,找到p的所有约数中是它的倍数的,
累加它们的出现次数,就是整除a的数的个数
然后同样重复以上过程k次,时间复杂度O(k*n*log + k*(约数个数^2)),正确概率1-(2^-k)
--------------------------------------------------------------