首页 > 代码库 > JOI 2012 fish 题解

JOI 2012 fish 题解

题目大意:

给你一个0/1/2序列Ai,每个值Ai有一个权值Pi。如果两个值的权值PiPj满足Pi2Pj,那么Ai就会把Aj吔掉,也就是说Ai, Aj不能共存。

Ai的一个子序列的特征三元组为(Sum0, Sum1, Sum2),其中Sump为子序列中的Ai=p的个数。当然这里要求所有值可以共存。

求:Ai的所有合法子序列的特征三元组的种类数目。1N200000

这道题可谓是难题(对于我),同样是听完题解外加问人外加参考代码才回的,我们给个原题网址(日文版)戳一下http://www.ioi-jp.org/camp/2012/2012-sp-tasks/

首先我们现将p从小到大排一下序,此时我们可以求出对于每一个i它的极大三元组,就是对于每一个i,求一个最大的j,使得pj<pi*2,那么统计i到j中的0,1,2的个数,记它为极大三元组,我们记这n个极大三元组为a,b,c。

如果将a,b,c放入立体三维空间中,那么问题就转换为了求这些立方体(0,0,0到a,b,c)的体积并,只要在立方体里面的点就一定满足条件,这显然是比较难求的,但是如果我们把它转换为二维,问题就简单了很多。

首先我们将它们以a从小到大排序,然后依次在平面内加入点(b,c),我们可以发现,对于任意a‘>a,满足a‘的所有b,c一定在a下一定成立,所以每次在统计a的时候,要加上之前>a的面积并。并且我们发现,每一时刻面积并的形状都是阶梯状的,也就是说,b越大c越小,所以可以每次加进来一个点,只需要判断它是否在图形外,在图形外,则要更新面积以及在边缘的点,这就体现了c++的好处,巧用set,就可以避免写平衡树了。贴几张原题题解图

     +-----+-----+                     
    /     /     /|
   +-----+-----+ |
  /     /     /| +
+-----+-----+ |/|
|     |     | + |
|     |     |/| +
+-----+-----+ |/|
|     |     | + |
|     |     |/| +
+-----+-----+ |/
|     |     | +
|     |     |/
+-----+-----+ 

     +-----+-----+
    /0,2,1/1,2,1/|
   +-----+-----+ |
  /     /     /| +
+-----+-----+ |/|
|     |     | + |
|0,2,0|1,2,0|/| +
+-----+-----+ |/|
|     |     | + |
|0,1,0|1,1,0|/| +
+-----+-----+ |/
|     |     | +
|0,0,0|1,0,0|/
+-----+-----+ 

       +---------+
      /         /|
     /         / |
    +---------+  |
    |         |  +--------+
    +------+  | /        /|
   /      /|  |/        / +-----+
  /      / ;--+        / /     /|
+------+ +-----------+ +-----+ +
|      | |           | |     |/
|      | |           | +-----+
|      | |           |/
|      | +-----------+
|      |/
+------+    

+--+--+----+----+---+-->
|  |  |    |    |   |
+--+--+----+----+---@
|  |  |    |    |
+--+--+----@    |
|  |  |         |
+--+--+---------@
+--+--@
|  |
|  |
+--@
|
V

 +-------------------+-->
|                   |
|               +---@
|               |
|               |
|               |
|     +---------@
|  +--@
|  |
|  |              o <-- たとえばこの点を追加するとします
+--@
|
V
 +-------------------+-->
|                   |
|               +-+-@
|               | |
|               | |
|               | |
|     +---------@ |
|  +--@           |
|  |              |
|  +--------------o
+--@
|
V

+-------------------+-->
|                   |
|                 +-@
|                 |
|                 |
|                 |
|               ; |
|     ;           |
|                 |
|  +--------------o
+--@
|
V

可能讲的不清楚,具体看代码吧。

 

  1 #include<iostream>  2 #include<set>  3 #include<cstdio>  4 #include<algorithm>  5 using namespace std;  6 int n;  7 const int maxn=200005;  8 struct node  9 { 10     int type,val; 11 }a[maxn]; 12 struct three 13 { 14     int a,b,c; 15 }d[maxn]; 16 bool cmp(node u,node v) 17 { 18     return u.val<v.val; 19 } 20 int now; 21 bool ff(three u,three v) 22 { 23     return u.a>v.a; 24 } 25 long long  mian; 26 set <int> s; 27 int h[maxn],l[maxn],r[maxn]; 28 void listAdd(int x, int prev) 29 { 30     int succ=r[prev]; 31     l[x]=prev;r[prev] = x; 32     r[x]=succ;l[succ] = x; 33 } 34 long long ans; 35 int main() 36 { 37     scanf("%d",&n); 38     for(int i=1;i<=n;i++)scanf("%d%d",&a[i].type,&a[i].val); 39     sort(a+1,a+n+1,cmp); 40 //    for(int i=1;i<=n;i++)cout<<a[i].val<<" "; 41     int da=0,db=0,dc=0; 42     for(int i=1;i<=n;i++) 43     { 44         if(i!=1) 45         { 46             if(a[i-1].type==0)da--; 47             else if(a[i-1].type==1)db--; 48             else dc--; 49         } 50         while(now<n && a[now+1].val<a[i].val*2) 51         { 52             now++; 53             if(a[now].type==0)da++; 54             else if(a[now].type==1)db++; 55             else dc++; 56         } 57       //  cout<<da<<" "<<db<<" "<<dc<<endl; 58         d[i].a=da+1; 59         d[i].b=db+1; 60         d[i].c=dc+1; 61     } 62     sort(d+1,d+n+1,ff); 63      64     for(int i=1;i<=n;i++) 65 //    printf("%d %d %d\n",d[i].a,d[i].b,d[i].c); 66  67     s.clear(); 68     int ll=0,rr=n+2; 69     l[ll]=l[rr]=ll; 70     r[ll]=r[rr]=rr; 71     h[ll]=rr; 72     h[rr]=ll; 73     s.insert(ll); 74     s.insert(rr); 75     for(int i=1;i<=n;i++) 76     { 77         ans+=mian*(long long)(d[i-1].a-d[i].a); 78     //    cout<<ans<<endl;     79      80         int x=d[i].b; 81         int y=d[i].c; 82         if(!s.count(x)) 83         { 84             int succ=*s.lower_bound(x); 85             s.insert(x); 86             listAdd(x,l[succ]); 87             h[x]=h[succ]; 88         } 89         while(true) 90         { 91             if(h[x]>=y)break; 92             mian+=((long long)y-h[x])*((long long)x-l[x]); 93             h[x]=y; 94             x=l[x]; 95         } 96         //cout<<i<<endl; 97         x=d[i].b; 98         while(h[l[x]]==h[x]) 99         {100             int tx=l[x];101             r[l[tx]]=r[tx];102             l[r[tx]]=l[tx];103             s.erase(tx);104         }105     //    cout<<i<<endl;106         //cout<<"find"<<endl;107     }108     ans+=mian*d[n].a;109     cout<<ans<<endl;110     return 0;111 }
View Code