1.16测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
突然发现好久都没写总结了...
今天的题网上找不到，这里简单写一下题意好了
----------------------------------------------------------------
题意：
T1:n个白色小球排成一个环，每次随机选一段来染黑，求期望多少次全部染黑。n≤10
T2:给定n维向量a,保证lb(n)是整数，求向量x,满足xi = Σ(i&j = j)aj ,其中&表示位与,n≤2^20
T3:给定实数集的子集S,求S有多少个大小等于4的子集，以其4个元素为边长的四边形不存在(即a+b+c<=d,其中d是这个子集中最大的元素)，|S|≤20000,S中的元素≤20000
----------------------------------------------------------------
T1:
用一个整数来表示一个状态
设f(i)表示染黑成i这个状态期望多少步,设S为第一次染色所有可能出现的状态集合,有转移：
f(i) = Σ(j属于S)p(j)*f(i or j) + 1,其中or表示位或
其中p(j)表示j这个状态出现的概率,为定值1/|S|
于是得到:(1-Σ((i or j) = i)p(j))f(i) = Σ(j属于S且(i or j) ≠ i)p(j)*f(i or j) + 1
记忆化搜索，在本机跑出来然后打表就好
----------------------------------------------------------------
T2:
裸的n维前缀和
枚举每一维，然后枚举其他维，对这一维做前缀和，覆盖原来的
最后的数组里面就是n维前缀和
----------------------------------------------------------------
T3:
设f(a,x) = Σ(i=1,|a|)x^ai
容斥一下，显然答案就是(1/6) * (f(a,x)^3 - 3*f(a,x^2)*f(a,x) + 2*f(a,x^3))
FFT就好
----------------------------------------------------------------
评论 (0)
