• <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>
            隨筆-72  評論-126  文章-0  trackbacks-0
            今天下午整了個線段樹
            http://acm.hdu.edu.cn/showproblem.php?pid=1698
            按照模板打了一遍
            然后想做這道
            http://acm.hdu.edu.cn/showproblem.php?pid=1754
            也是比較簡單的線段樹
            想了很久才想出思路來,打好代碼結果連sample都通不過,發現想是query那里錯了
            但是時間到6點了,有DIY,我也先放下,去做DIY
            http://acm.hdu.edu.cn/diy/contest_show.php?cid=2081
            密碼ac
            是斌仔出的
            第一道是數學題
            我想了好點時間才想出方法并證明了,第一次這么有條理的思考,呵呵,賽后還寫了解題報告
            http://m.shnenglu.com/notonlysuccess/archive/2009/02/11/73510.html

            第二道是大數比較,是這些題目中最水的了。。。
            規模不大直接暴力就好過的,就算大的話用二分也行
            不過我大數不太行,調試了好久才AC,汗。。。。。

            第三道是經典的矩陣的DP
            2維的轉化成n(n+1)/2個一維的求最大就行了

            第四道是最小生成樹,不會
            線段樹掌握后一定要解決這個問題~~~!!

            第五道是搜索
            哈哈,這道題目有意思,我抓住了A和C的本質區別,A中間的空格廣搜出去一定全找到*,而其他的則會越界,果然是正確的,1下就AC了

            第六道就是解碼
            挺好處理的,不知道為什么這么多人WA,我開始PE是自己處理數據打印觀察之后忘了去掉一個回車

            第七道是博弈
            全場沒有人動過,我到外邊看了提交記錄,有幾百MS過的,大概廣搜+剪枝也能過吧
            有空去想一下

            第八道回文
            開始想不出方法,后來TTBJ指點一下,從中間向兩邊延伸來做就馬上AC了


            做完這些題目后繼續那道線段樹
            終于改好了,一提交。。。結果TLE。。。
            我開始還以為是哪里不小心死循環了,后來才發現我讀入數據就建樹,每次都是log(n)
            方法太糟糕了200000*log(200000)不超時才怪
            改進一下先用數組先保存分數,再一起建樹這樣就會快很多了。。。。
            1         int a = query(l,mid,id<<1);
            2         int b = query(mid,r,(id<<1)+1);
            3         return Max(a,b);
            4 這個是AC的代碼
            5     else
            6         return Max(query(l,mid,id<<1),query(mid,r,(id<<1)+1));
            7 這個是TLE的代碼
            8 
            9 竟然相差這么多,我暈,改了長時間。。。
            終于刷到了第一
            心滿意足的睡覺去了


            #include<stdio.h>
            #include
            <string>
            #define Max(a,b) a>b?a:b
            struct Tree{
                
            int l,r,max;
            }T[
            3*200001];
            int score[200001];
            void Creat(int l,int r,int id)
            {
                T[id].l 
            = l;
                T[id].r 
            = r;
                
            if(r-l>1)
                {
                    
            int mid = (l + r)>>1;
                    Creat(l,mid,id
            <<1);
                    Creat(mid,r,(id
            <<1)+1);
                    T[id].max 
            = Max(T[id<<1].max,T[(id<<1)+1].max);
                }
                
            else
                    T[id].max 
            = Max(score[l],score[r]);
            }

            void updata(int num,int id)
            {
                
            if(T[id].r - T[id].l <= 1)
                {
                    T[id].max 
            = Max(score[T[id].r],score[T[id].l]);
                    
            return ;
                }
                
            if(T[id<<1].r >= num)
                    updata(num,id
            <<1);
                
            if(T[(id<<1)+1].l <= num)
                    updata(num,(id
            <<1)+1);
                T[id].max 
            = Max(T[id<<1].max,T[(id<<1)+1].max);
            }

            int query(int l,int r,int id)
            {
                
            if(l==T[id].l && T[id].r==r)
                    
            return T[id].max;
                
            int mid = (T[id].l + T[id].r)>>1;
                
            if(l>=mid)
                    
            return query(l,r,(id<<1)+1);
                
            else if(r<=mid)
                    
            return query(l,r,id<<1);
                
            else
                {
                    
            int a = query(l,mid,id<<1);
                    
            int b = query(mid,r,(id<<1)+1);
                    
            return Max(a,b);
                }
            }
            int getval()
            {
                
            char c;
                
            int ret=0;
                
            while((c=getchar())!=' '&&c!='\n')
                    ret
            =ret*10+(c-'0');
                
            return ret;
            }
            int main()
            {
                
            int n,m,i,a,b;
                
            char ch;
                
            while(scanf("%d%d",&n,&m)==2)
                {
                    getchar();
                    
            for(i=1;i<=n;i++)
                    {
                        
            int ret=0;
                        score[i] 
            = getval();
                    }
                    Creat(
            1,n,1);
                    
            while(m--)
                    {
                        ch 
            = getchar();
                        getchar();
                        a 
            = getval();
                        b 
            = getval();

                        
            if(ch=='U')
                        {
                            score[a] 
            = b;
                            updata(a,
            1);
                        }
                        
            else
                        {
                            
            if(a==b)
                                printf(
            "%d\n",score[a]);
                            
            else
                            {
                                
            int ans = query(a,b,1);
                                printf(
            "%d\n",ans);
                            }
                        }
                    }
                }
                
            return 0;
            }

            明天要好好休息了,早點睡覺。后天早上上火車回學校咯。。。
            posted on 2009-02-12 03:23 shǎ崽 閱讀(401) 評論(1)  編輯 收藏 引用

            評論:
            # re: 2009.2.11小記 2009-02-12 19:06 | AekdyCoin
            我才375MS...
            Orz...你怎么優化的?  回復  更多評論
              
            久久精品亚洲一区二区三区浴池| 久久人人爽人人爽人人片AV麻豆| 一本一本久久aa综合精品| 久久久久亚洲AV成人片| 99久久人妻无码精品系列| 久久九九免费高清视频| 伊人久久久AV老熟妇色| 国产成人精品久久一区二区三区av | 污污内射久久一区二区欧美日韩 | 久久精品国产免费一区| 久久青青草原国产精品免费| 久久无码一区二区三区少妇| 久久精品国产亚洲77777| 久久久无码精品午夜| 久久精品国产69国产精品亚洲| 久久只有这精品99| 很黄很污的网站久久mimi色| 一本一本久久A久久综合精品| 久久久久噜噜噜亚洲熟女综合| 国产产无码乱码精品久久鸭| 欧美亚洲国产精品久久高清| 青青青国产成人久久111网站| 亚洲AV日韩精品久久久久| 久久婷婷色香五月综合激情| 国产激情久久久久影院老熟女| 99久久99久久精品免费看蜜桃| 久久伊人五月丁香狠狠色| 久久综合色之久久综合| 91精品国产高清久久久久久91| 国内精品久久久久久99蜜桃| 久久一日本道色综合久久| 久久天天躁夜夜躁狠狠躁2022| 中文字幕无码久久久| 人妻无码精品久久亚瑟影视| 久久久久国产一区二区三区| 久久久久18| 亚洲综合久久久| 精品久久久中文字幕人妻| 亚洲AV无码久久精品蜜桃| 色狠狠久久AV五月综合| 色综合久久久久无码专区|