• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            數據加載中……

            URAL 1019 A line painting

            A Line painting

            Time Limit: 2.0 second
            Memory Limit: 16 MB
            The segment of numerical axis from 0 to 109 is painted into white color. After that some parts of this segment are painted into black, then some into white again and so on. In total there have been made N re-paintings (1 ≤ N ≤ 5000). You are to write a program that finds the longest white open interval after this sequence of re-paintings.

            Input

            The first line of input contains the only number N. Next N lines contain information about re-paintings. Each of these lines has a form:
            ai bi ci
            where ai and bi are integers, ci is symbol 'b' or 'w', ai, bi, ci are separated by spaces.
            This triple of parameters represents repainting of segment from ai to bi into color ci ('w' — white, 'b' — black). You may assume that 0 < ai < bi < 109.

            Output

            Output should contain two numbers x and y (x < y) divided by space(s). These numbers should define the longest white open interval. If there are more than one such an interval output should contain the one with the smallest x.

            Sample

            input output
            4
            1 999999997 b
            40 300 w
            300 634 w
            43 47 b
            47 634                                                        
            這個題目最直接的辦法是離散化,離散化了之后就好折騰了,因為操作指令很少,所以我選擇離散+樸素染色.
            復雜度上界為O(M*M),這里M表示離散化后得到的區間個數.

             1 #include<iostream>
             2 #include<algorithm>
             3 using namespace std;
             4 const int MAXN=10005;
             5 const int MAXL=1000000000;
             6 struct re
             7 {
             8   int a,b;
             9   char c;
            10 }op[MAXN];
            11 
            12 int n,p=0,que[MAXN];
            13 bool color[MAXN<<1];
            14 
            15 /* 二分查找 */
            16 int find(int num)
            17 {
            18   int l=0,r=p+1,mid;
            19   while (r-l>1)
            20     {
            21       mid=(l+r) >> 1;
            22       (que[mid]<=num)? l=mid : r=mid;
            23       if (que[l]==num) return l;
            24     }
            25   return l;
            26 }
            27 
            28 void disp(re& op)
            29 {
            30   /* 區間由1開始數,而不是由0開始 */
            31   op.a=find(op.a)+1;
            32   op.b=find(op.b);
            33 }
            34 
            35 void mark(int l,int r,char c)
            36 {
            37   for (int i=l;i<=r;++i) color[i]=(c=='b');
            38 }
            39 
            40 int main()
            41 {
            42  // freopen("data.in","r",stdin);
            43  // freopen("data.out","w",stdout);
            44   cin >> n;
            45   for (int i=0;i<n;++i)
            46     {
            47       cin >> op[i].a >> op[i].b >> op[i].c;
            48       que[++p]=op[i].a;
            49       que[++p]=op[i].b;
            50     }
            51   que[++p]=MAXL;
            52   /* 刪除重復出現的數字 */
            53   int rp=0;
            54   for (int i=1;i<=p;++i)
            55     if (que[rp]!=que[i]) que[++rp]=que[i];
            56   p=rp;
            57   /* 排序,便于定位和離散化 */
            58   sort(que,que+p+1);
            59   que[p+1]=MAXL+1;
            60   /* 對操作進行離散處理 */
            61   for (int i=0;i<n;++i) disp(op[i]);
            62   /* 處理操作序列 */
            63   memset(color,0,sizeof(color));
            64   for (int i=0;i<n;++i) mark(op[i].a,op[i].b,op[i].c);
            65   int t=1,a,b,mlen=0;
            66   for (int i=2;i<=p+1;++i)
            67     if (color[i]!=color[t] || i>p)
            68       { 
            69     if ((!color[t]) && (que[i-1]-que[t-1]>mlen)) { a=que[t-1];b=que[i-1];mlen=que[i-1]-que[t-1];}
            70     t=i;
            71       }
            72   cout << a << ' ' << b << endl;
            73   //system("pause");
            74   return 0;
            75 }
            76 
            個別目標遠大的同學可能并不僅僅是想解決這個題目,這時候建議你使用離散化+線段樹,復雜度會大大地降低

            posted on 2009-07-20 15:00 Chen Jiecao 閱讀(425) 評論(0)  編輯 收藏 引用 所屬分類: URAL

            狠狠精品久久久无码中文字幕| 99久久亚洲综合精品成人| 国产精品久久久久久久| 国产精品亚洲综合久久| 成人午夜精品久久久久久久小说 | 国产精品久久久久久吹潮| 中文字幕久久精品无码| 久久亚洲精品国产亚洲老地址| 久久这里有精品视频| 亚洲国产一成久久精品国产成人综合 | 99久久综合狠狠综合久久| 久久久婷婷五月亚洲97号色| 一本一本久久a久久精品综合麻豆| 精品国产VA久久久久久久冰| 精品久久久久久成人AV| 国产精品久久自在自线观看| 狠狠色丁香婷综合久久| 99久久国产综合精品成人影院| 久久亚洲高清观看| 品成人欧美大片久久国产欧美...| 精品久久人人妻人人做精品| 久久久久国产视频电影| 日韩欧美亚洲综合久久| 熟妇人妻久久中文字幕| 久久国产精品-国产精品| 久久久艹| 久久天天躁狠狠躁夜夜躁2O2O| 精品精品国产自在久久高清 | 久久综合久久性久99毛片| 久久久这里有精品| 狠狠久久亚洲欧美专区| 人妻少妇精品久久| 狠狠88综合久久久久综合网| 精品久久久久久无码中文野结衣 | 欧美一级久久久久久久大片| 久久久久久久久久久精品尤物| 国产午夜精品理论片久久影视| 亚洲欧美日韩精品久久亚洲区| 国产一级持黄大片99久久| 久久综合视频网| 国产精品成人99久久久久 |