A-F题解

altalt

A 牛牛的串串

模拟

按题意模拟即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=79078845

B 牛牛的合数

数论、分类讨论

若 $x$ 为奇数，那么 $x$ 的二进制下最后一位一定为 1 ，将 $x$ 异或 1 后，一定会得到二进制下最后一位为 0 的数字，也就是偶数。并且这个数一定等于 $x-1$ 。

若 $x$ 为偶数，那么 $x$ 的二进制下最后一位一定为 0 ，将 $x$ 异或 2 后，一定会得到二进制下最后一位为 0 的数字，也就是偶数。并且这个数一定等于 $x \pm 2$ 。

因此，归纳一下，若 $x>4$ ，按上述方式一定可行。若 $x = 4$ ，可以发现 $4 \oplus 2 = 6$ ，是个合数。若 $x < 4$ ，手推一下会发现一定无解。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=79079108

C 牛牛的排列

构造

首先有一个重要的结论： $gcd(x, x + 1) = 1$ 。

那么，如果 $n$ 为奇数，直接输出 $1, 2, 3, ..., n$ 就可以了，总和为 $n-1$ ，是偶数。

再引入两个结论： $gcd(1, x) = 1, gcd(2, 2 \times y) = 2$ 。

根据这两个结论，若 $n$ 为偶数，我们可以构造出 $n, 2, 3, 4, ..., n - 1, 1$ 。 2 到 $n - 1$ 中共有 $n - 2$ 个数，由于 $n$ 是偶数， $n-2$ 也是偶数，因此中间部分总和为 $n - 3$ ，根据上面引入的两个结论， $gcd(n, 2) = 2, gcd(n - 1, 1) = 1$ ，最终总和为 $(n - 3) + 2 + 1 = n$ ，是偶数。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=79079399

D 牛牛的子序列

模拟

首先可以将一个数组写成另一种形式，例如：将 $\{1, 2, 3, 1\}$ 写成 $\{1(1),2(1),3(1),1(1) \}$ ，将 $\{1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 1, 1\}$ 写成 $\{1(2),2(4),3(4),1(2) \}$ 。

为了方便描述，我们定义改写后的数组中括号外的数字为**“元素”，括号内的数字为元素的“指数”**，且后续的数组都是被改写后的。

若是 $a$ 数组可以变成 $b$ 数组，必须满足数组长度相同，并且每一个位置元素都相同，且 $a$ 数组中的指数小于等于 $b$ 数组中的指数。

一次操作最多可以使得 $a$ 数组中的每一个指数 $x$ 变成 $[x, x \times 2]$ 之间的任意一个数字，因此我们在不超过 $b$ 数组指数的情况下贪心考虑变成最大值。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=79080572

E 牛牛的约数

暴力

写了个看上去是 $O(n^2)$ 的代码，过了。

查表后发现复杂度是一个常数，大概是 $2.7 \times 10 ^ 8$ 。

大致思路就是，将数组去重并排序，然后对于每一个数，从它往前暴力，找到了就break，否则就是无解。

更新：时间复杂度应该是 $O(n \times logV)$ 左右，其中 $V$ 为值域。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=79081697

F 牛牛的三角形

DP、组合数学

首先考虑怎么样的数组无法构造三角形，一个很容易想到的数组是： $\{1, 2, 3, 5, 8, 13, ...\}$ ，可以发现是一个斐波那契数列，那就意味着在 1500 内，这个数组的数字数量不会太多。

考虑DP， dp[i][j][k] 表示数组中有 i 个数，次大的为 j ，最大的为 k 的方案数。
l = j + k
dp[i][j][k] -> dp[i + 1][k][l, l + 1, l + 2, ..., n]

暴力转移是 $O(n^3)$ 。

观察可以发现，这实际上是一个区间加，可以用数据结构（如线段树）优化成 $O(n^2 \times logn)$ 。

再观察可以发现，我们只需要查询一次，因此可以使用差分进一步优化 $O(n^2)$ 。

第一维（也就是数字个数）取 20 以内即可。

最后的时间复杂度为 $O(n^2 \times 20)$ 。