题目链接:https://ac.nowcoder.com/acm/contest/882/H

题目大意

  给定一个 n * m 的 01 矩阵,求其中第二大的子矩阵,子矩阵元素必须全部为 1。输出其大小。

分析1(前缀和,O(NM2))

  这题数据没那么强,所以用前缀和暴力枚举也能过。

代码如下

 #include <bits/stdc++.h>
using namespace std; #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i)
#define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define LOWBIT(x) ((x)&(-x)) #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define UNIQUE(x) x.erase(unique(x.begin(), x.end()), x.end())
#define REMOVE(x, c) x.erase(remove(x.begin(), x.end(), c), x.end()); // ?? x ?????? c
#define TOLOWER(x) transform(x.begin(), x.end(), x.begin(),::tolower);
#define TOUPPER(x) transform(x.begin(), x.end(), x.begin(),::toupper); #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
#define msM(a) memset(a,-1,sizeof(a)) #define MP make_pair
#define PB push_back
#define ft first
#define sd second template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
in >> p.first >> p.second;
return in;
} template<typename T>
istream &operator>>(istream &in, vector<T> &v) {
for (auto &x: v)
in >> x;
return in;
} template<typename T>
ostream &operator<<(ostream &out, vector<T> &v) {
Rep(i, v.size()) out << v[i] << " \n"[i == v.size()];
return out;
} template<typename T1, typename T2>
ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {
out << "[" << p.first << ", " << p.second << "]" << "\n";
return out;
} inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} template<class T>
inline string toString(T x) {
ostringstream sout;
sout << x;
return sout.str();
} inline int toInt(string s) {
int v;
istringstream sin(s);
sin >> v;
return v;
} //min <= aim <= max
template<typename T>
inline bool BETWEEN(const T aim, const T min, const T max) {
return min <= aim && aim <= max;
} typedef long long LL;
typedef unsigned long long uLL;
typedef pair< double, double > PDD;
typedef pair< int, int > PII;
typedef pair< int, PII > PIPII;
typedef pair< string, int > PSI;
typedef pair< int, PSI > PIPSI;
typedef set< int > SI;
typedef set< PII > SPII;
typedef vector< int > VI;
typedef vector< double > VD;
typedef vector< VI > VVI;
typedef vector< SI > VSI;
typedef vector< PII > VPII;
typedef map< int, int > MII;
typedef map< int, string > MIS;
typedef map< int, PII > MIPII;
typedef map< PII, int > MPIII;
typedef map< string, int > MSI;
typedef map< string, string > MSS;
typedef map< PII, string > MPIIS;
typedef map< PII, PII > MPIIPII;
typedef multimap< int, int > MMII;
typedef multimap< string, int > MMSI;
//typedef unordered_map< int, int > uMII;
typedef pair< LL, LL > PLL;
typedef vector< LL > VL;
typedef vector< VL > VVL;
typedef priority_queue< int > PQIMax;
typedef priority_queue< int, VI, greater< int > > PQIMin;
const double EPS = 1e-;
const LL inf = 0x7fffffff;
const LL infLL = 0x7fffffffffffffffLL;
const LL mod = 1e9 + ;
const int maxN = 1e3 + ;
const LL ONE = ;
const LL evenBits = 0xaaaaaaaaaaaaaaaa;
const LL oddBits = 0x5555555555555555; int N, M, preSumY[maxN][maxN];
int Fmax, Smax; int main(){
//freopen("MyOutput.txt","w",stdout);
//freopen("input.txt","r",stdin);
//INIT();
scanf("%d%d", &N, &M);
For(i, , N) {
For(j, , M) {
scanf("%1d", &preSumY[i][j]);
preSumY[i][j] += preSumY[i - ][j] * preSumY[i][j];
}
} For(x, , N) {
For(y, , M) {
// 枚举以(x, y)为右下角所能形成的所有矩形
int len = preSumY[x][y], width = ; while(len) {
int area = len * width; if(area > Fmax) {
Smax = Fmax;
Fmax = area;
}
else if(area > Smax) Smax = area; len = min(len, preSumY[x][y - width]);
++width;
}
}
} printf("%d\n", Smax);
return ;
}

分析2(单调栈,O(NM))

  这是对分析1的优化,每一行都可以看成是直方图的底边,然后从底边开始向上连续最多的 1 代表柱子的高度。于是问题转化为求直方图最大面积。
  而求直方图最大面积可以用到单调栈(可以求一个数的左右最近小的位置)。详细见:https://www.cnblogs.com/linkstar/p/6139668.html

代码如下

 #include <bits/stdc++.h>
using namespace std; #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i)
#define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define LOWBIT(x) ((x)&(-x)) #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define UNIQUE(x) x.erase(unique(x.begin(), x.end()), x.end())
#define REMOVE(x, c) x.erase(remove(x.begin(), x.end(), c), x.end()); // ?? x ?????? c
#define TOLOWER(x) transform(x.begin(), x.end(), x.begin(),::tolower);
#define TOUPPER(x) transform(x.begin(), x.end(), x.begin(),::toupper); #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
#define msM(a) memset(a,-1,sizeof(a)) #define MP make_pair
#define PB push_back
#define ft first
#define sd second template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
in >> p.first >> p.second;
return in;
} template<typename T>
istream &operator>>(istream &in, vector<T> &v) {
for (auto &x: v)
in >> x;
return in;
} template<typename T>
ostream &operator<<(ostream &out, vector<T> &v) {
Rep(i, v.size()) out << v[i] << " \n"[i == v.size()];
return out;
} template<typename T1, typename T2>
ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {
out << "[" << p.first << ", " << p.second << "]" << "\n";
return out;
} inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} template<class T>
inline string toString(T x) {
ostringstream sout;
sout << x;
return sout.str();
} inline int toInt(string s) {
int v;
istringstream sin(s);
sin >> v;
return v;
} //min <= aim <= max
template<typename T>
inline bool BETWEEN(const T aim, const T min, const T max) {
return min <= aim && aim <= max;
} typedef long long LL;
typedef unsigned long long uLL;
typedef pair< double, double > PDD;
typedef pair< int, int > PII;
typedef pair< int, PII > PIPII;
typedef pair< string, int > PSI;
typedef pair< int, PSI > PIPSI;
typedef set< int > SI;
typedef set< PII > SPII;
typedef vector< int > VI;
typedef vector< double > VD;
typedef vector< VI > VVI;
typedef vector< SI > VSI;
typedef vector< PII > VPII;
typedef map< int, int > MII;
typedef map< int, string > MIS;
typedef map< int, PII > MIPII;
typedef map< PII, int > MPIII;
typedef map< string, int > MSI;
typedef map< string, string > MSS;
typedef map< PII, string > MPIIS;
typedef map< PII, PII > MPIIPII;
typedef multimap< int, int > MMII;
typedef multimap< string, int > MMSI;
//typedef unordered_map< int, int > uMII;
typedef pair< LL, LL > PLL;
typedef vector< LL > VL;
typedef vector< VL > VVL;
typedef priority_queue< int > PQIMax;
typedef priority_queue< int, VI, greater< int > > PQIMin;
const double EPS = 1e-;
const LL inf = 0x7fffffff;
const LL infLL = 0x7fffffffffffffffLL;
const LL mod = 1e9 + ;
const int maxN = 1e3 + ;
const LL ONE = ;
const LL evenBits = 0xaaaaaaaaaaaaaaaa;
const LL oddBits = 0x5555555555555555; int N, M, board[maxN][maxN];
int Fmax, Smax;
stack< PII > st; void update(int area) {
if(area < ) return;
if(area > Fmax) {
Smax = Fmax;
Fmax = area;
}
else if(area > Smax) Smax = area;
} int main(){
//freopen("MyOutput.txt","w",stdout);
//freopen("input.txt","r",stdin);
//INIT();
scanf("%d%d", &N, &M);
For(i, , N) {
while(!st.empty()) st.pop(); board[i][] = -; // 哨兵
For(j, , M) {
scanf("%1d", &board[i][j]);
if(board[i][j]) board[i][j] += board[i - ][j];
}
board[i][M + ] = -; // 哨兵 For(j, , M + ) {
while(!st.empty() && st.top().ft > board[i][j]) {
PII tmp = st.top(); st.pop(); int w = j - tmp.sd + tmp.sd - st.top().sd - ;
update(tmp.ft * w);
update(tmp.ft * (w - ));
update((tmp.ft - ) * w);
}
st.push(PII(board[i][j], j));
}
} printf("%d\n", Smax);
return ;
}

最新文章

  1. app慢的可能情况需要优化
  2. iOS--页面跳转(UITableView)
  3. 旋转轮子 UIActivityIndicatorView
  4. IOS网络第二天 - 01-基本的HTTP请求
  5. Neo4j图数据库管理系统开发笔记之三:构建安全的RMI Service(Server)
  6. 范式(Oracle)
  7. js中的String数据类型
  8. The first time
  9. Cracking the coding interview--Q1.1
  10. mysql中,执行delete语句时出现Lock wait timeout exceeded问题
  11. 普通IT和文艺IT工程师的区别
  12. Java泛型的类型擦除
  13. NYOJ--513--A+B Problem IV(大数)
  14. Rest_framework Serializer 序列化 (含源码浅解序列化过程)
  15. python六十三课——高阶函数之sorted
  16. Java中高级面试必问之多线程TOP50(含答案)
  17. 启动项详解和更改deepin启动内核的方法
  18. 打开和写入excel文件
  19. python自学第三天,列表
  20. MySQL Replication--GTID基础

热门文章

  1. 「AHOI / HNOI2018」转盘 解题报告
  2. Github代码管理教程
  3. BZOJ 3430: [Usaco2014 Jan]Ski Course Rating(并查集+贪心)
  4. BAT批处理知识 及 常用批处理
  5. 关于Python中函数的使用
  6. flutter 小知识
  7. python excel单元格及样式
  8. 您应升级到 MySQL 5.5.0 或更高版本。 phpmyadmin
  9. JUC源码分析-集合篇(九)SynchronousQueue
  10. 用Cython加速Python代码