2019 Multi-University,Nowcoder Day 4

Problem A

Solved by Weaver_zhu. 01:43:34 (+)

Problem B

Upsolved by Weaver_zhu. (-5)

Problem C

Solved by Kilo_5723. 03:23:47 (+2)

题意：给定两个序列 $\{a_n\},\{b_n\}$，求出 $max_{1 \le l \le r \le n}(min(a_{l\dots r}) \cdot sum(b_{l \dots r}))$。

题解：考虑枚举 $a_i$ 作为区间最小值的所有情况。我们发现，如果从大到小将每个 $a_i$ 插入，那以 $a_i$ 作为区间最小值的区间 $[l,r]$ 肯定是包含 $a_i$ 的，$a_i$ 附近已经插入的连续点构成的段落。

考虑维护区间左/右端开始的和极大/极小的 $b_i$ 连续段落和以及区间和，我们发现，每次插入一个 $a_i$，只要查看 $i-1,i+1$ 是不是区间的左右端点，如果是，则将答案根据 $a_i$ 的正负加上 $a_i \cdot$ 左/右端开始的和极大/极小的 $b_i$ 连续段落和，并且将左右的区间和 $[i,i]$ 合并即可。合并的操作是 $O(1)$ 的。

Problem D

Solved by Xiejiadong. 01:23:59 (+)

题意：求最小数量的三的倍数的数，使得他们位或的结果是 $a$ 。

题解：大力分类讨论。我们可以发现二进制下，每一位模 $3$ 是 $1,2,1,2,\cdots $

我们不妨从总和下手：

• 总和是 $3$ 的倍数，直接输出；

• 总和是 $3$ 的倍数多 $1$ ，如果有 $1$ 去掉 $1$ 或者去掉两个 $2$ ，然后去掉的数考虑用 $1,1$ 或者 $2$ 去组成三的倍数，可以证明一定存在；

• 总和是 $3$ 的倍数多 $2$ ，如果有 $2$ 去掉 $2$ 或者去掉两个 $1$ ，然后去掉的数考虑用 $2,2$ 或者 $1$ 去组成三的倍数，可以证明一定存在。

所以发现其实最多只有两个数就能搞出来了。

Problem E

Solved by Kilo_5723. 04:02:11 (+1)

题意：求满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=x$ 的序列 ${a_n}$ 的数量，其中 ${\rm or}$ 是二进制下的或运算。

题解：对 $x$ 的二进制表达式中的 $1$ 进行分类：

二进制下每一位的权值 ${\rm} mod 3$ 只可能是 $1$ 或 $2$。我们令 $m$ 的二进制中权值为 $1$ 的 $1$ 的数量为 $cnt1(m)$，权值为 $2$ 的数量为 $cnt2(m)$。

我们考虑满足 $a_1\;{\rm or}\;a_2\;{\rm or}\dots{\rm or}\;a_n=y$，其中 $cnt1(y)\le cnt1(x),cnt2(y) \le cnt2(x)$ 的情况数，我们可以枚举 $cnt1(a_i)$ 和 $cnt2(a_i)$。

Problem F

Upsolved by Xiejiadong.

题意：要求支持两个操作：

• 对于区间 $[1,r]$ 类归并（本身是没有顺序的）

• 询问某一个位置上的数

题解：

可以发现 merge 函数的规律，我们可以把两个需要归并的数列分块，每一块的第一个数都是最大值，之后连续的 $\le $ 他的数都在同一块，因为一旦第一个数比下面一个数列小了，这一整块都会被放入最后的数列的连续位置。

于是就考虑维护这些块，对于右端点 $r$ 所在的块，我们可以直接裂为 $[x,r],[r+1,y]$ ，在处理完 $[1,r]$ 的归并以后再合并 $[1,r],[r+1,y]$ 即可。

而 $m$ 所在的块，左半边 $[x,m]$ 合成一块显然成立，右半边 $[m+1,y]$ ，需要按照上面的要求不断的裂开。

维护这个块的归并可以用 treap ，我们用权值来表示坐标，对于每一块的开头一定是连续一段的 max ，再维护一个区间 max 就可以了。

Problem G

Unsolved.

Problem H

Upsolved by Kilo_5723.

Problem I

Solved by Xiejiadong. 02:47:24 (+1)

题意：求本质不同的字符串个数，正串和反串相同的串只算一个。

题解：考虑一下就不难想到，正串、反串分别插入 SAM 算一算就好了。但是发现回文串会重复计数。

我们不妨假设有 $x$ 个回文串，有 $y$ 个串的正串和反串是不相同的，有 $z$ 个串的正串和反串是相同的（不包括回文串）。

于是有，正串插入 SAM 后本质不同的串有 $x+y+z$ ，反串也插入以后，本质不同的串有 $x+2y+z$ ，减一减就能得到 $y$ 。

本质不同的回文串个数，建一下 PAM ，结点个数就是了，于是 $z$ 也算出来了，答案显然就是 $x+y+ \frac{z}{2}$ 。

Problem J

Solved by Kilo_5723. 01:39:30 (+3)

Problem K

Solved by Xiejiadong. 00:19:37 (+)

题意：求字符串的子串中有多少 $300$ 的倍数。

题解：$300$ 的倍数就是末尾有两个 $0$ ，前面的数字和是 $3$ 的倍数就好了。

我们把当前数字后面跟着两个 $0$ 的位置称为有效的结束位置，把所有的有效结束位置的前缀和模 $3$ 扔进 map 。

然后枚举开头，判断有多少同值的有效结尾就好了。

还需要特判一个 $0$ 和两个连续 $0$ 的情况。