离散化就一定比普通暴力慢吗

P3397 地毯

御坂19000号 @ 2018-08-25 15:36:46

#include<bits/stdc++.h>
#define re register
using namespace std;
const int N = 1005;
int n,m,num[N][N];
inline int read(){
    int f = 0,x = 0;char ch;
    do{ch = getchar();f |= (ch == '-');}while(!isdigit(ch));
    do{x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}while(isdigit(ch));
    return f ? -x : x;
}
int main(){
    n = read(),m = read();
    for(re int i = 1;i <= m;++i){
        int x = read(),y = read(),x_ = read(),y_ = read();
        //cout << min(x,x_) << ' ' << max(x,x_) << ' ' << min(y,y_) << ' ' << max(y,y_) << endl;
        for(re int j = x;j <= x_;++j){
            for(re int k = y;k <= y_;++k){
                ++num[j][k];
            }
        }
    }
    for(re int i = 1;i <= n;++i){
        for(re int j = 1;j <= n;++j)printf("%d ",num[i][j]);
        putchar('\n');
    }
    return 0;
}

一般的暴力

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define re register
using namespace std;
const int N = 1005;
int n,m,x[N],y[N],x2[N],y2[N];
inline int read(){
    int f = 0,x = 0;char ch;
    do{ch = getchar();f |= (ch == '-');}while(!isdigit(ch));
    do{x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}while(isdigit(ch));
    return f ? -x : x;
}
int main(){
    n = read(),m = read();
    for(re int i = 1;i <= m;++i){
        int a = read(),b = read(),c = read(),d = read();
        x[i] = a,x2[i] = c,y[i] = b,y2[i] = d;
    }
    //for(re int i = 1;i <= m;++i)cout << x[i] << ' ' << x2[i] << ' ' << y[i] << ' ' << y2[i] << '\n'; 
    for(re int i = 1;i <= n;++i){
        for(re int j = 1;j <= n;++j){
            int cnt = 0;
            for(re int k = 1;k <= m;++k){
                if(i >= x[k] && i <= x2[k] && j >= y[k] && j <= y2[k])++cnt;
            }
            printf("%d ",cnt);
        }
        putchar('\n');
    }
    return 0;
}

离散的代码2AC其他全T了


by A星际穿越 @ 2018-08-25 15:37:52

吸氧


by 御坂19000号 @ 2018-08-25 15:45:14

@A星际穿越 可是吸了氧还T啊


by 御坂19000号 @ 2018-08-25 15:45:34

@A星际穿越 难道要吸臭氧


by A星际穿越 @ 2018-08-25 15:46:21

@御坂19000号 其实我也不太清楚太玄学了


by 御坂19000号 @ 2018-08-25 15:48:08

@A星际穿越 氧气太毒瘤


by fangd @ 2019-10-05 21:31:07

其实我觉得这道题的数据还是可以加强一些的。毕竟非常朴素的暴力,都能过掉,例如:

#include <cstdio>
#define MAXN 1010
int carpet[MAXN][MAXN];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while (m--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        for (int i = x1; i <= x2; ++i)
            for (int j = y1; j <= y2; ++j)
                ++carpet[i][j];
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j < n; ++j)
            printf("%d ", carpet[i][j]);
        printf("%d\n", carpet[i][n]);
    }
    return 0;
}

最长的一个点才266ms,这对各种有高级解题思路的大佬似乎不太公平。但是对我这种蒟蒻还是十分友好的。
要是爱情有这么简单CSP有这么简单该多好。


|