建设部网站施工员查询,临海市建设规划局网站,网站建设自身优势的分析,做百度收录的网站幻灯片
题目大意#xff1a;
有n个幻灯片映在一起#xff0c;每个幻灯片的的左上角是a1,a2,右上角是a3,a4,颜色是a5当多个幻灯片在同一个位置时#xff0c;颜色就是他们的和#xff0c;求有所少种颜色
样例输入
3
2 2 3 3 2
2 0 4 4 1
1 1 3 5 3
样例输出
4
数据…幻灯片
题目大意
有n个幻灯片映在一起每个幻灯片的的左上角是a1,a2,右上角是a3,a4,颜色是a5当多个幻灯片在同一个位置时颜色就是他们的和求有所少种颜色
样例输入
3
2 2 3 3 2
2 0 4 4 1
1 1 3 5 3
样例输出
4
数据范围限制
提示
数据说明
对于50%的数据0X1,Y1,X2,Y210^2。
对于100%的数据0X1,Y1,X2,Y210^9。
解题思路
这道题只能拿50分暴力想拿100分首先要离散化注意这里要加0.5或减0.5要不然会有bug离散化要排序去重然后还要将去重后的位置放回原处这样就可以省下很多空间时间然后用一种差分快速推出每一个地方的颜色
#includecstdio
#includeiostream
#includealgorithm
#includecstring
using namespace std;
int w,n,len,ans,b[1005][1005],pd[10005];
double f[1005];
struct rec
{double x1,x2,y1,y2;//每一个幻灯片int c;
}a[105];
int main()
{freopen(b.in,r,stdin);freopen(b.out,w,stdout);scanf(%d,n);for (int i1;in;i){scanf(%lf %lf %lf %lf %d,a[i].x1,a[i].y1,a[i].x2,a[i].y2,a[i].c);f[w]a[i].x1-0.5;//全是避免bugf[w]a[i].y1-0.5;f[w]a[i].x20.5;f[w]a[i].y20.5;f[w](a[i].x10.5);f[w](a[i].y10.5);f[w](a[i].x2-0.5);f[w](a[i].y2-0.5);}sort(f1,f1w);//排序lenunique(f1,f1w)-f-1;//去重for (int i1;in;i){a[i].x1lower_bound(f1,f1len,a[i].x1)-f;//先二分查找再放回去离散化a[i].y1lower_bound(f1,f1len,a[i].y1)-f;a[i].x2lower_bound(f1,f1len,a[i].x2)-f;a[i].y2lower_bound(f1,f1len,a[i].y2)-f;b[(int)a[i].x1][(int)a[i].y1]a[i].c;//左上角b[(int)a[i].x21][(int)a[i].y21]a[i].c;//右下角b[(int)a[i].x1][(int)a[i].y21]-a[i].c;//右上角b[(int)a[i].x21][(int)a[i].y1]-a[i].c;//左下角}for (int i1;ilen;i)for (int j1;jlen;j){b[i][j]b[i-1][j]b[i][j-1]-b[i-1][j-1];//差分if ((b[i][j])(!pd[b[i][j]]))//判断是否记录过和是否有颜色ans,pd[b[i][j]];//颜色种数加一}printf(%d,ans);//输出fclose(stdin);fclose(stdout);return 0;
}
