2019 Multi-University,Nowcoder Day 8

Problem A

Solved by Xiejiadong. 03:52:19 (+1)

题意：求极大全 $1$ 矩阵的个数，极大全 $1$ 矩阵的定义是不被其他的全 $1$ 矩阵包含的全 $1$ 矩阵。

题解：和求面积最大的全 $1$ 矩阵类似的。枚举矩阵的下边界，就变成了最大广告牌覆盖问题。

连续相同高度的的一段只需要处理其中一个，但也有特殊的，比如 $1\;2\;2\;1$ 的情况，两边的 $1$ 也认为是相同的。

也就是对应于同一个区间的相同高度只能处理一次。

保证当前行处理的，前面没有处理过，计数即可。

Problem B

Solved by Kilo_5723. 00:12:03 (+)

题意：给定一个数串 $\{a_n\}$，求其所有子串中不同数字的数量之和。

题解：考虑每种数字对串的贡献，发现除了所有在这种数字的相邻两个位置的间隔中的子串都能得到 $1$ 的贡献，所以对每种数字统计其间隔中的子串即可。

Problem C

Solved by Kilo_5723. 00:38:06 (+1)

题意：构造一个 $2^k \times 2^k$，只含有 $1,-1$ 的矩阵，使得其任意两行点积为 $0$。

题解：对于一个 $2^k$ 的方阵，考虑如何将其推广到 $2^{k+1}$ 的情况：

我们发现，对合法的矩阵 $A,B$，$-A$ 和 $\left( A \; B\right)$ 也肯定合法。

因此，对 $2^k \times 2^k$ 的合法矩阵 $A$，构造 $\left( \begin{array}\\ A&A\\ A&-A\\ \end{array} \right)$，可以证明它一定合法。

Problem D

Unsolved.

Problem E

Solved by Kilo_5723. 02:44:17 (+)

题意：给定一个无向图，第 $i$ 条边连接 $u_i,v_i$ 且可以让重量在 $[l_i,r_i]$ 中的人通过，求有多少种不同的重量的人可以从 $1$ 走到 $n$。

题解：将 $l_i,r_i$ 离散化后剩下了 $m$ 个关键点，我们可以看作一共有 $m$ 张图，每条边要加入 $[l_i,r_i]$ 中的图。

我们可以用线段树维护这些图，每条边插入时，我们把边加到线段树对应的节点上，这样一条边最多被加到 $log(m)$ 个节点上，而对于每一个叶节点，其对应的图就是其到根节点路径上每一个节点的所有边的集合。

因此，如果我们可以按序撤回加边的操作，我们从根节点开始做一遍 dfs 就能求出所有叶节点上 $1$ 到 $n$ 的连通性。可以用可回滚并查集维护图的连通性，到叶节点判断是否连通，在返回的时候将并查集回滚到进入当前结点之前的状态即可。

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 00:18:27 (+1)

题意：如果有三个连续的字母可以消掉，消掉以后前后相连，问最多能消除几次。

题解：如果连续的有一段字母，且个数不是 $3$ 的倍数，无论怎么消，都无法使得这一连续字母前后相连，也就是无论如何都会断掉，所以就可以贪心的消了。

用栈维护贪心消除即可。

开局智商下线，白送一发。

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Weaver_zhu. 04:58:42 (+8)

题意：踩石头过河，某些时刻某些石头不能踩，跳的距离至少为 $d$，求有多少种跳法

题解：组合数学，非法情况包括之前合法或非法的情况刚好走 $t_i$ 步到 $p_i$，或者是之前是非法的刚好不走 $t_i$ 步到 $p_i$。枚举第一个踩雷的情况就行了，这部分容斥减去之前踩过雷的情况。任意走 $t$ 步过 $p$ 距离可以用插板法公式直接搞出来。