牛客小白月赛63

七点十分左右看到有小白赛，感觉很适合我这样的小白，于是过来做做看。

---

A 子序列的权值最小值

感觉是个骗人的题

按位与的数的数量越多，结果肯定越小。

那么答案就是所有数 & 起来。

---

B 魔导师晨拥

一个模拟题。

根据题意直接模拟即可。

时间复杂度 $O(nm)$ 。

---

C GCPC总决赛

注意到 $n$ 的范围十分小，所以可以考虑直接暴力。

暴搜全排列即可。

时间复杂度 $O(n!)$ 。

---

D Ginger的大花环

一个思维题。

显然只要 $k$ 不为 $1$ ，那就有解。

一开始的思路错了，心想直接讨论奇偶性，ABAB 或者 ABABA 这样地填不就行了，其中 A 是最小， B 是次小。

后来发现不太行，例如 $n$ 为 $6$ 时，上面的策略为 ABABAB ，而显然 AABAAB 这样是更优的。

所以应该根据 $3$ 来讨论。

是 $3$ 的倍数就三个三个 AAB 这样的填。

模 $3$ 余 $1$ 就前面全是 AAB 最后一个 A 。

模 $3$ 余 $2$ 就前面全是 AAB 最后一个 AB 。

首先还要对 $k$ 个颜色排序。

如此即可 $O(k\log k)$ 解决本题。

---

看到 E 是个推式子，就摆了。

剩下俩题明天补吧，打游戏去~

懒比就这还想打ACM？

---

E 最值区间计数

首先贴一个十分巧妙的思维做法。

下面来说说数学做法。

假设 $1$ 所在的位置为 $i$ ， $n$ 所在的位置为 $j$ ，那么答案即为

$$A_2^2\times (n-2)!\times \sum_{i=1}^n \sum_{j=i+1}^ni(n-j+1)$$

化简

$$\begin{aligned} A_2^2\times (n-2)!\times \sum_{i=1}^n \sum_{j=i+1}^ni(n-j+1) &= A_2^2\times (n-2)!\times \sum_{i=1}^n i\sum_{j=i+1}^n(n-j+1)\\&= A_2^2\times (n-2)!\times \sum_{i=1}^n \dfrac{i(n-i+1)(n-i)}{2}\\&= (n-2)!\times \sum_{i=1}^n i(n-i)(n-i+1) \end{aligned}$$

至此其实已经可以 $O(n)$ 解决本题了。

但是如果追求更高效的做法的话可以接着化。

$$\begin{aligned} (n-2)!\times \sum_{i=1}^n i(n-i)(n-i+1) &= (n-2)!\times \sum_{i=1}^n\Big[(n^2+n)i-(2n+1)i^2+i^3\Big]\\&= (n-2)!\times \Big[n(n+1)\dfrac{n(n+1)}{2}-(2n+1)\dfrac{n(n+1)(2n+1)}{6}+\big[\dfrac{n(n+1)}{2}\big]^2\Big] \end{aligned}$$

如此即可。

但还需要 $O(n)$ 求阶乘，时间复杂度 $O(n)$ 。

---

F Ginger的数

贴个题解。