【7.29】Code Source - 【Arrangement】【Stone Game II】【Cow and Snacks】【Minimum Number of Spawns】【Sequence】

#746. 排列

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

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

思路：首先按照 $a_i$ 降序排列.当 $n\ge 3$ 时,Worst case all the buffs go to someone $a_i$ 的身上,Then this person's gain goes to someone else $a_j$ （不是前面的 $a_{i-1}$）身上,这样的话会使得 $a_{i-1},a_i$ 之间的差 $a_i-a_{i-1}$ 最大化.If the two numbers are still non-increasing after maximization,Then the two numbers will not contradict.对于每个 $i$ All can be judged.注意如果 $a$ 值相同的,要按照 $b$ 值升序排列,This maximizes the difference.

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

---

#738. 石子游戏 II

题意：共有 $n(1\le n\le 10^6)$ 堆石子,其中第 $i$ The heap initially contains $a_i(1\le a_i\le 10^9)$ 个石子.They take turns doing one of the following：

• Divide a pile of odd-numbered stones into two piles,Neither heap can be empty.

• Combine two piles of even-numbered stones into one pile.

The person who cannot do anything will lose the game.问先手必胜或必败.

思路：First discover some properties.Operates on odd heaps,The number of odd numbers is constant,The operation will have one more even number at a time;Operates on even heaps,Even numbers will only get smaller,The operation is one less even number at a time.Then it is easy to know that the situation where the number of even heaps is even is the winning state,Because in the end even heaps will only be odd.Pay attention to the situation that the special judge can't operate at first.

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

---

#807. Cow and Snacks

题意：

有编号从 $1$ 开始的 $n$ 种小吃,每种小吃只有一份.有 $m$ 个客人会来,每个客人有两种最喜欢的口味.The order in which guests arrive can be arranged at will.每个客人来到农场时,会把他喜欢的口味的小吃全部吃掉（如果有的话）.如果没有他喜欢的口味,那么他就会伤心地离开.

Ask the guests how to line up,能使伤心的客人最少？输出最少的伤心的客人的数量.

思路：First let's consider the situation in which no one is sad,If the data is structured as a graph,Equivalent to the edge of these people constituted 一棵树 .If someone is sad,Then both points must fall on a tree,That is, a ring is formed,No longer a tree.Connectivity can be maintained using unions,See how many people's two points fall on a tree.

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$ ,We connect it to its smallest prime factor $minp(x)$ ,This costs $x$ .连完之后,It is found that the composite numbers are connected to the prime numbers,We also have to make the prime numbers connected.容易知道 $2-3,2-5,2-7\cdots$ 比 $2-3,3-5,5-7\cdots$ 更优,So all prime numbers are connected $2$ 身上.

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

---

#664. 数列

题意：给定 $d,p(1\le d,p\le 10^9)$ ,Find the number of sequences that satisfy the following properties,对 $p$ 取模.

• 非空,长度任意.$1\le a_1<a_2<\cdots <a_{n-1}<a_n\le d$ .Prefix XOR sequence $c$ 递增.

思路：First dig out the nature：the highest bit of the sequence $1$ 必须是递增的,satisfy this property.

Then the sequence length will not exceed $31$ .The way I wrote it：定义 $dp(i,j)$ 表示长度为 $i$ 且第 $i$ The highest bit of each element is $j$ 的方案数.$dp(i,j)={\sum }_{k=0}^{j-1}(dp(i-1,k)\times count(j))$ ,$count(j)$ Indicates that the highest bit is $j$ The number of numbers in the range.时间复杂度 $O(n+{\log }^{3}n)$

But the idea given by the solution is simpler.We group by the highest order,例如 $d=9:[1],[10,11],[100,101,110,111],[1000,1001]$ ,Then each group has $count(j)+1$ 种选择（Choose one or not）,乘法原理乘起来即可.时间复杂度 $O(n)$ .

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

---

Today's question is a bit watery.Brushed more than half,It will be finished in no time.