2019-09-17 19:22 已编辑算法工程师

关注

【题解】牛客练习赛52

牛客练习赛52 题解

A. 数数

送温暖题。

只需要掌握基础的交换求和号的知识就能解决这题。

交换 $\sum$ 的原则：\bf{交换前后多项式的每一项不变。

那么便可以顺理成章的推出来了：

$\sum_{i=1}^n\sum_{j=1}^nij=\sum_{i=1}^ni\sum_{j=1}^nj=\sum_{i=1}^ni\frac{n(n+1)}2=\left(\frac{n(n+1)}2\right)^2$

$\prod$ 的交换也是一样的。类比上面的做法不难推出。和 $\sum$ 比较不同的地方就是变化的地方多是指数。

$\prod_{i=1}^n\prod_{j=1}^nij=\prod_{i=1}^ni\prod_{j=1}^nj=\prod_{i=1}^ni\times(n!)=(n!)^{2n}$

~~其实手动展开一下或者打个表也很容易就能看出来的。~~

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

B.Galahad

解法1：codesonic

将询问离线，维护一个初始全为 $0$ 的序列 $\{b\}$ ，从 $a_1$ 遍历到 $a_n$ ，对于每个 $a_i$ ，记录下上一次出现的位置 $last[a_i]$ ，遍历到 $a_i$ 时，对 $b$ 序列的 $last[a_i]$ 到 $i$ 进行区间加 $a_i$ ，并且处理询问的右端点为 $i$ 的询问，设该询问的左端点为 $l$ ，即输出当前 $b_l$ 的值，树状数组即可解决。

解法2：wjyyy

同样将询问离线，按右端点从小到大排序。建立树状数组 $c$ ，维护贡献的前缀和。

由于权值 $a_i$ 满足 $1\le a_i\le500\ 000$ ，所以不用离散化，直接维护 $lst[i]$ 表示元素 $i$ 上一次出现的位置。

设当前更新到的位置为 $t$ 。如果 $a_i$ 没有出现过，即 $lst[a_i]=0$ ，则不产生影响；否则把树状数组上的 $lst[a_i]$ 贡献变为 $0$ ，在 $t$ 位置贡献 $+1$ 。

增大 $t$ ，依次更新。直到 $t$ 抵达当前询问的右端点 $r$ 。

时间复杂度 $O(n\log n)$

C.烹饪

写这道题的人应该都见过并用过 gcd 这个东西。

介绍一个与 gcd 有关的一个定理，裴蜀定理，内容就是：形如 $ax+by=c$ 的不定方程有解的条件就是 $\gcd(a, b)\mid c$ 。

这个定理推广到任意多个未知数也是成立的。

考虑题目求的是什么

挑选出 $m$ 种食材 $(1\le m\le n)$ ，让他们能够组合出任意正整数的美味值。

其实就是一个 $a_1\times x_1 + a_2 \times x_2 + \ldots + a_m \times x_m =$ 任意正整数的不定方程！

任意正整数都有的 gcd 是 1。

所以这个问题就变成了挑选若干个数，让他们的 gcd 为 1。

这个问题可以用 $dp$ 来解决。

设 $f[i][j]$ 表示前 $i$ 个数的 gcd 为 $j$ 的方案数。

不难推出转移方程：

$f[i][\gcd(j, a[i])] = f[i - 1][\gcd(j, a[i])] + f[i - 1][j]$

最终 $f[n][1]$ 就是答案。

D.粉丝群

拿到这个题可以先考虑手动构造，但是发现有很多都是不满足的。所以可以打表。

打表发现当 $n$ 为偶数时，仅有无序集 $\{1, 1,\ldots, n + 1\}$ 满足条件，按照字典序排列分别是 $n + 1$ 在第 $n$ 个位置， $n + 1$ 在第 $n-1$ 个位置， $\ldots$ ， $n + 1$ 在第 $1$ 个位置，共 $n$ 组。因为是奇数 $(n-1)$ 个 $1$ 和 $1$ 个 $n + 1$ 的异或，第二问可以直接输出 $(n + 1)\ xor\ 1\ =\ n$ 。

当 $n$ 为奇数时，有上述无序集以及长为 $n$ 的集合 $\{2, 2,\ldots, 2\}$ 满足条件。因此共 $n + 1$ 组答案，而这个集合是比有序集 $\{n + 1, 1, \ldots , 1\}$ 小的，所以排在字典序第 $n$ 小。

特判 $n\ =\ 1$ 的情况下只有 1 组 $\{2\}$ 满足条件（这组数据是 wjyyy 后来加的）

下证有且仅有这两种情况。

设 $\{a\}$ 是一个满足条件的数列，对于 $1 \le i \le n$ ，考虑下面的 $n + 1$ 个数

$a_i, a_i+1, a_i + a_{i+1}, \ldots, a_i + a_{i+1} + \ldots + a_{i+n-1}.(1)$

其中 $a_{n+j} = a_j$ 。

因为 $\{a\}$ 不能分成和相等的两部分数，那么其中肯定没有若干个数的和为 $n$ 。

因此，数列 (1) 中除了 $a_i$ 和 $a_{i+1}$ ，其余任意两项模 $n$ 意义下不同余（项数多的减去项数少的，所得差等于 $n$ ），而数列 (1) 中有 $n + 1$ 个数，其中必定有两个数模 $n$ 同余，所以 $a_i \equiv a_{i+1}\ (mod\ n)$ ，这个对任意 $1 \le i \le n$ 都成立。

所以有

$a_1 \equiv a_2 \equiv a_3 \equiv \ldots \equiv a_n$

又因为他们的和是 $2n$ ，所以 $a_1 \equiv a_2 \equiv a_3 \equiv \ldots \equiv a_n \equiv 1$ 或 $2\ (mod\ n)$ 。

所以，只有数列 $\{1, 1, 1, 1, \ldots, n + 1\}$ 和 $\{2, 2, 2, 2, 2, \ldots, 2\}$ （ $n$ 为奇数）满足要求。

E.魔法少女

简单 DP。
因为 $c_i$ 一定在 $a_i$ 和 $b_i$ 之内，所以只要第 1 列和第 $m$ 列向下走能走到同一列，那么全部物体都会落到同一列（所以魔法装置可以认为是一个“合并器”）。

那么只要第 1 列和第 $m$ 列能走到同一列里，就收集成功了，那么，除了最后一个魔法装置，其他的魔法装置都不可能同时对不同的两列产生作用。

考虑 DP，设 $fl[i]$ ，为rainy从第一列向下走到第 $i$ 列的花费， $fr[i]$ 为rainy从第 $m$ 列走到第 $i$ 列的花费，其中 $fl[1] = 0, fr[m] = 0$ , 其他都为 inf，每一行就把 $fl[a_i]$ 到 $fl[b_i]$ 中的最小值加上 $d[i]$ ，来更新 $fl[c_i]$ 。 $fr$ 同理。