锐客网

  1. 首页 > it技术 > >

NOIP|NOIP 模拟 八十五

T1 冲刺NOIP2021模拟18 莓良心 容易发现答案和每一个 \(w_i\) 无关，我们只需要求出总和然后计算方案数。
对于每一个数贡献的方案数是相同的，首先是自己的部分就是\(\begin{Bmatrix} n\\k\end{Bmatrix}\)。
然后考虑每个数和其他数在一组时都会额外有贡献，考虑将两个数捆绑那么答案是 \((n-1)\times\begin{Bmatrix} n-1\\k\end{Bmatrix}\)
计算只需要以上两个第二类斯特林数就可以完成。
\(\mathcal O(n^2)\) 的计算方式显然不能满足实现，我们需要容斥去求。
\(\begin{Bmatrix} n\\k\end{Bmatrix}=\frac{1}{k!}\times \sum \limits _{i=0}^{k}(-1)^i\times \begin{pmatrix} k\\i\end{pmatrix}\times (k-i)^n\)
后面的幂可以线性递推，复杂度\(\mathcal O(n)\)。
T2 冲刺NOIP2021模拟18 尽梨了 考虑两个商店满足\(a_1\times (b_2+1)>a_2\times(b_1+1)\)，一定是第一个在前面。
首先根据以上要求排序，然后考虑 \(\mathcal O(n^2)\) 的 dp。设 \(dp_{i,j}\) 为考虑前 i 个，选了 j 个的最小时间。
转移只选要看当前点是否要去选择。
对于 a 不为 0，我们发现时间的增长是指数型的，于是第二维只有 log 级别。
然后考虑 加上 a 为0，此时我们二分，能塞多少塞多少。
然后得到答案。此题重在分析数据。
T3 冲刺NOIP2021模拟18 团不过 考虑求出先手必败的方案数，用总方案减去即可。
设 \(p_i\) 为\(2^n-1\) 的 i 次下降幂，这样总方案显然为 \(p_n\)。
设 \(f_i\) 为 i 堆石子先手必败的方案数。我们只需要根据前 i-1 的结果来调整即可。
【NOIP|NOIP 模拟 八十五】
\[f_i=p_{i-1}-f_{i-1}-f_{i-2}\times(i-1)\times(2^n-i+1) \]
这样递推是减去了前 i-1 为 0 这一位不可取 0，后者是任意 i-2 为 0 然后 这一位会和前面有相同。
T4 冲刺NOIP2021模拟18 七负我 根据调整法答案最大是把时间均分给最大的完全图。
我们只需要找出最大的完全图即可。
meet in middle 。前面 dp ，后面 并出边根据 dp 数组出答案。

    推荐阅读


    上一篇：关于vue在PC端，对不同屏幕进行适配，未使用媒体查询（大小的自适应）的问题

    下一篇：Sunny丰盛日记day|Sunny丰盛日记day 72