- 最大矩阵
- 最大正方形
- 最大子矩阵和
最大矩阵
Code - 存到了队列里，可以求第k大
1/**
2 * author: Akvicor
3 * created: 2019-07-21 21-00-00
4**/
5
6#include <bits/stdc++.h>
7
8using namespace std;
9
10#ifdef DEBUG
11#define FAST_IO 17
12#else
13#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
14#define endl '\n'
15#endif
16
17#define rep(i, n) for(int i = 0; i < (n); ++i)
18#define reep(i, n) for(int i = 0; i <= (n); ++i)
19#define lop(i, a, n) for(int i = a; i < (n); ++i)
20#define loop(i, a, n) for(int i = a; i <= (n); ++i)
21#define prec(x) fixed << setprecision(x)
22#define ms(s, n) memset(s, n, sizeof(s))
23#define all(v) (v).begin(), (v).end()
24#define sz(x) ((int)(x).size())
25#define pb(x) push_back(x)
26#define mp(x, y) make_pair(x, y)
27#define fi first
28#define se second
29#define MOD(x) const int MOD = (int)x
30#define MAXN(x) const int MAXN = (int)x + 10
31
32typedef long long LL;
33typedef unsigned long long ULL;
34typedef pair<int, int> PII;
35typedef vector<int> VI;
36typedef vector<PII> VII;
37
38namespace SOL{
39
40const double EPS = 1e-6;
41const double PI = acos(-1.0);
42const int INF = 0x3f3f3f3f;
43const LL LINF = 0x7f7f7f7f7f7f7f7f;
44
45/** >------- Akvicor's Solution -------< **/
46
47MOD(1e9+7);
48MAXN(1010);
49
50int mp[MAXN][MAXN], l[MAXN], r[MAXN];
51priority_queue <int> ans;
52
53void solve(){
54 FAST_IO;
55
56 int n, m;
57 cin >> n >> m;
58 loop(i, 1, n) loop(j, 1, m){
59 char c; cin >> c;
60 mp[i][j] = (c == '1');
61 }
62 loop(i, 2, n) loop(j, 1, m)
63 if(mp[i-1][j] && mp[i][j]) mp[i][j] += mp[i-1][j];
64 loop(i, 1, n){
65 set<pair<int, PII> > S;
66 stack<int> A, B;
67 loop(j, 1, m){
68 while(!A.empty() && mp[i][A.top()] >= mp[i][j]) A.pop();
69 l[j] = A.size() ? A.top()+1 : 1;
70 A.push(j);
71 }
72 for(int j = m; j >= 1; --j){
73 while(!B.empty() && mp[i][B.top()] >= mp[i][j]) B.pop();
74 r[j] = B.size() ? B.top() - 1 : m;
75 B.push(j);
76 }
77 loop(j, 1, m){
78 if(mp[i][j]){
79 pair<int, PII> temp = mp(r[j], mp(l[j], mp[i][j]));
80 pair<int ,PII> temp2;
81 if(!S.count(temp)){
82 ans.push((r[j] - l[j]+1)*mp[i][j]);
83 S.insert(temp);
84 }
85 if(r[j] - l[j]){
86 temp = mp(r[j], mp(l[j]+1, mp[i][j]));
87 temp2 = mp(r[j]-1, mp(l[j], mp[i][j]));
88 if(!S.count(temp)){
89 ans.push((r[j] - l[j]) * mp[i][j]);
90 S.insert(temp);
91 }else if(S.count(temp2)){
92 ans.push((r[j]-l[j])*mp[i][j]);
93 S.insert(temp2);
94 }
95 }
96 }
97 }
98 }
99 if(ans.size()<2) ans.push(0);
100 ans.pop();
101 cout << ans.top() << endl;
102
103}
104
105/** >----------------------------------< **/
106
107}
108
109int main(){
110
111#ifdef DEBUG
112 int DEBUGCNT = 0;
113 clock_t DEBUGstart, DEBUGfinish;
114 double DEBUGduration;
115 cout << ">------- Akvicor's Solution -------<" << endl;
116 while (true) {
117 DEBUGstart = clock();
118#endif
119
120 SOL::solve();
121
122#ifdef DEBUG
123 DEBUGfinish = clock();
124 DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
125 cout << " --> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <--" << endl;
126 if (cin.eof()) break;
127 ++DEBUGCNT;
128 }
129 cout << ">----------------------------------<" << endl;
130#endif
131
132 return 0;
133}
Code - 速度更快，但只能求前几大
1/**
2 * author: Akvicor
3 * created: 2019-07-23 08-52-07
4**/
5
6#include <bits/stdc++.h>
7
8using namespace std;
9
10#ifdef DEBUG
11#define FAST_IO 17
12#else
13#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
14#define endl '\n'
15#endif
16
17#define rep(i, n) for(int i = 0; i < (n); ++i)
18#define reep(i, n) for(int i = 0; i <= (n); ++i)
19#define lop(i, a, n) for(int i = a; i < (n); ++i)
20#define loop(i, a, n) for(int i = a; i <= (n); ++i)
21#define per(i, a, n) for(int i = a; i >= (n); --i)
22#define prec(x) fixed << setprecision(x)
23#define ms(s, n) memset(s, n, sizeof(s))
24#define all(v) (v).begin(), (v).end()
25#define sz(x) ((int)(x).size())
26#define mp(x, y) make_pair(x, y)
27#define pb(x) push_back(x)
28#define fi first
29#define se second
30#define MOD(x) const int MOD = (int)x
31#define MAXN(x) const int MAXN = (int)x + 10
32
33typedef long long LL;
34typedef unsigned long long ULL;
35typedef pair<int, int> PII;
36typedef vector<int> VI;
37typedef vector<PII> VII;
38
39namespace SOL{
40
41const double EPS = 1e-6;
42const double PI = acos(-1.0);
43const int INF = 0x3f3f3f3f;
44const LL LINF = 0x7f7f7f7f7f7f7f7f;
45
46/** >------- Akvicor's Solution -------< **/
47
48MOD(1e9+7);
49MAXN(1e3);
50
51int n, m;
52string s;
53int high[MAXN];
54
55int mxx, mxx2;
56int stkhg[MAXN], stkpos[MAXN];
57int cnt;
58
59void solve(){
60 FAST_IO;
61
62 cin >> n >> m;
63 high[m+1] = 0;
64 loop(i, 1, n){
65 cout << ">-- Line #" << i << " --<" << endl;
66 cin >> s;
67 loop(j, 1, m) high[j] = s[j-1]=='0' ? 0 : high[j]+1;
68#ifdef DEBUG
69 cout << "str: " << s << endl;
70 cout << "high: ";
71 loop(j, 1, m+1) cout << high[j] << ' ';
72 cout << endl;
73#endif
74 stkhg[0] = stkpos[0] = cnt = 0;
75 loop(j, 1, m+1){
76 if(high[j] > stkhg[cnt]){ // 如果比上一格高，说明可以构成矩形，就push进栈
77 stkhg[++cnt] = high[j];
78 stkpos[cnt] = j;
79 }else if(high[j] < stkhg[cnt]){ // 如果比上一格矮，
80 // 那么高度等于上一格高度的矩形已经完全找出来了，
81 // 当前格比上一格矮，不能参与构成上个矩形
82 while(high[j] < stkhg[cnt]){ // 将栈中高于当前位置的高度全部出栈
83 int area = (j-stkpos[cnt]) * stkhg[cnt]; // 当前位置坐标-比当前格高的格的坐标就是宽度
84 // 更新前两大矩形
85 if(area >= mxx){
86 mxx2 = mxx;
87 mxx = area;
88 mxx2 = max(mxx2, max(area-stkhg[cnt], area-(j-stkpos[j])));
89 }else if(area > mxx2){
90 mxx2 = area;
91 }
92 --cnt;
93 }
94 if(stkhg[cnt] != high[j]){
95 stkhg[++cnt] = high[j];
96 }
97 }
98#ifdef DEBUG
99 cout << j << " stkhg: ";
100 loop(j, 1, m+1) cout << stkhg[j] << ' ';
101 cout << endl;
102 cout << j << " stkpos: ";
103 loop(j, 1, m+1) cout << stkpos[j] << ' ';
104 cout << endl;
105 cout << "mxx: " << mxx << " mxx2: " << mxx2 << endl;
106#endif
107 }
108 }
109 cout << mxx2 << endl;
110
111}
112
113/** >----------------------------------< **/
114
115}
116
117int main(){
118
119#ifdef DEBUG
120 int DEBUGCNT = 0;
121 clock_t DEBUGstart, DEBUGfinish;
122 double DEBUGduration;
123 cout << endl << ">------- Akvicor's Solution -------<" << endl << endl;
124 while (DEBUGCNT < 70) {
125 cout << ">---> Test: #" << DEBUGCNT << " <---<" << endl;
126 DEBUGstart = clock();
127#endif
128
129 SOL::solve();
130
131#ifdef DEBUG
132 DEBUGfinish = clock();
133 DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
134 cout << ">---> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <---<" << endl << endl;
135 if (cin.eof()) break;
136 if (!cin.good()) break;
137 if (cin.fail()) break;
138 if (cin.bad()) break;
139 ++DEBUGCNT;
140 }
141 cout << ">----------------------------------<" << endl << endl;
142#endif
143
144 return 0;
145}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。