ZOJ 2301 离散化

题目链接：题意是说，有从 1 开始递增依次编号的很多球，开始他们都是黑色的，现在依次给出 n 个操作（ai，bi，ci），每个操作都是把编号 ai 到 bi 区间内的所有球涂成 ci 表示的颜色（黑 or 白），然后经过 n 次给定的操作后，求最长的连续白色区间的左端点和右端点。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int maxn=100000;

int cnt;

struct node{

   ll l,r;

}ne[2*maxn+10];

bool cmp(node a,node b)

{

   if(a.l!=b.l) return a.l<b.l;

   else return a.r<b.r;

}

bool inter(node i,node j)

{

   return j.r>=i.l&&j.l<=i.r;

}

void update(node &tmp,node &j)

{

   if(tmp.l>j.l&&tmp.r<j.r)

       {

           ne[++cnt]=(node){tmp.r+1,j.r};

           j=(node){j.l,tmp.l-1};

           return;

       }

   if(tmp.l<=j.l&&tmp.r>=j.r)

      {j.l=-1;j.r=-1;return;}

   if(tmp.l>j.l)

       j.r=tmp.l-1;

   else  j.l=tmp.r+1;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        int l,r;

        char op[5];

        cnt=0;

        for(int i=1;i<=n;i++)

           {

               scanf("%d %d",&l,&r);

               if(l>r) swap(l,r);//题目只是说给定的范围

               scanf("%s",op);

               if(op[0]=='w')

                   {ne[++cnt].l=l;ne[cnt].r=r;}

               else

               {

                   node tmp=(node){l,r};

                   int curcnt=cnt;

                   for(int j=1;j<=curcnt;j++)

                       if(inter(tmp,ne[j]))

                            update(tmp,ne[j]);

               }

           }

           sort(ne+1,ne+cnt+1,cmp);

           node ans=(node){1,0};

           for(int i=1;i<=cnt;)

               {

                   node cur=(node){ne[i].l,ne[i].r};

                   if(cur.l<0) {i++;continue;}

                   while(cur.r+1>=ne[i].l)

                    {

                        cur.r=max(ne[i].r,cur.r);i++;//注意新加入的区间不///一定r大于当前

                        if(i>cnt) break;

                    }

                   if(cur.r-cur.l+1>ans.r-ans.l+1)

                      ans=cur;

               }

           if(ans.r!=0)

               printf("%lld %lld\n",ans.l,ans.r);

           else printf("Oh, my god\n");

    }

    return 0;

}

　　分析：最多int范围内的数的球，说明直接开数组是肯定不行的，考虑离散化，毕竟n<=2000,每个

节点代表一个区间，然后每次一出现一个新的黑色的节点，就考虑其对已经有的白色区间的干扰，最后

对所有的白色区间合并记录最长长度就好，参考文章；

wa代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int maxn=100000;

int cnt;

struct node{

   ll l,r;

}ne[2*maxn+10];

bool cmp(node a,node b)

{

   if(a.l!=b.l) return a.l<b.l;

   else return a.r<b.r;

}

bool inter(node i,node j)

{

   return j.r>=i.l&&j.l<=i.r;

}

void update(node &tmp,node &j)

{

   if(tmp.l>j.l&&tmp.r<j.r)

       {

           j=(node){j.l,tmp.l-1};

           ne[++cnt]=(node){tmp.r+1,tmp.r};

           return;

       }

   if(tmp.l<=j.l&&tmp.r>=j.r)

      {j.l=-1;j.r=-1;return;}

   if(tmp.l>j.l)

       j.r=tmp.l-1;

   else  j.l=tmp.r+1;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        int l,r;

        char op[5];

        cnt=0;

        for(int i=1;i<=n;i++)

           {

               scanf("%d %d",&l,&r);

               scanf("%s",op);

               if(op[0]=='w')

                   {ne[++cnt].l=l;ne[cnt].r=r;}

               else

               {

                   node tmp=(node){l,r};

                   for(int j=1;j<=cnt;j++)

                       if(inter(tmp,ne[j]))

                            update(tmp,ne[j]);

               }

           }

            sort(ne+1,ne+cnt+1,cmp);

            node ans=(node){0,0};

           for(int i=1;i<=cnt;)

               {

                   node cur=(node){ne[i].l,ne[i].r};

                   if(cur.l<0) continue;

                   while(inter(cur,ne[i]))

                    {cur.r=ne[i].r;i++;}

                   if(cur.r-cur.l+1>ans.r-ans.l+1)

                      ans=cur;

               }

           if(ans.l!=0&&ans.r!=0)

               printf("%d %d\n",ans.l,ans.r);

           else printf("Oh, my god\n");

    }

    return 0;

}

巴特西

ZOJ 2301 离散化

最新文章

热门文章