2019 Multi-University,Nowcoder Day 1

Problem A

Solved by Kilo_5723. 00:20:52 (+)

题意：给定两个 $1$ ~ $n$ 的排列 $\{a_i\},\{b_i\}$，求最大的 $m$，使得 $RMQ(a,l,r)=RMQ(b,l,r)$ 对所有 $1 \le l \le r \le m$ 成立，其中 $RMQ(c,l,r)$ 是 $c_l,c_{l+1},\dots,c_r$ 中最小元素的下标。

题解：考虑对任意 $m$ 判断是否满足条件。我们发现，若 $RMQ(a,1,m) \neq RMQ(b,1,m)$ 则肯定不满足条件，否则对所有 $l \le m \le r$，$RMQ(a,l,r)=RMQ(b,l,r)$。此时对 $(l,m-1)$ 和 $(m+1,r)$ 递归求解就可以判断 $1~m$ 是否满足条件。

因此，对 $m$ 二分求解，就可以找到最大的 $m$。

Problem B

Upsolved by Kilo_5723. (-1)

题意：求 $\frac{1}{\pi}\int_0^{\infty}\frac{1}{\prod_{i=1}^n(a_i^2+x^2)}{\rm d}x$。

题解：可以把分式的连乘转换成分式的和，再分别积分。

我们发现，$\prod_{i=1}^n(a_i^2+x^2)=\sum_{i=1}^{n}\frac{1}{(x^2+a_i^2)\prod_{j=1}^n(a_j^2-a_i^2)(j!=i)}$。

利用此性质，将乘积的积分转换成积分的和，易解。

Problem C

Solved by Kilo_5723. 04:12:29 (+1)

题意：给定一个 $n$ 维空间中的点 $(a_1,a_2,\dots,a_n)$，求一个点 $(p_1,p_2,\dots,p_n)(\sum_{i=1}^n p_i=1,a_i>=0)$，使得两点距离最短。

题解：显然，若没有 $p_i>=0$ 的限制，使得每一个 $a_i=p_i$ 相等即可。但加上限制之后，为了最小化影响，应该对 $>0$ 的 $p_i$ 均等的减少一定量的值补给 $<0$ 的缺口。

一种实现方法是：对 $p_i$ 进行排序，统计 $<0$ 的 $p_i$ 的和。从小到大遍历 $>0$ 的 $p_i$：

如果 $p_i$ 小于将当前的缺口平均分摊给每一个正数的均摊值，说明 $p_i$ 要被减到 $0$，将缺口减去 $p_i$。

否则，对于当前的 $p_i$ 以及之后的每一个 $p_i$，均摊缺口。

由于要求输出分数，运算过程中分子分母的大小可能超过 long long 能存储的范围，但答案没有超出范围，用 __int128 存储即可。

Problem D

Upsolved by Weaver_zhu.

前置芝士：FWT异或卷积

借鉴博客地址：

https://blog.csdn.net/qq_37136305/article/details/81606170

https://www.cnblogs.com/cjyyb/p/9065615.html

https://www.cnblogs.com/Dup4/p/11211043.html

题意：首先考虑转化式子：$count(x) =\frac{1}{2^m} \times \sum\limits_{i=0}^{n-1}\prod\limits_{j=0}^{m-1}(1-(-1)^{a_{i,j}\&x})$

定义：$i$ 与 $j$ 的奇偶性 $|i\&j|$ 表示 $i\&j$ 二进制表示中1的个数的奇偶性

引理：仅考虑二进制位的奇偶性，有 $|a\&b| + |a\&c| = |a \& (b \oplus c)|, count(x) =\frac{1}{2^m} \times \sum\limits_{i=0}^{n-1}\prod\limits_{j=0}^{m-1}(1-(-1)^{|a_{i,j}\&x|})$

再考虑二项展开：$=\frac{1}{2^m} \times\sum\limits_{i=0}^{n-1}\sum\limits_{T \subseteq S}(-1)^{|\bigoplus\limits_{a_j\in T}a_j \& x|}$

根据FWT的性质，$F(i) = \sum\limits_{|j\&i|=0}{a_j} - \sum\limits_{|j\&i|=1}{a_j}$，证明显然，点积乘起来正好是定义的结果。

然后发现这不就是我们要求的吗，考虑对一个数组 $a_i$ 做 FWT 正变换，$FWT[i] =\sum\limits_{|j\&i|=0}{a_j} - \sum\limits_{|j\&i|=1}{a_j}= \sum\limits_{j}(-1)^{|j\& i|} = count(i) \times 2^m$

有多个数列，加起来就好了，没有冲突。

于是我们要算出来的数列是，各个 $\{a[i]\}$ 枚举子集，然后把贡献加到 $F$ 数组，最后对 $F$ 做 FWT，再算出来。枚举子集，设异或值为 $x$，$F[x] = F[x] + (-1)^{|S|}$

Problem E

Solved by Kilo_5723. 02:25:19 (+)

题意：求长度为 $2(n+m)$ 的 $01$ 序列，使得其中恰好能取出不一定连续的 $n$ 个 $01$ 和 $m$ 个 $10$。

题解：先考虑给定一个序列，如何判断其是否能取出 $n$ 个 $01$ 和 $m$ 个 $10$。我们发现，可以贪心的将新读到的数作为端口 $0-$ 或 $1-$，直到对应的端口数量已经满足要求，需要和对应的另一种端口 $1-$ 和 $0-$ 匹配成 $10$ 和 $01$。如果过程中另一种端口的数量不足，则给定序列不满足性质。

根据这种方法，我们可以将加入字符看作是在平面上移动的过程。横纵坐标分别为 $0,1$ 的数量，初始位置为 $(0,0)$，我们要向右或向上走（即加入 $0$ 或 $1$），到达 $(n+m,n+m)$。根据上面的判断方式，需要满足的限制条件为 $-n \le x-y \le m$。将问题转换为在只能向右或向上走，且横纵坐标 $x,y$ 始终满足 $-n \le x-y \le m$ 的情况下，$(0,0)$ 到 $(n+m,n+m)$ 的路径条数。 $O(n^2)$ dp 求解。

Problem F

Solved by Kilo_5723. 00:50:00 (+)

题意：在一个三角形内随便散点，一次散点的价值是被分出来的最大三角形的面积，求随机散点的期望价值。

题解：小范围随机散点，蒙特卡洛找规律。

可以发现答案是 $22$ 倍的三角形面积。

Problem G

Upsolved Xiejiadong && Kilo_5723.

题意：求字符串中有多少本质不同的串，能单射的串也认为是同构的。

题解：参考 SA 求不同子串的方法，对所有的后缀排序以后，总的子串个数减去相邻 LCP 的长度。

同理可以推广到这道题目。

能单射的串也认为是同构的，我们可以通过 $last$ 串相同来处理。 $last[i]$ 的值是在 $i$ 位前，与 $i$ 位字母相同的最近距离。

从后往前推一遍 $last$ ，每次往前走一位，最多改变一个位置的值。

处理 $last$ 的 LCP 可以用二分判断前缀 hash 是否相同。排序也是同样求出 LCP 以后，比较 LCP 的后一位大小。

需要维护历史版本的区间 hash ，一开始写了主席树，这样的话排序需要 $O(nlog^3n)$ ， TLE 。

排序可以去掉一个 log ，用可持久化分块数组实现，这样每次查询历史版本区间 hash 就变成 $O(1)$ 。

Problem H

Upsolved by Weaver_zhu.

题意：给一个数列，求所有异或和为0的子集的大小之和。

题解：考虑包含每一个数的子集有多少个，即考虑每一个数的贡献（实在看不懂题解写的线性期望之类的= =，但我觉得指的就是这个）。选取某个数，然后就要考虑剩下的数是否能把他异或成0。于是考虑线性基，非基肯定是可以被基异或成0的，于是答案加上 $2^{n-r-1}*(n-r)$，表示含有任何一个非基数，再加上其他非基数的任意组合，都能最后被基异或成0。然后再考虑包含基数的，同样是枚举每个数，非基中的数再组成一个线性基，再加上基数中的其他数组成一个新的线性基。如果新的线性基包含当前数，答案加上 $2^{n-pcnt-1}$，表示含有这个基数的子集个数，此时的新的线性基包含除了现在这个枚举的基数之外的所有数的异或可能。第一部分 $O(64n)$，第二部分 $O(64*64*64)$。

Problem I

Upsolved by Xiejiadong.

题意：平面上有一些点，求一条折线分割这些点，折线的左上部分的价值取点的 $a$ ，折线的右下部分的价值取 $b$ ，求最大的价值。

题解：不妨假设折线式贴合右下部分的点的。即折线上的点都属于 $b$ 部分。

考虑 dp ，枚举每一个点位于折线上时的最大价值，在做 dp 的过程中顺便加入每个点，更新所有的状态。

对于一个点 $(i,j)$ ，只能从 $(x,y)(x<i,y<j)$ 转移到它，而加入这个点以后，之后的点如果位于他的上方，他的贡献为 $a$ ，如果位于他的下方，他的贡献为 $b$ 。

这部分直接用线段树维护即可。

Problem J

Solved by Xiejiadong. 00:07:33 (+)

题意：比较两个分数的大小。

题解：直接比较会爆 long long ，开 __int128 就好了。