社区讨论
新人求助,棋盘制作那题,本机WA,提交AC。。。
P1169[ZJOI2007] 棋盘制作参与者 7已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xmm95
- 此快照首次捕获于
- 2025/11/20 12:29 4 个月前
- 此快照最后确认于
- 2025/11/20 15:19 4 个月前
下面是我的代码
CPP// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int N = 2005;
int n, m, ans1, ans2;
int b[N][N], sum[N][N];
struct data {
int num, id;
};
stack<data>s;
int sqr(int x) {
return x * x;
}
void qwq(int num, int id) {
for(int i = id; !s.empty() && s.top().num > num; id = s.top().id, s.pop()) {
ans1 = max(ans1, (i - s.top().id) * s.top().num);
ans2 = max(ans2, sqr(min(i - s.top().id, s.top().num)));
}
s.push((data) {num, id});
}
void solve() {
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; ++i)
for(int j = m; j >= 1; --j)
sum[i][j] = b[i][j] ? sum[i][j + 1] + 1 : 0;
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
qwq(sum[j][i], j);
}
while(!s.empty()) s.pop();
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
scanf("%d", &b[i][j]);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if((i + j) & 1)
b[i][j] ^= 1;
solve();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
b[i][j] ^= 1;
solve();
printf("%d\n%d", ans2, ans1);
return 0;
}
/*
2 2
1 0
0 1
*/
数据确实好水啊QAQ
回复
共 11 条回复,欢迎继续交流。
正在加载回复...