• 欢迎光临~

# 2022牛客国庆集训派对day6 A(极大矩阵计数)

A-All-one Matrices_2022牛客国庆集训派对day6 (nowcoder.com)

## 思路

``````rep(j,1,m) while(L[j] > 1 and h[j] <= h[L[j] - 1] and (h[L[j]] and h[L[j] - 1])) L[j] = L[L[j] - 1];
dec(j,m,1) while(R[j] < m and h[j] <= h[R[j] + 1] and (h[R[j]] and h[R[j] + 1])) R[j] = R[R[j] + 1];
``````

``````#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3fll
#define ull unsigned long long
#define endl 'n'
// #define int long long
#define SZ(x) (int)x.size()
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define dec(i,n,a) for(int i = n;i >= a;i--)
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
using PII = array<int,2>;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{
int n,m; cin >> n >> m;
vector<vector<int>> a(n + 1,vector<int>(m + 1));
rep(i,1,n) rep(j,1,m) {
char t; cin >> t;
a[i][j] = t == '1';
if(a[i - 1][j] and a[i][j]) a[i][j] += a[i - 1][j];
}
vector<vector<int>> l(n + 1,vector<int>(m + 1)), r(n + 1,vector<int>(m + 1));

rep(i,1,n) {
auto &h = a[i];
auto &L = l[i], &R = r[i];
rep(j,1,m) L[j] = R[j] = j;
rep(j,1,m) while(L[j] > 1 and h[j] <= h[L[j] - 1] and (h[L[j]] and h[L[j] - 1])) L[j] = L[L[j] - 1];
dec(j,m,1) while(R[j] < m and h[j] <= h[R[j] + 1] and (h[R[j]] and h[R[j] + 1])) R[j] = R[R[j] + 1];
}
vector<array<int,4>> b;
rep(i,1,n) rep(j,1,m) if(a[i][j]) {
if(i < n and a[i + 1][j] and l[i][j] >= l[i + 1][j] and r[i][j] <= r[i + 1][j])
continue;
int x = i, y = l[i][j], z = i - a[i][j] + 1, w = r[i][j];
b.push_back({x,y,z,w});
}

sort(b.begin(),b.end());
b.erase(unique(b.begin(),b.end()),b.end());
cout << SZ(b);
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

//int T;cin>>T;
//while(T--)
solve();

return 0;
}
``````