题解 P3397 【地毯】

引领天下

2017-07-10 12:05:56

Solution

嗯……看到楼下们 int 数组敢开到 $10000\times10000$ 的,我大受震撼。 ------ 下面说我的方法: 注意到数据都不大,为了节省空间,我们使用 short 代替 int! 事实上,对于 $1000\times1000$ 的数组,开 int 空间也是可以接受的。 代码: ```cpp #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--){ 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;//记得输出完了一行就换行 } } ```