2018 Multi-University, Nowcoder Day 10

Problem A

Solved by kblack. 00:23 (+)

题意：随机修改范围内的 $x$ 为 $x+lowbit(x)$ 或 $x-lowbit(x)$，求区间和期望。

题解：假题。。。修改操作不改变期望。。。

Problem D

Solved by ultmaster. 01:20 (+1)

题意：有三种操作，区间加，对整个序列求前缀和，求区间和。第三种操作不会超过 500 个。

题解：考虑每次区间加对答案的贡献都是独立的，对每次询问，分别计算每个区间加对答案的贡献即可。区间加的贡献可以拆成一个 (l, +w) 的贡献和一个 (r, -w) 的贡献。对于每个 w，只要稍微推导一下很容易看到是一个组合数。

Problem E

Upsolved by zerol & ultmaster.

题意：考虑原问题是 $\sum_{i=1}^n a_i x_i \equiv 0 \pmod m$ 中 $x_i$ 的解的个数；现对 $m \in [1,M]$，回答 $B$ 的所有子集 $A$ 对应的解的个数的和。

题解：原问题答案是 $m^{n-1} \text{gcd} (a_1,a_2,\ldots,a_n,m)$。努力感受一下就好了。答案一定是 gcd 的倍数，且一定分布得非常均匀。。。

对于 $B$，预处理 $c_i$ 为 $B$ 中是 $i$ 的倍数的数有多少个。则对于特定的 $m$，以及 $m$ 的因数 $d$，假设 gcd 就是 $d$ 的倍数 ($kd$, $kd | m$)，所有的解的 "$m^{n-1}$" 之和就是 $((m+1)^{c_d}-1)/m$，记为 $w_d$。同时，记 $f_d$ 为 gcd「恰好」是 $d$ 的情况，则 $\displaystyle w_d = \sum_{kd | m} f_{kd}$，容斥一下可以得到 $\displaystyle f_d = \sum_{kd | m} \mu(k) w_{kd}$。由于最后对 $m$ 所有式是 $\displaystyle \sum_{d|m} d f_d$，代入 $f_d$ 使用 $\displaystyle \sum_{d|n} \mu(d) \frac{n}{d} = \phi(n)$ 化简后可以得到 $\sum_{d|m} \phi(d) w_d$。

其实做到容斥那一步就可以过了。复杂度是因子平方。

Problem F

Solved by kblack. 03:33 (+)

题意：给一张带权完全图，重建一张图，新图每个点代表原来一条边，每对代表有公共端点的边对的点对之间连一条原始两边权和的边，求新图的点两两最短路之和。

题解：首先拆解新图上的最短路，$(i,j)$ 的最短路可以拆成 $w_i+w_j+2\times min(dis(i_0, j_0), dis(i_0, j_1), dis(i_1, j_0), dis(i_1, j_1))$ 其中 $x_0$ 与 $x_1$ 代表边 $x$ 的两个端点，$dis(a, b)$ 代表原图上两点最短路。第一部分是原始边权和的常数倍，不管他了。第二部分可以先枚举一条 $(A, B)$，然后计算他与其他剩下的边的边权距离和，方法是 Floyd 预处理两点最短路，先计算出剩下所有点与当前边的最短路并排序，设排序后数组是 $C$，其他边相当于连接其他点的边，最短距离则是与当前边距离较小的的点的距离，因为完全图所有向更大方向的点是满的，直接 $\sum_{i=1}^{n} C_i(n-i)$。因为整个过程会计算每个边对两次，所以连两倍都省了。

Problem H

Upsolved by ultmaster.

题意：两只蚂蚁有分别从 $(1,0)$ 开始，在 $y=\frac{a}{b} x$ 和 $y = \frac{c}{d} x$ 两条直线下面爬。在下面爬的意思是如果能变成 $(x,y+1)$ 就变成它，不行就变成 $(x+1,y)$。求两只蚂蚁公共经过的点的个数。

题解：公共经过的点满足 $x \ge 1, y \ge 0, y \le \frac{a}{b} x, y > \frac{a}{b} (x-1) - 1, y \le \frac{c}{d} x, y > \frac{c}{d} (x-1) - 1$。假设 $\frac{a}{b} < \frac{c}{d}$，得到只剩 $y \le \frac{a}{b}, y > \frac{c}{d} (x-1) - 1, x \ge 1$ 这三个不等式。即求两条直线只能的整点个数。

类欧几里得（求直线下的整点个数）：$f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor​$: 当 $a \ge c​$ or $b \ge c​$ 时，$f(a,b,c,n)=(\frac{a}{c})n(n+1)/2+(\frac{b}{c})(n+1)+f(a \bmod c,b \bmod c,c,n)​$；否则 $f(a,b,c,n)=nm-f(c,c-b-1,a,m-1)​$，其中 $m = \lfloor \frac{an+b}{c} \rfloor$。

套用即可。注意处理边界，求 $m$ 的中间过程会爆 LL。把原点移到 $(1,-1)$（第二条直线的不动点）会比较好做一点。

Problem J

Solved by zerol | kblack. 00:27 (-1/+) | 01:25 (+)

题意：依次合并每个串，b 合入 a 的结果是 s，s 满足它的前缀是 a，且 b 是 s 的子序列，且最短。

题解：每插入一个字母，把所有以这个字母开头的字符串删除第一个字符。

zerol：出题人数据锅了，导致对一个签到调到怀疑人生。后来让 kblack 重写了一个过了，而本质的区别是 cin/scanf。