【11.11】Codeforces 刷题

$\text{DP}$ ：

---

C. Insertion Sort

题意：

给出一个长度为$n(2\le n\le 5000)$的无序序列，序列为$0$到$n-1$的排列，现在需要你用冒泡排序来将序列排成从小到大有序的序列

你可以执行一次交换两个元素$i,j(i\ne j,1\le i,j\le n)$，使得执行冒泡排序时，交换相邻元素的次数最少

要你求出交换相邻元素的最少次数和满足交换相邻元素的次数最少的方案数

思路：易知冒泡排序交换次数为逆序对个数。我们暴力枚举需要交换的数对，如何 $O(1)$ 计算交换后的逆序对？ $n^2$ 预处理每个数向左、向右的各个长度区间有多少个数大于、小于这个数，即可实现。

AC代码：https://codeforces.com/contest/362/submission/180259922

---

D. Towers

题意：

有$n(1<=n<=5000)$座塔排在一条直线上，从左到右每个塔的高度分别为$h_i(1<=h_i<=100000)$.

每次操作你可以选择一座塔（假设是第$i$座），用吊车把它吊起来，然后放到与它相邻的一座塔上（可以是第$i-1$座也可以是第$i+1$座），这样，新塔的高度为两座塔的和，完成操作后，塔的总数减少一座。

问最少需要多少次操作可以使得所有的塔从左到右形成一个非递减序列。

思路：问题抽象为合并相邻元素，使得序列非递减，问合并的最小次数。

定义 $dp(i)$ 表示考虑前 $i$ 个元素的最小合并次数， $g(i)$ 表示对应的最小合并次数的最小末尾元素大小。容易知道合并次数越少，末尾元素大小越小，因此这样优化是可以的。

AC代码：https://codeforces.com/contest/229/submission/180413610

---

构造题 ${}^{\ast }1700{\sim }^{\ast }2000$ ：

---

C. Xenia and Weights

题意：

有 $1$ 到 $10$ 十种砝码，同种砝码要么永远无限个，要么就没有。现在放天平，满足：

1. 前后两次不能放置同种砝码

2. 第奇数次放左边，第偶数次放右边

3. 每次放的一边都要保证放完后这边的总重量比另一边重

给定一个数m，问能否用这些砝码在两个天平上共放置m个砝码。

思路：爆搜。不会算时间复杂度。

AC代码：https://codeforces.com/contest/339/submission/180415782

---

D. Phoenix and Science

题意：

小P觉得很无聊于是开始繁殖细菌。

在第一天，有一个质量为1的细菌。

接下来的每一天，会有若干个细菌分裂成两个（0$\le$分裂的细菌的数量$\le$当前的细菌数），两个细菌的质量皆为原来细菌的一半。

所有细菌分裂完之后每个细菌的质量增长1。

给出你一个整数$n$，如果没有方案能够在若干天后使得细菌质量的和等于$n$，输出-1，否则输出两行，第一行是最少花费的天数，第二行是每一天分裂的细菌的数量。

思路：把问题抽象一下。假设答案序列为 $a_1,a_2,\cdots a_m$ ，那么我们第 $i$ 天时有 $d_i=d_{i-1}+a_i,d_0=1$ 个细菌。 $a$ 是 $d$ 的等差序列，需构造 $d$ 序列。容易知道 $d$ 序列需要满足两个要求：

1. $d_{i-1}\le d_i\le 2\cdot d_{i-1},d_0=1$
2. ${\sum }_{i=0}^m{d}_i=n$

二次幂拆分即可使得长度最小。

AC代码：https://codeforces.com/contest/1348/submission/180422309

---

A. Extreme Subtraction

题意：

你有一个序列 $a$，你可以进行 $2$ 种操作：

• 选择前 $k$ 个数，将它们全部减 $1$
• 选择后 $k$ 个数，将它们全部减 $1$

$k$ 由你自己定，并且每次操作可以不同。
问是否可以把通过若干次操作整个序列变为全是 $0$ 的序列

本题多测，有 $t$ 组数据
$t\le 30000$，$\sum n\le 30000$，$a_i\le {10}^6$

思路：经典套路。略。

AC代码：https://codeforces.com/contest/1442/submission/180422993

---

D. Two Divisors

题意：

给定 $n$ 个数 $a_1,a_2,\dots ,a_n$。

对于每一个 $a_i$ 求出它的两个不为 $1$ 的约数 $d_1,d_2$ ，满足 $\gcd (d_1+d_2,a_i)=1$，或指出不存在这样的 $d_1,d_2$。

$n\le 5\times 10^5,2\le a_i\le 10^7$

思路：

对于 $a\%4=0,a\%4=2$ 的情况，可以构造一组 $d_1=2,d_2=奇数$ 的数对。

对于 $a\%4=1,a\%4=3$ ，即 $a$ 为奇数的情况，由打表可知，仅当我们将 $a$ 对 $a$ 的最小质因子除尽之后，剩下的这个因子才可能成为答案。

时间复杂度 $O(n\cdot {\log }_{2}w)$

AC代码：https://codeforces.com/contest/1366/submission/180426780