【LGR-050】洛谷8月月赛I 相关

8月预赛大礼包：课件+T2markdown题解（神TM我放了一道T4题面，题解见下）+反演教程+标程+你们要的图 链接: https://pan.baidu.com/s/1tiSjTAZmxv1rdjqOADok4A 密码: yzby --- 先放两道markdown题解，其余的会陆陆续续地~~咕~~更新上来 --- # T2 ## 30分做法 由于$n$只有10，可以爆搜。 ## 60分做法 考虑这样一种贪心：每次选择最小的两个数字，设最小为$x$，次小为$y$。 - 如果$2x \le y$，那么就把$x$丢弃（之后就不管了）； - 如果$2x > y$， 就把$y$减小到$x$，然后把它们组合成$2x$。 不断重复这个操作，直到只剩一个数，就是答案。证明在最后部分。 可以使用一个堆（优先队列）来维护最小数，总复杂度$O(n\log n)$。 ## 100分做法 由于$n$达到了$10^7$的级别，需要一个$O(n)$的算法。考虑在60分做法的基础上进行优化。 和[NOIP2016 蚯蚓](https://www.luogu.org/problemnew/show/P2827)类似，可以观察到一个性质：按照上面的方法，每次合成出来的数字大小是不断增加的。于是可以用一个队列来维护合成出来的数字，每次的最小值只可能在队头取到。 然后将原数列进行桶排序，每次在排序后的数列和队列中取最小值，就可以做到$O(n)$的总复杂度了。 ## 贪心的证明 首先注意到，如果一个数对最后答案有贡献，要么本身成为最大值，要么与其他数合成一个更大的。 同时，每次合并都要产生一个比原来两个数更大的数，否则没有意义。 然后分别来看两种情况： - 如果$2x \le y$，那么就把$x$丢弃； 首先，$x$成为不了最大值，假设$x$与某个数$z$合并。由于$y$是次小值，所以$y \le z$。然而$x$和$z$合并，最大只能变成$2x$。而$2x \le y \le z$，合并之后没有得到更大的数，不如不合并，所以$x$应该丢弃。 - 如果$2x > y$， 就把$y$减小到$x$，然后把它们组合成$2x$。 $x$成为不了最大值，所以$x$会与其他数合并或者丢弃。因为$x$是最小的，与其他数合并只能合出$2x$，所以那个数应该越小越好（用一个更大的数会造成“浪费”），故应该用$y$。合并之后，相比于直接丢弃，得到了一个更大的数($2x > y$)，所以这样合并是最优的。 --- # T4 题意：在$n\times m$的棋盘上，放$2\times n$个棋子，每行每列最多两个棋子的方案数 显然每行恰好两个棋子。 转换模型：将$1..m$各$2$个（表示纵坐标），填入$n$对无序二元组（表示行），且二元组内两数不同 考虑容斥（二项式反演）：$f(n,m)$表示原题答案，$g(n,m)$表示$1..m$各$2$个，填到$2\times n$个格子里的方案，则易知 先思考$g$的计算：考虑选用了$n-i$对一样的数字，然后剩下的位置要从$m-n-i$种数字中选出$2i$个单独的数字补足$2n$个格子，之后就是有部分元素相同的全排列（乘上全排列，再除掉相同数字交换的结果），即 $$ \huge g(n,m)=(2n)!\sum^{min(m-n,n)}_{i=0}\frac{C^{n-i}_mC^{2i}_{m-n+i}}{2^{n-i}}$$ 再考虑用$f$算$g$：$g$中“$2\times n$个格子”等价于“$n$对有序二元组”，那么枚举有$n$对有序二元组中**选**$i$对填写了相同的数字，再用$m$中的$i$种数字**排**进他们，剩下的位置是$f(n-i,m-i)$的情况，即 $$\huge g(n,m)=\sum_{i=0}^nC^i_nA^i_m2^nf(n-i,m-i)$$ XJB反（rong）演（chi）一下 $$ \huge f(n,m)=\frac{1}{2^n}\sum_{i=0}^n(-1)^iC_n^iA_m^ig(n-i,m-i) $$ 然后你就得到了一个看起来是$O(nm)$的算法 但是我们发现计算$g$是$O(min(m-n,n))$的，出题人也很有默契的写了$m-n\leq10$ 到此，你就能通过100%的数据辣