Znzryb's Blog
0%

D. I Love 1543（在层状矩阵中顺时针数“1543”出现了几次）

Posted on Edited on

思路讲解

模拟题，没什么好说的

我的写法是学的题解的写法，我觉得挺好的

化曲为直，是个好做法。

AC代码

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
#include <iostream>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e3)+10;
ll n,T,m;
char maze[N][N];
// 呃，题目还是很清楚的
// 就是模拟嘛，谁怕谁
// 唉，我怕了，这模拟不给我数据我咋调
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll ans=0;
		cin>>n>>m;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				cin>>maze[i][j];
			}
		}
		ll ceng=min(n,m)/2;
		for(int i=1;i<=ceng;++i){
			ll cnt=0;string s;
			// 最右边            最下边
			ll upm=m-(i-1),upn=n-(i-1);
			for(int j=i;j<=upm;++j) s+=maze[i][j];
			for(int j=i+1;j<=upn;++j) s+=maze[j][upm];
			for(int j=upm-1;j>=i;--j) s+=maze[upn][j];
			for(int j=upn-1;j>=i+1;--j) s+=maze[j][i];
			ll len=s.size();
			for(int j=0;j<len;++j)
				if(s[j]=='1' && s[(j+1)%len]=='5' && s[(j+2)%len]=='4' && s[(j+3)%len]=='3')
					++ans;
		}
		cout<<ans<<endl;
	}
	return 0;
}
// WA on 2 https://codeforces.com/contest/2036/submission/293979229
// AC https://codeforces.com/contest/2036/submission/293986402

心路历程（WA，TLE，MLE……）

说实话，我也实在不太清楚哪里错了

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e3)+10;
ll n,T,m;
char maze[N][N];
const char ob[6]={'1','5','4','3'};
// 呃，题目还是很清楚的
// 就是模拟嘛，谁怕谁
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll ans=0;
		cin>>n>>m;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				cin>>maze[i][j];
			}
		}
		ll ceng=min(n,m)/2;
		for(int i=1;i<=ceng;++i){
			ll cnt=0;
			// 最右边            最下边
			ll upm=m-(i-1),upn=n-(i-1);
			for(int j=i;j<=upm;++j){
				if(maze[i][j]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			for(int j=i+1;j<=upn;++j){
				if(maze[j][upm]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			for(int j=upm-1;j>=i;--j){
				if(maze[upn][j]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			for(int j=upn-1;j>=i;--j){
				if(maze[j][i]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			ll step=1;
			// 这下面是为了避免样例7那种情况搞的
			if(cnt<2)
				continue;
			for(int j=i+1;j<=upm;++j){
				if(step>=3)
					break;
				++step;
				if(maze[i][j]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			for(int j=i+1;j<=upn;++j){
				if(step>=3)
					break;
				++step;
				if(maze[j][upm]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
// WA on 2 https://codeforces.com/contest/2036/submission/293979229