多校冲刺 NOIP 20211029 模拟 (18)

T1

若两个物品i,j被分到了一组,贡献是\(w_i+w_j\)

考虑将所有二元组和单个元素的贡献分别计算

\(S(n,k)* \sum_i w_i+(n-1)*S(n-1,k)* \sum_i w_i\)

第二类斯特林数求单点的容斥方法

\(S(n,k)=\frac{1}{k!}\sum_{i=0}^{k}(-1)^i{k\choose i}{(k-i)}^n\)

大概就是将集合标号,枚举强制不选i个集合然后容斥

因为集合本身没有编号,所以最后乘上逆元

T2

若两个物品都选,设到时间为t,若先到i比先到j优

\[t+a_it+b_i+(t+a_it+b_i+1)a_j+b_j<t+a_jt+b_j+(t+a_jt+b_j+1)a_i+b_i \]

\[a_j(b_i+1)<a_i(b_j+1) \]

于是可以先排序,然后dp[i][j]表示前i个里选j个的最短时间

发现若\(a_i>=1\),每次的时间至少翻一倍,第二维可以缩成log

若\(a_i=0\),按照这种排序方式\(i\)一定在最后;

于是可以先把\(a_i>0\)dp完,把\(a_i=0\)按照\(b_i\)升序,然后用dp的每个最终状态贪心选,\(O(n\log n)\)

T3

设\(p_i\)表示\((2^n-1)^{\underline{i}}\),即全部的合法方案

设\(f_i\)表示选了 i 个石子的必败方案数,答案就是\(p_n-f_n\)

考虑转移\(f\)

  1. 选第 i个石子时,可以由前 i-1 个的所有石子异或,第i个再抵消,方案数\(p_{i-1}\)

  2. 若前 i-1 个疑惑和为0,不合法,减去\(f_{i-1}\)

  3. 若最后两堆相等也不合法,方案数\((2^n-i+1)* (i-1)* f_{i-2}\),但是我写成+2才对,不知道为啥

T4

结论是选最大完全图,每次平均分配

证明是完全图的话就考虑在完全图上删边和加边,发现答案是降低的

平均分配的话使用调整法

然后可以meet in the middle,设\(p=\frac{n}{2}\),前p个\(f_S\)表示 S 集合的最大完全图,可以\(n2^p\)求

后n-p个,假设枚举到的集合为 S,那么若 S 为完全图,设其所有点的邻边的交集在前p个里是 T ,这时找到了一个\(|S|+f_T\)的完全图

上一篇:2021.10.30考试总结[冲刺NOIP模拟19]


下一篇:多校冲刺NOIP模拟20 - 集合均值——期望、线性逆元