Blackbird137

编辑于 2022-04-15 22:22

+ 关注

牛客挑战赛 59 题解精

A

首先发现所有小木桩之间独立，所以我们考虑往大木桩之间插入小木桩，找到最大的位置，然后全部***去就行了。

设插入的位置前面有 $x$ 个大木桩，那么答案就是 $x(a-x)-x$ 即 $-x^2+ax-x$ ，可得在 $x=\frac{a}{2}$ 时答案最大，时间复杂度 $\text{O}(T)$ 。

代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51832865

B

考虑 dp 出每个人有多少种情况会获胜。

设 $dp1_{i,j}$ 表示前 $i$ 个人，最后胜利的人一直出 $j$ 的方案数。

设 $dp2_{i,j}$ 表示后 $i$ 个人，只出 $j$ 的人能胜利的方案数。

转移比较显然，可以参考代码，时间复杂度 $\text{O}(n)$ 。

代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51832872

C

偶数的情况构造 $b_i=a_i \oplus a_{i+1} (1 \le i \le n-1)$ 。

奇数的情况构造 $b_i=a_i \oplus 2^{\inf}$ 。

两种情况答案显然都是在 $b$ 中选择一个子集使得异或和最大，线性基即可。

当然如果你会其中一个做法，那么另一个可以直接通过钦定一个必选然后到对应的线性基去找最大，不过由于 STL 的 bitset 没有内置比较符号，所以可能需要手写 bitset。

还有一种更容易实现的做法是把奇数情况 $b$ 的线性基搞出来，然后偶数时的答案就是在忽略第 $\inf$ 位的时候在这个线性基里查询最大，读者可以想想为什么是正确的。

时间复杂度 $\text{O}(\frac{n^3}{\omega})$ 。

代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51832874

D

十分抱歉放了个无聊卡常题在这个位置，可能交换 D,E 或 D,F 都能带来更好的体验。

首先考虑不带修，直接通过维护几个 $\mathtt{o,r,z,or,rz}$ 的前缀和算贡献。

如果带修，那么考虑先把操作离线，把插入后的字符串求出来，倒着求答案。这样插入就变成了删除，而每次删除只要把要删除的位置清空即可，可以直接树状数组维护。

关于如何求出插入后的字符串：由于插入的字符相同，所以可以维护每个字符后面插入了多少个 $\mathtt{o}$ ，插入位置的可以通过树状数组上倍增找到。

关于如何删除：如果有一段连续的 $\mathtt{o}$ ，那么这段中的每个 $\mathtt{o}$ 对答案的贡献显然都是相等的。所以删除的时候并不需要知道要删除具体哪个 $\mathtt{o}$ ，只要知道要删除的 $\mathtt{o}$ 在哪个连续的 $\mathtt{o}$ 中，然后删除这个段中的任意一个 $\mathtt{o}$ 即可。

关于如何找到插入后的区间下标：同样可以树状数组上倍增解决。

时间复杂度： $\text{O}(n\log n)$ ，std只跑了 1.3s 左右。

因为时限不能卡得太死加上牛客评测机波动比较大，好像把线段树维护答案放过去了（

代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51832879

E

先将序列 $a$ 排序，假设我们先固定一共分了多少组。

我们把一组划分成三部分，设这组作为中位数的位置称为 $B$ ，那么把小于 $a_{B}$ 的位置称为 $A$ ，大于 $a_B$ 的位置成为 $C$ 。

通过简单的观察可以发现，最优方案中最小的 $B$ 一定大于最大的 $A$ ，否则一定可以通过交换两者使答案不劣。

又因为 $B$ 整体上越在数组后部答案越大，所以我们希望最小的 $B$ 尽可能大，所以我们枚举最小 $B$ 的位置，然后可以 $\text{O}(1)$ 来check是否存在一种方案满足枚举的位置，随后问题就变成了一个子问题，可以继续贪心解决。

这样如果固定了分多少组，那么可以 $\text{O}(n)$ 求最大值，总时间复杂度 $\text{O}(n^2)$

考虑上述贪心选择的中位数的位置是分成两段的，前面一段和后面一段的下标都是一个等差数列。

显然这两段的分界点是单调的，所以可以通过双指针+前缀和优化到 $\text{O}(n)$ ，算上排序的复杂度为 $\text{O}(n\log n)$ 。

代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51832886

F

同样先将数列排序，然后考虑 dp，设 $dp_{i,j,k,l}$ 表示前 $i$ 个位置，已经分了 $j$ 组，前面有 $k$ 个数还没分进某一组，后面还需要 $l$ 个数分进中位数在前面的某一组。

然后有转移：

$dp_{i,j,k,l} \leftarrow dp_{i-1,j,k-1,l}$

$dp_{i,j,k,l} \leftarrow dp_{i-1,j,k,l+1}$

$dp_{i,j,k,l} \leftarrow dp_{i-1,j-1,k+p,l-p} + a_i \oplus b_{p\times 2+1}\ (\left\lceil\frac{l-1}{2}\right\rceil \le p \le \left\lfloor\frac{r-1}{2}\right\rfloor)$

时间复杂度 $\text{O}(n^5)$ ，由于有用状态数很少，所以可以通过。

当然可以用二分平均数的方式优化到 $\text{O}(n^4\log a)$ ，但是由于直接做的常数太小，后者根本没法卡掉前者，所以就都放过了。

代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51832890

G

考虑转化限制条件，显然等价于排列数值上相邻的数在排列上的相对位置不变。

比如 $[3,1,2,4]$ 这个排列中 $(3,4)$ 这对相邻数值的相对位置就不可能通过操作发生改变，即 $3$ 一定在 $4$ 左边。

那么我们考虑排列的置换 $p'$ ，显然 $p$ 与 $p'$ 构成双射，所以我们考虑在 $p$ 上的限制对 $p'$ 有什么影响，也就是问题变成给定 $n-1$ 个限制，第 $i$ 个限制形如 $p'_{i} < p'_{i+1}$ 或 $p'_{i} > p'_{i+1}$ ，求有多少个满足条件的排列。