ccf 201409 02 (画图)
作者:
Accepting
,
2020-08-10 00:03:19
,
所有人可见
,
阅读 627
鄙人不才,此中鄙陋甚多,望海涵!!!
直接暴力显然是最简单的方法,那让我们来分析一下时间复杂度,若每次要执行的区间都是最大的,共10000个数,最多执行100万次,100万,统计的复杂度也是1万,也就是100万的复杂度,不会超时,但这显然是一个二位前缀和的题目,这里我们用二维前缀和来写一下就好,注意,既然用到了前缀和,那我们不妨将每个点往后推一个,下标从1开始!
#include<iostream>
using namespace std;
const int N=110;
int s[N][N];
void insert(int x1,int y1,int x2,int y2)
{
s[x1][y1]++;
s[x1][y2]--;
s[x2][y1]--;
s[x2][y2]++;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
insert(x1+1,y1+1,x2+1,y2+1);
}
int sum=0;
for(int i=1;i<=101;i++)
for(int j=1;j<=101;j++)
{
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
if(s[i][j]) sum++;
}
cout<< sum <<endl;
return 0;
}
持续更新中,更新完历年1,2就会更新4,5!