ACM-ICPC 2018 南京赛区网络预赛

62 阅读 0 评论 41 点赞

我是靠谱客的博主开放鸡翅，最近开发中收集的这篇文章主要介绍ACM-ICPC 2018 南京赛区网络预赛，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

B. The writing on the wall

数矩阵个数的题目。

先来看看常规的无小黑块限制的矩阵个数怎么数。

高度为1的话，很容易知道对于长度为L的矩阵一共有L+(L-1)+(L-2)+...+1个矩阵。那么对于高度为H的情况，只需要将高度从1遍历到H，但是注意到的是，对于特定长度的矩阵，高度每增加1，多出来的矩阵有h（当前高度值）个（详情见上图）。所以对于常规无黑块限制的数矩阵个数代码是：

 1 for(int i = 1; i <= H; i++)
//遍历高度
 2 {
 3
for(int j = 1; j <= L; j++)
//遍历长度
 4 
{
 5
for(int k = j; k > 0; k--)
 6 
{
 7
count += i;
 8 
}
 9 
}
10 }

但是这题有个小黑块限制，含有小黑块的矩阵不能算。这里就需要一个比较巧妙的处理了（感觉是有点巧妙，不好怎么描述，看图和代码就懂了。。。

 1 #include<iostream>
 2 using namespace std;
 3 int t, n, m, k;
 4 long long ans;
 5 int mapp[100010][110];
 6 int up[110];
 7 int main()
 8 {
 9
cin >> t;
10
for(int ca = 1; ca <= t; ca++)
11 
{
12
ans = 0;
13
cin >> n >> m >> k;
14
for(int i = 1; i <= n; i++)
15 
{
16
for(int j = 1; j <= m; j++)
17 
{
18
mapp[i][j] = 0;
19
up[j] = 0;
20 
}
21 
}
22
int x, y;
23
for(int i = 1; i <= k; i++)
24 
{
25
cin >> x >> y;
26
mapp[x][y] = 1;
//标记为黑块
27 
}
28
for(int i = 1; i <= n; i++)
29 
{
30
for(int j = 1; j <= m; j++)
31 
{
32
if(mapp[i][j])
33 
{
34
up[j] = i;
//标记该列黑块所处的最大行
35 
}
36 
}
37
for(int j = 1; j <= m; j++)
38 
{
39
long long minn = 0x3f3f3f3f;
40
for(int k = j; k > 0 ; k--)
//这里要从j到1，不能从1到j，不然minn的值有问题，会导致多加
41 
{
42
minn = min(minn, (long long)(i - up[k]));
43
//cout << "i:" << i << " " << "j:" << j << " " << "k:" << k << " " << "minn:" << minn << endl;
44
//cout << "ans += " << minn << endl;
45
ans += minn;
46
//cout << "ans==" << ans << endl;
47 
}
48 
}
49 
}
50
cout << "Case #" << ca << ": " << ans << endl;
51 
}
52
return 0;
53 }