是否样例过水?

P1736 创意吃鱼法

onglu @ 2021-02-25 09:07:21

写了个O(n^4)的暴力,然后一发过了?

#include <bits/stdc++.h>
using namespace std;
int read() {
    char c; int num, f = 1;
    while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
    while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
    return f * num;
}
int n, m, g[2509][2509], maxn, ans; 
int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n ;i++) 
        for(int j = 1; j <= m; j++) 
            g[i][j] = read();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int f = 1;
            maxn = 0;
            for(int len = 1; len + i - 1 <= n && len + j - 1 <= m; len++) {
                f = 1;
                if(g[i + len - 1][j + len - 1] != 1) break;
                for(int k = i; k < len + i - 1; k++) {
                    if(g[k][len + j - 1] == 1) {
                        f = 0;
                        break;
                    } 
                }
                for(int k = j; k < len + j - 1; k++) {
                    if(g[len + i - 1][k] == 1) {
                        f = 0;
                        break;
                    } 
                }
                if(f == 0) break;
                else maxn++;
            }
            ans = max(ans, maxn);
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int f = 1;
            maxn = 0;
            for(int len = 1; len + i - 1 <= n && j - len + 1 > 0; len++) {
                f = 1;
                if(g[i + len - 1][j - len + 1] != 1) break;
                for(int k = i; k < len + i - 1; k++) {
                    if(g[k][j - len + 1] == 1) {
                        f = 0;
                        break;
                    } 
                }
                for(int k = j; k > j - len + 1; k--) {
                    if(g[len + i - 1][k] == 1) {
                        f = 0;
                        break;
                    } 
                }
                if(f == 0) break;
                else maxn++;
            }
            ans = max(ans, maxn);
        }
    }
    printf("%d\n", ans);
    return 0;
}

by Unknown_F233 @ 2021-02-25 09:09:07

%%%


by LeavingZzz @ 2021-02-25 09:09:15

那和样例有什么关系


by yjl290250 @ 2021-02-25 09:09:39

%%%%


by onglu @ 2021-02-25 09:10:53

@_Leaving (是数据,口误)


by 听取MLE声一片 @ 2021-02-25 09:24:07

我暴力能过


by 听取MLE声一片 @ 2021-02-25 09:26:00

https://www.luogu.com.cn/record/34501710


by onglu @ 2021-02-25 09:41:10

@听取MLE声一片 我加了一堆剪枝,能剪到900ms。。 评测记录


by 听取MLE声一片 @ 2021-02-25 09:41:38

我的n^3


by cherubim @ 2021-02-25 14:51:40

草确实很水,我也是就这么卡过了,应该加强一波数据让直接暴力枚举过不了吧


|