2019 Multi-University,Nowcoder Day 2

Problem A

Solved by Weaver_zhu && Kilo_5723. 01:36:01 (+2)

题意：给出一个环的大小，从0开始，每次随机向两个方向之一走一步，求走到m的期望

题解：起手蒙特卡洛就找到答案了，但是没看到前缀积（英语白学了，也没看到有人过，于是就扔了。还好有Kilo和机房后面队伍的欢呼声救场（逃

Problem B

Upsolved by Kilo_5723.

题意：一个人从 $1$ 出发，有均等的概率走 $1$ ~ $k$ 步，问经过一个点（可能是无穷远处）的概率。

题解：首先考虑无穷远处的情况，因为每一步和上一步间隔的期望是 $\frac{k-1}{2}$，所以经过的点占全部的点的比例应该是 $\frac{2}{k+1}$。

然后，很容易看出递推方程为 $dp_n=\sum_{i=n-k}^{n-1}dp_i$，问题就转变成了快速求线性齐次递推式的第 $n$ 项，模板题。

Problem C

Unsolved.

Problem D

Upsolved by Xiejiadong.

题意：求图中的权值 $k$ 小团。

分析：权值都是非负的，所以每次往团中新加一个点也是团的话，权值一定会增加。

新加一个团，我们可以用 bitset 优化变成 $O(1)$ 的，本来是团，一个点加入以后变成团，当且仅当这个点和当前团中的所有点都有边，拿状压结果 $\&$ 一下即可。

于是我们每次都考虑从当前最小团，新加结点形成新的团来维护。

把所有更新出来的团扔进优先队列就好了。

为了保证不重不漏，我们每次从一个已经加入的标号的后一个结点开始枚举新加入的结点。

Problem E

Upsolved by Kilo_5723.

题意：给定一宽度不超过 $10$ 的地图，每一步可以向上走或者左右移动，但不能回头走已经走过的格子，每次修改地图上一个方格的可通过/不可通过状态，查询从最下一行某一格到第一行某一格的路径条数。

题解：我们可以把从第 $i$ 行的每一格到第 $i+1$ 行每一格的路径条数看作一个乘法矩阵，那么问题就变成了维护 $n$ 个矩阵的乘积，每次修改一个矩阵。用线段树维护。

Problem F

Upsolved by Weaver_zhu. (-1)

题意：给出 $n^2$ 对关系，求把 $n$ 个人分成两类，只保留不同类之间的关系权值和最小的方案。

题解：灵性的暴搜，先加上 $n^2$ 对关系，然后去掉同类关系，求最小值。复杂度少了个 $n$ 还方便可行性剪枝。

Problem G

Upsolved by Kilo_5723.

题意：给出 $1000$ 条直线，求出其划分平面的所有封闭区域的面积，每次查询第 $k$ 大值。

题解：将每一条直线拆成两个方向的有向直线，对每一条直线 $l_i$ 和其他的所有直线的交点按在直线上的位置排序。

我们发现，交点的数量是偶数，且每一个位置都会有和当前有向直线叉积 $>0$ 和 $<0$ 的两条有向直线 $l_j,l_j'$ 产生的两个交点 $c_{(i,j)},c_{(i,j)}'$。我们将每一个 $c_{(i,j)}$ 和下一个交点 $c_{(i,k)}'$ 连边，这样每个封闭区域都会构成一个独立的环。对每一个环用叉积求出对应的面积，大小排序。

细节比较多，但代码量还好。

Problem H

Solved by Xiejiadong. 03:43:42 (+2)

题意：求全 $1$ 的次大矩阵面积。

题解：考虑最大矩阵如何做，对于每一行考虑这一行作为底的最大矩形面积。

这个就变成了经典的最大广告牌问题，用单调栈维护每个位置向左向右最多能拓展的长度，即可算出最的矩形。

对于次大的矩形，考虑裁掉最大矩形的四个角，在分别算最大的矩形面积，取这四个中的较大值即可。

脑子不动，暗示 Weaver_zhu 写了不知道多少个小时的三分，于是这题爆炸了。

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 04:37:15 (+6)

题意：一个长度为 $10^9$ 的区间，有 $10^6$ 段长度总和不超过 $10^7$ 的区间为 $1$，其他的全是 $0$，问有多少区间内和 $>0$。

题解：考虑将问题转换为前缀和，即有多少对 $l,r$ 满足 $sum_l<sum_r$。

根据题目，我们发现，因为有意义的 $sum_l$ 要满足存在 $sum_r>sum_l$ ，因此这样的 $sum_l$ 的数量级是不超过 $10^7$ 的。我们考虑对每一个 $sum$ 进行计数，动态维护当前所有满足 $sum_l<sum_{cur}$ 的 $l$ 的数量，我们还能发现一个性质：当 $sum_{cur}=0$ 时，之后的所有连续 $-1$ 都不会对答案产生新的贡献，而所有可能对 $cur$ 有贡献的 $sum$ 都分布在区间的左边和右边，数量总和的数量级同样不超过 $10^7$，每次计数即可。但在内存和时间的双重限制下，可能需要用自己的数据结构维护 $cnt$ 数组。