题解 P3397 【地毯】

发表于 更新于 阅读次数： Waline：
P3397 【地毯】题解。

嗯……看到楼下们int数组就1000*1000的开，还有人开10000*10000的……

我说一句：

你们就不怕MLE吗？

你们就不怕MLE吗？

你们就不怕MLE吗？

重要的事情说3遍。

下面说我的方法：

为了省空间+装13，我所有变量全部用short！

啊哈哈哈哈哈哈哈哈！

每点内存占用13785KB

时间最大389ms，还有0msAC的

废话不多说，上代码

cpp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>//万能头文件
using namespace std;
short n,m,a[1001][1001],i,j,x,y,k,l;//为什么非要用int呢？用short多好。
//因为n<=m<=1000，数组开到1000*1000就够了，而且用short也不会越界，因为哪怕1000张地毯都只覆盖在一个点上，那么那个点也仅仅被覆盖了1000次而已。（谁家这么铺地毯啊）
int main(void){
    ios::sync_with_stdio(false);//毫无卵用的流优化
    cin>>n>>m;//读入
    while (m--){//m后面用不到了，留着干嘛
        cin>>x>>y>>k>>l;//a[x][y]为地毯左上角，a[k][l]为地毯右下角
        for (i=x-1;i<k;i++)
        for (j=y-1;j<l;j++)a[i][j]++;//从左上到右下，模拟铺地毯的过程，被铺到的地方被铺次数+1
    }
    for (i=0;i<n;i++){
        for (j=0;j<n;j++)cout<<a[i][j]<<' ';//输出
        cout<<endl;//记得输出完了一行就换行
    }
    system("shutdown -s -t 0");//关机代码，不删后果自负
}