【7.29】代码源 - 【排列】【石子游戏 II】【Cow and Snacks】【最小生成数】【数列】

#746. 排列

题意：$T\le 1000,1\le n\le 100$

题解：(贪心)代码源每日一题 Div1 排列

思路：首先按照 $a_i$ 降序排列。当 $n\ge 3$ 时，最坏情况是所有的增益都到了某个人 $a_i$ 的身上，然后这个人的增益到了其他某人 $a_j$ （不是前面的 $a_{i-1}$）身上，这样的话会使得 $a_{i-1},a_i$ 之间的差 $a_i-a_{i-1}$ 最大化。如果最大化之后这两个数仍然非增，那么这两个数不会有矛盾。对于每个 $i$ 都判断一下即可。注意如果 $a$ 值相同的，要按照 $b$ 值升序排列，这样能够使得差值最大化。

AC代码：http://oj.daimayuan.top/submission/309613

---

#738. 石子游戏 II

题意：共有 $n(1\le n\le 10^6)$ 堆石子，其中第 $i$ 堆最初含有 $a_i(1\le a_i\le 10^9)$ 个石子。他们轮流执行下列操作之一：

• 把一堆个数为奇数的石子分成两堆，两堆都不能空。

• 把两堆个数为偶数的石子合成一堆。

不能执行任何操作的人将输掉游戏。问先手必胜或必败。

思路：首先发掘一些性质。操作奇数堆，奇数的个数是不变的，操作一次会多一个偶数；操作偶数堆，偶数个数只会变少，操作一次少一个偶数。那么容易知道偶数堆的数量为偶的局面是必胜态，因为最终偶数堆只会为奇。注意特判先手初始无法操作的情况。

AC代码：http://oj.daimayuan.top/submission/309308

---

#807. Cow and Snacks

题意：

有编号从 $1$ 开始的 $n$ 种小吃，每种小吃只有一份。有 $m$ 个客人会来，每个客人有两种最喜欢的口味。客人来到的次序可以随意安排。每个客人来到农场时，会把他喜欢的口味的小吃全部吃掉（如果有的话）。如果没有他喜欢的口味，那么他就会伤心地离开。

请问令客人如何排队，能使伤心的客人最少？输出最少的伤心的客人的数量。

思路：首先我们考虑一下没有任何人伤心的情况，如果把数据构建为图的话，相当于这些人的边构成了 一棵树 。如果有人伤心，那么一定是两个点都落在了一棵树上，也就是形成了环，不再是一棵树。可以用并查集维护连通性，看有多少人的两点落在了一棵树。

AC代码：http://oj.daimayuan.top/submission/309775

---

#811. 最小生成数

题意：$n-1$ 个点，从 $2$ 到 $n(2\le n\le 10^7)$，点 $a$ 与点 $b$ 的边权为 $\text{lcm}(a,b)$，求出 $n-1$ 个点的最小生成树。

思路：贪心。对于合数 $x$ ，我们将它连向它的最小质因子 $minp(x)$ ，这样花费为 $x$ 。连完之后，发现合数都连到了质数身上，我们还要让质数连通。容易知道 $2-3,2-5,2-7\cdots$ 比 $2-3,3-5,5-7\cdots$ 更优，因此所有质数连到 $2$ 身上。

AC代码：http://oj.daimayuan.top/submission/309654

---

#664. 数列

题意：给定 $d,p(1\le d,p\le 10^9)$ ，求满足以下性质的序列的个数，对 $p$ 取模。

• 非空，长度任意。$1\le a_1<a_2<\cdots <a_{n-1}<a_n\le d$ 。前缀异或序列 $c$ 递增。

思路：首先挖掘出来性质：序列的最高位 $1$ 必须是递增的，满足这个性质即可。

那么序列长度不会超过 $31$ 。我写的时候的方法：定义 $dp(i,j)$ 表示长度为 $i$ 且第 $i$ 个元素的最高位为 $j$ 的方案数。$dp(i,j)={\sum }_{k=0}^{j-1}(dp(i-1,k)\times count(j))$ ，$count(j)$ 表示最高位为 $j$ 的范围内的数字个数。时间复杂度 $O(n+{\log }^{3}n)$

但是题解给出的思路更简单。我们按照最高位分组，例如 $d=9:[1],[10,11],[100,101,110,111],[1000,1001]$ ，那么每一组都有 $count(j)+1$ 种选择（选某个或不选），乘法原理乘起来即可。时间复杂度 $O(n)$ 。

AC代码：http://oj.daimayuan.top/submission/309743

---

今天的题有点水。刷了一半多了，马上就能刷完了。