题目大意
题目背景
Felix 的生日派对上，一张 H×W 的矩形披萨被客人吃掉了一些部分，剩下的部分由若干 1×1 的正方形单元格组成。
题目描述
给出一个 H×W 的网格，其中字符 # 表示剩下的披萨块，. 表示已经被吃掉（空缺）的部分。
你需要将所有剩下的披萨块（#）划分成若干个边长为 k 的正方形区域。
要求：
-
每个划分出的正方形必须完全由 # 组成。
-
所有 # 必须被恰好覆盖一次（不能重叠，不能遗漏）。
-
只能沿网格线切割。
-
划分出的所有正方形边长必须相等。
求满足上述条件的最大边长 k。
输入格式
第一行包含两个整数 H 和 W (1≤H,W≤2500)，表示网格的高度和宽度。
接下来 H 行，每行包含一个长度为 W 的字符串，由 # 和 . 组成。
保证输入中至少包含一个 #。
输出格式
输出一个整数，表示最大的可行边长 k。
样例 1
1
2
3
4
5
6
7
8
9
| Input
4 7
####...
####.##
.######
.####..
Output
2
|
样例 1 解释
对于第一个样例，最大边长为 2。
剩下的披萨块可以被划分为 5 个 2×2 的正方形，其左上角坐标 (r,c) 分别为：(0,0),(0,2),(1,5),(2,1),(2,3)。
所有 # 均被这 5 个正方形不重不漏地覆盖。
这道题说白了其实意思很简单，就是井号的地方代表就是披萨，然后你要把披萨切成正方形的，大小相同的块，问这些切出来的正方形块的最大边长是多少？
样例 2
1
2
3
4
5
6
7
8
| Input
3 5
#####
#####
###..
Output
1
|
样例 3
1
2
3
4
5
6
7
8
| Input
3 5
.##..
#####
##.##
Output
1
|
样例 4
1
2
3
4
5
6
7
8
9
10
| Input
5 13
....###......
....###..###.
.######..###.
.###.....###.
.###.........
Output
3
|
思路讲解
首先呢我们还是要想到啊，就是我我们首先还是要想到一个算法，能够判定在此边长下能否切割出这样子的东西啊。
这个算法的时间复杂度就是 O(H×W) 就行，可以了。
这算法其实很简单，也不需要前缀和啊什么之类的。其实只需要一个贪心即可。就说白了，最上面的那个点，最上面最左边的那个点，或者你倒过来做最最左边最上面的那个点。你不放一个正方形在上面，就不以这个正方形，不放一个正方形在这里的话，没有正方形可以覆盖这个点，所以这里必须放一个正方形。就这个披萨点。必须放一个正方形。那么你放了这，放下去这个正正方形以后，你就判断一下这个正方形会不会和其他你放的正方形重叠，啊什么之类的就行了。说白了就是一个贪心。
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
| auto check=[&](ll len) -> bool {
++tim;
for (ll i=1;i<=N;++i) {
for (ll j=1;j<=M;++j) {
if (vis[i][j]>=tim) continue;
if (maze[i][j]=='#') {
if (i+len-1>N) {
return false;
}
if (j+len-1>M) {
return false;
}
for (ll x=i;x<i+len;++x) {
for (ll y=j;y<j+len;++y) {
if (maze[x][y]!='#') {
return false;
}
if (vis[x][y]>=tim) {
return false;
}
vis[x][y]=tim;
}
}
}
}
}
return true;
};
|
现在问题就来到什么呢？就是我不可能枚举2500次是吧？枚举2500次就超了。那我怎么样枚举的次数少一点？我其实就加一个非常简单的一个判定即可。它 cnt 的因数数量肯定是根号下 cnt，也就是数量级是2500。又因为 i 乘 i 才是 才能组成 cnt 的一个因数，所以实际上 i 只有50的量级。
1
2
3
4
5
6
7
8
9
10
| for (ll i=min(N,M);i>=2;--i) {
if (cnt%(i*i)!=0) {
continue;
}
if (check(i)) {
cout<<i<<"\n";
return;
}
}
cout<<1<<"\n";
|
AC代码
AC
https://codeforces.com/gym/106129/submission/362620886
源代码
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
vector<ll> minp,primes;
void sieve(ll n){
minp.assign(n+5,0);
for(int i=2;i<=n;++i){
if(minp[i]==0){
minp[i]=i;
primes.push_back(i);
}
for(auto p:primes){
if(i*p>n){
break;
}
minp[i*p]=p;
if(p==minp[i]){
break;
}
}
}
}
void Solve() {
ll N,M;
cin >> N >> M;
vector<vector<char>> maze(N+2,vector<char>(M+2));
ll cnt=0;
for (ll x=1;x<=N;++x) {
for (ll y=1;y<=M;++y) {
cin>>maze[x][y];
if (maze[x][y]=='#') {
++cnt;
}
}
}
int tim=0;
vector<vector<int>> vis(N+2,vector<int>(M+2));
auto check=[&](ll len) -> bool {
++tim;
for (ll i=1;i<=N;++i) {
for (ll j=1;j<=M;++j) {
if (vis[i][j]>=tim) continue;
if (maze[i][j]=='#') {
if (i+len-1>N) {
return false;
}
if (j+len-1>M) {
return false;
}
for (ll x=i;x<i+len;++x) {
for (ll y=j;y<j+len;++y) {
if (maze[x][y]!='#') {
return false;
}
if (vis[x][y]>=tim) {
return false;
}
vis[x][y]=tim;
}
}
}
}
}
return true;
};
for (ll i=min(N,M);i>=2;--i) {
if (cnt%(i*i)!=0) {
continue;
}
if (check(i)) {
cout<<i<<"\n";
return;
}
}
cout<<1<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf);
#endif
sieve(2600);
Solve();
return 0;
}
|
心路历程（WA，TLE，MLE……）
WA
https://qoj.ac/submission/2030500
出问题的代码
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
void Solve() {
ll N,M;
cin >> N >> M;
vector<vector<char>> maze(N+2,vector<char>(M+2));
for (ll x=1;x<=N;++x) {
for (ll y=1;y<=M;++y) {
cin>>maze[x][y];
}
}
int tim=0;
vector<vector<int>> vis(N+2,vector<int>(M+2));
auto check=[&](ll len) -> bool {
++tim;
for (ll i=1;i<=N;++i) {
for (ll j=1;j<=M;++j) {
if (vis[i][j]>=tim) continue;
if (maze[i][j]=='#') {
if (i+len-1>N) {
return false;
}
if (j+len-1>M) {
return false;
}
for (ll x=i;x<i+len;++x) {
for (ll y=j;y<j+len;++y) {
if (maze[x][y]!='#') {
return false;
}
if (vis[x][y]>=tim) {
return false;
}
vis[x][y]=tim;
}
}
}
}
}
return true;
};
ll ans=1;
for (ll len=2;len*len<=max(N,M);++len) {
if (check(len)) {
ans*=len;
}
}
ans=min(ans,min(N,M));
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf);
#endif
Solve();
return 0;
}
|
上面这个代码的问题是出在哪里呢？首先第一啊，就是这个因数啊，你直接乘起来，它去找这个最大，其实是不大对的。那么在 m 比较小的情况下，不如直接倒序遍历 m ，然后检验这个 m 的所有的素因数。是否全部都在我们可以凑出来的素因数集合之中。
不过后面我们发现更加大的问题，就是它这个道题目，它其实并不符合说有这个因数，然后我们乘，然后它就能够合在一起，即只要素因数合法，那么所凑出来的合数也合法，这其实是不对的，它们乘起来的合数是不一定合法的。其实很简单吧，就是边长为2和边长为3是没有反例的（即满足边长为2和满足边长为3，在不限制这个长度的情况下，应该是有满足边长为6的解决方案）。这个状况，让我们造成了一些错觉，以为说这个其实是可以乘的。但实际上不是这样子的。**满足边长为2，那一定满足边长为4吗？**一定满足边长为8吗？你看它这个2，它可以乘，它，但是它乘上去它就不一定对了。