jzoj幻灯片【离散化】【模拟】

幻灯片【离散化】【模拟】"/>

jzoj幻灯片【离散化】【模拟】

>Description
在一个平面上放置有许多涂满颜色的幻灯片，这些幻灯片都是矩形而且是半透明的，所有的幻灯片的四边都与X轴或Y轴平行。我们可以给这些幻灯片的颜色编一个号，相同的数字对应相同的颜色。但是这些幻灯片可能会相互重叠，重叠部分的颜色就会混合变成另一种颜色，这个颜色值等于所有重叠幻灯片的颜色值之和。你的任务是找出这个平面上有多少种不同的颜色。

>Input
输入第一行为一个整数N（1<=N<=100），N为平面上幻灯片的数量。接下来N行每行5个整数X1, Y1, X2, Y2, C，X1<X2，Y1<Y2，1<=C<=100，描述了一张幻灯片的情况，(X1,Y1)为左下角坐标，(X2,Y2)为右上角坐标，C为幻灯片颜色值。

>Output
输出一个整数，为平面上出现的不同颜色的数量。

>Sample Input
3
2 2 3 3 2
2 0 4 4 1
1 1 3 5 3

>Sample Output
4

对于50%的数据，0<=X1,Y1,X2,Y2<=10^2。
对于100%的数据，0<=X1,Y1,X2,Y2<=10^9。

>解题思路

对于很多人，50%的数据应该都可以水过（我不是普通人）
由于100%的数据太大了，所以需要使用到离散化这个东西：

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；
……………………

（从百度百科上Ctrl+C来的）
虽然看着很懵逼8，但是其实还是看得懂的。

根据题意，把每一个坐标中的行和列存入所有行和所有列所分别属于的结构体，排个序，对于每一个数组（结构体），第一个数原本存的内容更替为1，第二个更替为2……（如果原本存入的数与上一个数的原型相同的话，就存与上一个数现在存入的相同，下一个数如果不相同的话，就按照原排序的序号存，很像成绩排序那样）

这样，最后只用模拟很小的范围就OK了。要注意每组数据的匹配。

>代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct ooo
{int bh,s,sb,hh; //bh存当前数属于哪张幻灯片，hh存当前数属于左下角(1)还是右上角(2)，s为内容，sb为离散化后的内容
}a[305],b[305]; //a为行，b为列
int n,ans,t,c[205],cc[205][205]; //c存每张幻灯片颜色
bool yd[10000005];
bool lil(ooo aa,ooo bb){return aa.s<bb.s;}
bool lil2(ooo aa,ooo bb)
{if(aa.bh!=bb.bh) return aa.bh<bb.bh;return aa.hh<bb.hh;
}
int main()
{
//	freopen("b.in","r",stdin);
//	freopen("b.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){a[i].bh=a[n+i].bh=b[i].bh=b[n+i].bh=i; a[i].hh=b[i].hh=1; a[n+i].hh=b[n+i].hh=2;scanf("%d%d%d%d%d",&a[i].s,&b[i].s,&a[n+i].s,&b[n+i].s,&c[i]);}t=2*n;sort(a+1,a+1+t,lil); //按照内容大小排序for(int i=1;i<=t;i++){if(a[i].s==a[i-1].s) a[i].sb=a[i-1].sb;else a[i].sb=i; //离散化（你懂的8）}sort(b+1,b+1+t,lil); //同上for(int i=1;i<=t;i++){if(b[i].s==b[i-1].s) b[i].sb=b[i-1].sb;else b[i].sb=i; //同上}sort(a+1,a+1+t,lil2);sort(b+1,b+1+t,lil2); //排回以前的顺序（幻灯片从1~n，每张幻灯片内先左下角后右上角）for(int k=1;k<=t;k+=2) //枚举幻灯片for(int i=a[k].sb+1;i<=a[k+1].sb;i++)for(int j=b[k].sb+1;j<=b[k+1].sb;j++) //模拟矩阵（+1是因为坐标表示的是点，不是格子！！）cc[i][j]+=c[(k+1)/2]; //累加颜色for(int i=1;i<=t;i++)for(int j=1;j<=t;j++)if(cc[i][j]>0&&!yd[cc[i][j]]){yd[cc[i][j]]=1;ans++;}printf("%d",ans);return 0;
}