NOIP集训-10.16总结

表示一直在做第三题,然后花五分钟写了第一题的70分,第二题看都没看,然而第三题还是没调出来...简直跪爽!
 
-------------------------------------------------------------------
1807:SuperOj931
 
SB DP..
-------------------------------------------------------------------
Minimum:SuperOj932
 
首先从每个白点开始,跑一次最短路,看哪些黑点是需要到达的,以及哪些边需要保留
这样就得到了一个森林,显然需要在其中选一些边,使得原来连通的依然连通
发现是MST,但是是个森林,不好搞
可以加一个超级节点,连向所有边,这样就搞成一个MST问题了...
 
-------------------------------------------------------------------
Gcd:SuperOj933
 
有意思的题,先说一下我考试时候的做法(后来调出来了,因常数太大而TLE..TAT):
假设Si表示gcd为i的倍数的子集个数
这个可以通过枚举i的倍数求得
求出Si的时间复杂度是O(M/1 + M/2 + M/3 + ... + M/M) = O(M*ln(M)) (M为数组中最大数)
然后可以通过素数容斥求出gcd刚好为1的子集个数p:
p = Σ(i=1,M) miu(i)*Si
然后可以再用一次素数容斥求出答案,伪代码如下(已略去求模):
(已预先排除集合中所有的1,并得到了1的个数num)
ans <- ((2^n - 1) - p) * num
for i ∈ a     (这里及之后用∈符号表示i是数组a中的元素)
  for j | i
    ans <- ans + miu(j) * Sj
  end
end
然后这个的时间复杂度是O(n*(M^0.5))的,在M=10^7,n=10^5这个数量级下和O(M*ln(M))差不多大
然后就T掉了...
 
标算:
发现答案就是:
总的方法数-Σ(gcd为1子集)(n-子集大小)-Σ(gcd不为1的子集)子集大小
设p = Σ(gcd不为1的子集)子集个数
  q = Σ(gcd不为1的子集)子集大小
化简原式然后可以得到答案的表达式为:
2*q - n*p + n
接下来只需要求出p、q就可以了
可以用素数容斥:(假设Li表示i的倍数出现的个数)
p = Σ(i∈a) miu(i) * (2^(Li)-1)
q = Σ(i∈a) miu(i) * (Li* (2^(Li-1)))
然后这个算法的时间复杂度是O(n*ln(M))的,和上面那个复杂度一样,但是常数小一倍...
 
-------------------------------------------------------------------