HDU 1199 - Color the Ball 离散化-白红宇

HDU 1199 - Color the Ball 离散化

阅读量：4445 次

发布时间：2019-06-07

本文共 1659 字，大约阅读时间需要 5 分钟。

【题意】现在有几个球排成一排，编号从1开始，开始时所有球为黑色，现在有n（<=2000）次操作，每次操作将l[i]至r[i]（均在int范围）的球凃成颜色c[i]（黑色'b'或白色'w'），然后找到最长的连续白色球，输出左右端点符号

【离散化】因为l[i]和r[i]都在int范围，显然不不可以开一个2^31-1那么大的数组。将l[i]和r[i]+1离散化，再模拟染色即可。

如果你不知道离散化：

将l[i]数组所有数与r[i]+1数组所有数取出来从小到大排序，做一个映射。

如样例

1 4 w

8 11 w

3 5 b

把1、5、8、12、3、6取出来，排序为1、3、5、6、8、12，离散化后

原数	1	3	5	6	8	12
离散化后	0	1	2	3	4	5

用mp[]做映射，类型为mp<int,int>。rev_mp[int]做逆向映射。

比如mp[4]=8，离散化后的4就可以看成数8,9,10,11的集合。如果离散化后的4被染成白色，那么相当于原数8,9,10,11均被染成白色。

再取样例中的一行： 1 4 w作为例子，这里1,4是原数，要从把球1,2,3,4均涂色，显然是凃离散化后0（1,2）和1（3,4）即可。

如果当初把r[i]做离散化而不是r[i]+1做离散化的话，r[i]就表示从它开始几个数的集合都被涂色，而不是从它结束涂色。

做好映射后，2^31-1个数就可以看成最多2*n个数，然后模拟染色即可。

这道题写的好晕啊，WA了5发后发现是多Case输入。。。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #define eps 1e-914 #define FOR(i,j,k) for(int i=j;i<=k;i++)15 #define MAXN 100516 #define MAXM 4000517 #define INF 0x3fffffff18 using namespace std;19 typedef long long LL;20 int i,j,k,n,m,x,y,T,ans,big,cas,num;21 bool flag;22 map 
                 
                   mp;23 set 
                  
                    st;24 25 int l[8005],r[8005],rev_mp[8010];26 char c[8005],color[8010];27 int main()28 {29 while(~scanf("%d",&n))30 {31 st.clear();32 mp.clear();33 for (i=1;i<=n;i++)34 {35 scanf("%d %d %c",&l[i],&r[i],&c[i]);36 st.insert(l[i]);//现将其压入set中，也可以放入数组中最后排序 37 st.insert(r[i]+1);38 }39 40 num=0;41 for (set 
                   
                     ::iterator it=st.begin();it!=st.end();it++)//离散化 42 {43 mp[*it]=num;//mp为map
                    
                     类型，做一个映射，如上边的表格 44 rev_mp[num]=*it;//这是map的逆向映射。 45 46 num++;47 }48 49 for (i=0;i

转载于:https://www.cnblogs.com/zhyfzy/p/4257357.html

你可能感兴趣的文章