嘩啦啦的小彭玉染色問題

Time Limit: 1 Sec??Memory Limit: 256 MB

題目連接

http://acdream.info/problem?pid=1725

Description

嘩啦啦，嘩啦啦~

小彭玉很開心，拿著一堆海報就開始宣傳明天要開始的嘩啦啦大會了~

小彭玉很可愛，他的海報都是五顏六色的~

嘩啦啦，嘩啦啦~

小彭玉在一個巨大的宣傳欄上貼了一大堆海報！

“真是好看呢！”，唐老師說道。

唐老師這時，就想出了一個題目，“這面宣傳欄，最后能看見多少顏色呢？”

狗哥噗呲一笑，“這題太簡單了！”

那你們會嗎？

注意啦：后面貼的海報是會覆蓋先前貼的~

Input

第一行，n,m,c，表示宣傳欄有n行，m列，一開始顏色是c

第二行,? k，表示小彭玉一共貼了k張海報

接下來k行 x1i,y1i,x2i,y2i,ci,ti??六個字母，表示小彭玉在ti的時間，在貼上左下角坐標為（x1i,y1i），右上角坐標為（x2i,y2i），顏色為ci的海報

數據保證每一時間，小彭玉最多貼一張海報~

數據范圍：

1<=n<2147483647 ? 1<=m<2147483647?? 1<=c<2147483647

0<=k<=1000

1<=x1i<=n,1<=y1i<=m,1<=x2i<=n,1<=y2i<=n,1<=ci<2147483647

Output

輸出一個整數，表示有多少顏色能夠被看見

?

Sample Input

3 3 1
4
3 3 3 3 5 3
2 1 2 3 3 1
1 1 1 1 1 2
2 2 3 3 2 4

?

Sample Output

3

?

HINT

樣例之后，宣傳欄變成了：

1 2 2
1 2 2
1 3 1

所以顏色總共有3種

題意

?

題解：

離散之后，并查集優化一下就好了~

然后直接亂搞

http://pan.baidu.com/s/1sjoLGxn

代碼：

?

//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 4005 #define mod 10007 #define eps 1e-9 int Num; char CH[20]; //const int inf=0x7fffffff; //§?§é§à§é¨f§3 const int inf=0x3f3f3f3f; /*inline void P(int x) {Num=0;if(!x){putchar('0');puts("");return;}while(x>0)CH[++Num]=x%10,x/=10;while(Num)putchar(CH[Num--]+48);puts(""); } */ inline ll read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } inline void P(int x) {Num=0;if(!x){putchar('0');puts("");return;}while(x>0)CH[++Num]=x%10,x/=10;while(Num)putchar(CH[Num--]+48);puts(""); } //**************************************************************************************struct node {int x1,y1,x2,y2,t,c; }; int n,m,c; int k; node a[maxn]; vector<int> q1; vector<int> q2; map<int,int> H1; map<int,int> H2; int fa[2010][2010]; int mp[2010][2010]; map<int,int> flag; int ans;bool cmp(node b,node c) {return b.t>c.t; }int fi(int x,int y) {if(y!=fa[x][y])fa[x][y]=fi(x,fa[x][y]);return fa[x][y]; }int main() {scanf("%d%d%d",&n,&m,&c);q1.push_back(n);q2.push_back(m);q1.push_back(1);q2.push_back(1);scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].c,&a[i].t);q1.push_back(a[i].x1);q1.push_back(a[i].x2);q2.push_back(a[i].y1);q2.push_back(a[i].y2);}a[k].x1=1,a[k].y1=1,a[k].x2=n,a[k].y2=m,a[k].c=c,a[k].t=0;sort(a,a+k+1,cmp);sort(q1.begin(),q1.end());sort(q2.begin(),q2.end());q1.erase(unique(q1.begin(),q1.end()),q1.end());q2.erase(unique(q2.begin(),q2.end()),q2.end());for(int i=0;i<q1.size();i++)H1[q1[i]]=i+1;for(int i=0;i<q2.size();i++)H2[q2[i]]=i+1;for(int i=1;i<=q1.size()+1;i++)for(int j=1;j<=q2.size()+1;j++)fa[i][j]=j;for(int p=0;p<=k;p++){for(int i=H1[a[p].x1];i<=H1[a[p].x2];i++){for(int j=H2[a[p].y1];j<=H2[a[p].y2];j++){j=fi(i,j);if(j>H2[m])break;mp[i][j]=a[p].c;if(!flag[a[p].c])ans++;flag[a[p].c]=1;fa[i][j]=j+1;}}}printf("%d\n",ans); }

?

總結

以上是生活随笔為你收集整理的acdream 1725 哗啦啦的小彭玉染色问题 离散化并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。