2019牛客暑期多校训练营第八场题解(待更新)

本文包括2019牛客暑期多校训练营第八场的题面与题解。

A - String

题目描述

Gromah and LZR entered the great tomb, the first thing they see is a matrix of size $ n \times m $ , and the elements in the matrix are all $ 0 $ or $ 1 $ .

LZR finds a note board saying “An all-one matrix is defined as the matrix whose elements are all $ 1 $ , you should determine the number of all-one submatrices of the given matrix that are not completely included by any other all-one submatrices” .

Meanwhile, Gromah also finds a password lock, obviously the password should be the number mentioned in the note board!

Please help them determine the password and enter the next level.

输入描述

The first line contains two positive integers $ n,m $ denoting the size of given matrix.

Following $ n $ lines each contains a string with length $ m $ ,whose elements are allor $ 0 $ or $ 1 $ ,denoting the given matrix.

$ 1\le n,m \le 3000$

输出描述

Print a non-negative integer, denoting the answer.

示例1

输入

1
2
3
4
3 4
0111
1110
0101

输出

1
5

说明

The 5 matrices are $ (1,2)-(1,4), \; (1,2)-(2,3), \; (1,2)-(3,2), \; (2,1)-(2,3), \; (3,4)-(3,4)_{} $ .

题解

题意

定义完美全 $ 1 $ 矩阵为不存在包含该矩阵的全 $ 1 $ 矩阵的全 $ 1 $ 矩阵。

给定一个 $ 01 $ 矩阵,询问其中有多少完美全 $ 1 $ 矩阵。

解法

在最大全 $ 1 $ 矩形的模板上稍作修改,增加判重和去除无效答案的操作即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 3005
int l[N][N], r[N][N], f[N][N], n, m;
char c[N];
ll d[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", c + 1);
for (int j = 1; j <= m; j++)
f[i][j] = (c[j] == '1') ? f[i - 1][j] + 1 : 0;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) l[i][j] = r[i][j] = j;
f[i][0] = f[i][m + 1] = -1;
for (int j = 1; j <= m; j++)
while (f[i][j] <= f[i][l[i][j] - 1]) l[i][j] = l[i][l[i][j] - 1];
for (int j = m; j >= 1; j--)
while (f[i][j] <= f[i][r[i][j] + 1]) r[i][j] = r[i][r[i][j] + 1];
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 1; j <= m; j++)
if (f[i][j] && (i == n || f[i + 1][j] == 0 ||
(l[i][j] != l[i + 1][j] || r[i][j] != r[i + 1][j])))
d[++s] = (ll)l[i][j] << 30 | (ll)r[i][j] << 15 | (ll)f[i][j];
sort(d + 1, d + s + 1);
ans += unique(d + 1, d + s + 1) - d - 1;
}
printf("%d\n", ans);
return 0;
}

B - Beauty Values

题目描述

Gromah and LZR have entered the second level. There is a sequence $ a_1, a_2, \cdots, a_n $ on the wall.

There is also a note board saying “the beauty value of a sequence is the number of different elements in the sequence”.

LZR soon comes up with the password of this level, which is the sum of the beauty values of all successive subintervals of the sequence on the wall.

Please help them determine the password!

输入描述

The first line contains one positive integer $ n $ , denoting the length of the sequence.

The second line contains $ n $ positive integers $ a_1, a_2, \cdots, a_n $ , denoting the sequence.

$ 1 \le a_i \le n \le 10^5 $

输出描述

Print a non-negative integer in a single line, denoting the answer.

示例1

输入

1
2
4
1 2 1 3

输出

1
18

说明

The beauty values of subintervals $ [1,1], [2,2], [3,3], [4,4] $ are all $ 1 $ .

The beauty values of subintervals $ [1,2], [1,3], [2,3], [3,4] $ are all $ 2 $ .

The beauty values of subintervals $ [1,4], [2,4] $ are all $ 3 $ .

As a result, the sum of all beauty values are $ 1\times 4 + 2\times 4 + 3\times 2 = 18 $ .

题解

题意

给定一个序列,对于该序列的每一个子序列,定义它的权值为该子序列包含的元素个数。

询问你该序列的全部连续子序列的权值和。

解法

如果两个元素相同,那么这两个元素在同一区间时只对答案产生一次贡献。

那么如果这 $ n $ 个元素各不相同,显然答案为 $ \dfrac{n(n+1)(n+2)}{6} $ ,如果有相同元素,那么将相同元素的影响删去即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define ll long long
int last[N], n;
int main() {
scanf("%d", &n);
ll ans = (ll)n * (n + 1) * (n + 2) / 6, num = 0;
for (int i = 1, a; i <= n; ++i) {
scanf("%d", &a);
num += last[a], last[a] = i, ans -= num;
}
printf("%lld\n", ans);
return 0;
}