• <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

            久久久久久久久66精品片| 国产aⅴ激情无码久久| 久久伊人精品青青草原高清| 久久亚洲国产欧洲精品一| 99久久精品国产一区二区三区 | 理论片午午伦夜理片久久| 久久久久噜噜噜亚洲熟女综合| 久久伊人精品青青草原日本| 久久夜色精品国产欧美乱| 成人精品一区二区久久久| 久久综合视频网| 久久免费视频观看| 久久亚洲AV成人无码| 欧美伊香蕉久久综合类网站| 99久久无色码中文字幕人妻| 色综合久久综合网观看| 日产精品久久久久久久| 亚洲精品97久久中文字幕无码| 久久久久久亚洲AV无码专区| 久久青青国产| 国产视频久久| 青青草原综合久久| 97久久精品国产精品青草| 久久亚洲日韩看片无码| 久久久久亚洲精品中文字幕| 久久精品成人免费看| 久久久久亚洲AV无码麻豆| 久久久SS麻豆欧美国产日韩| 久久久久无码国产精品不卡| 国产成人精品久久综合 | 久久最近最新中文字幕大全| 国内精品综合久久久40p| 久久天天躁狠狠躁夜夜2020 | 久久免费视频1| 久久久久18| 亚洲欧美国产日韩综合久久| 久久se精品一区二区影院| 久久久久18| 麻豆av久久av盛宴av| 日本欧美久久久久免费播放网| 午夜精品久久久久久久久|