社区讨论

新人求助,棋盘制作那题,本机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 条回复,欢迎继续交流。

正在加载回复...