7.5测试
7.11测试总结

7.6测试总结

YYY posted @ 2016年7月06日 16:47 in OI相关 with tags 简单题 乱搞 DP 状态压缩 容斥原理 莫比乌斯反演 , 950 阅读
_THIS_IS_START_OF_ARTICLE_
​---------------------------------------------------------------------------
简单场
挂得跟什么一样...
 
​---------------------------------------------------------------------------
T1:
题意给你n个数,让你选出一个最大的集合使得这个集合中的数互质,输出集合大小
 
<=n^0.5的素数状压,>n^0.5的素数每个人最多有一个,一样的只能选一个,枚举选哪一个,转移就行了
​---------------------------------------------------------------------------
T2:
题意是给你n个数,每个数不超过m,让你选一个集合使得这个集合gcd不为1,再选一个数,使得把这个数加进这个集合后这个集合gcd就为1了,问方案数
 
推一下公式:
设u[i]表示gcd为i的倍数的集合个数
设v[i]表示gcd为i的集合个数
设l[i]表示a[j]|i的j个数
答案r=Σ(i=1,n)Σ(j=1,n)v[j]*[(a[i],j) = 1]
=Σ(i=1,n)Σ(j=1,n)v[j]*Σ(d|(a[i],j) miu(d)
=Σ(i=1,n)Σ(d|a[i]) miu(d) Σ(j是d的倍数)v[j]
=Σ(d=1,n)miu(d) l[d] * u[j]
=Σ(d=1,n)miu(d) l[d] * (2^(l[i])-1)
原题要求gcd不为1,所以减去某个数就可以了
​---------------------------------------------------------------------------
T3:
给你一棵带权树,设S(u)表示u的儿子集合,定义f(u,v)=Σ(x∈S(v))dis(u,x)^2 -  Σ(x∉S(v))dis(u,x)^2,q个询问,每次询问f(u,v)
 
标算太简单了,就是预处理一下随便讨论一下,搞一搞
​---------------------------------------------------------------------------
 
_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter