计蒜客NOIP模拟赛-1 Day1 T1(旋转+前缀和)

题目链接
原图要求一个分值最大的斜正方形,斜着不好弄,那就倒过来。
把矩阵旋转$45^{\circ}$,然后就可以直接水平求正方形了。
具体怎么旋转看我的另一个博文。这里注意旋转以后的数组有些地方不可用,可能会敲到棋盘外,也有可能敲到边上,在输入的时候用一个数组记录一下就好,注意数组比较大,不要MLE了.
顺便附上使用了前缀和优化的暴力,考试时拿了90分,不能相信…

正解:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<ctime>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 2000 + 5;
int n, k, ma[4005][4005], s[4005][4005], vi[4005][4005];
void clean() {
ms(s, 0), ms(vi, 0);
}
void solve() {
clean();
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
int T = i + j - 1, P = n - i + j;
scanf("%d", &ma[T][P]);
vi[T][P] = true;//避免打到不是棋盘的地方
}
}
for (int i=0;i<=n*2;i++) {
for (int j=0;j<=n*2;j++) {
s[i][j] = ma[i][j];
if (i - 1 >= 0) s[i][j] += s[i - 1][j];
if (j - 1 >= 0) s[i][j] += s[i][j - 1];
if (i - 1 >= 0 && j - 1 >= 0) s[i][j] -= s[i - 1][j - 1];
}
}
int ans = 0;
for (int i=0;i<=n*2;i++) {
for (int j=0;j<=n*2;j++) {
if (!vi[i][j]) continue; //避免打到不是棋盘的地方
int tot = 0;
tot = s[i][j];
if (i - 2 * k + 1 >= 0) tot -= s[i - 2 * k + 1][j];
if (j - 2 * k + 1 >= 0) tot -= s[i][j - 2 * k + 1];
if (i - 2 * k + 1 >= 0 && j - 2 * k + 1 >= 0) tot += s[i - 2 * k + 1][j - 2 * k + 1];
ans = max(ans, tot);
}
}
printf("%d\n", ans);
}
int main() {
scanf("%d%d", &n ,&k), solve();
return 0;
}

暴力:

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
36
37
38
39
40
41
42
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<ctime>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 2000 + 5;
int n, k, ma[MAXN][MAXN], s[MAXN][MAXN];
void clean() {
ms(s, 0);
}
void solve() {
clean();
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
scanf("%d", &ma[i][j]);
s[i][j] = s[i][j-1] + ma[i][j];
}
}
int ans = 0;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
int tot = 0;
for (int l=0;l<k&&i+l<=n&&i-l>0;l++) {
if (i + l == i - l) tot += s[i + l][min(j+k-1-l, n)] - s[i + l][max(j-k+1+l, 1) - 1], ts++; else {
tot += s[i + l][min(j+k-1-l, n)] - s[i + l][max(j-k+1+l, 1) - 1];
tot += s[i - l][min(j+k-1-l, n)] - s[i - l][max(j-k+1+l, 1) - 1];
}
}
ans = max(ans, tot);
}
}
printf("%d\n", ans);
}
int main() {
scanf("%d%d", &n ,&k), solve();
return 0;
}

------ 本文结束 ------