NOIP集训-10.14总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
今天简直跪爽了啊...
--------------------------------------------------------------
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)
--------------------------------------------------------------
评论 (0)
