Difference between revisions of "2019 Multi-University,Nowcoder Day 8"

From EOJ Wiki
Jump to navigation Jump to search
Line 29: Line 29:
 
题解:对于一个 $2^k$ 的矩阵,考虑如何将其推广到 $2^{k+1}$ 的情况:
 
题解:对于一个 $2^k$ 的矩阵,考虑如何将其推广到 $2^{k+1}$ 的情况:
  
我们发现,对一个合法的矩阵 $A$,$-A$ 也肯定合法。
+
我们发现,对一个合法的矩阵 $A$,$-A$ 和 $\left( A \; A\right)$也肯定合法。
  
 
因此,对 $2^k \cdot 2^k$ 的合法矩阵 $A$,构造
 
因此,对 $2^k \cdot 2^k$ 的合法矩阵 $A$,构造

Revision as of 07:06, 11 August 2019

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 \cdot 2^k$,只含有 $1,-1$ 的矩阵,使得其任意两行点积为 $0$。

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

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

因此,对 $2^k \cdot 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 (+)

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)