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

            The Sun Also Rises

            Algorithm, Mathematica, 計算機科學, C++, photography, GNU/Linux的討論空間

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              73 隨筆 :: 6 文章 :: 169 評論 :: 0 Trackbacks

            比較不錯的一套題,很多題挺有意思的~

            Strange Billboard

            經典思路了,枚舉第一行的使用方法(2^16),然后推后面的方案。

            Cell Phone
            以每個點為圓心,r為半徑畫圓,問題轉化為求被覆蓋次數最多的區域次數。可以在每個圓上將相交的圓弧求出來,排序掃描,復雜度O(n^2logn)
            CEOI06 Antenna有一種解法就是二分半徑然后用這個方法來求最多能覆蓋多少個點。
            CODE


            Hexagonal Parcels
            Euclid空間上的Steiner樹有一個性質就是n個點,增加的點不超過n-2個。然后這道題有點Steiner樹的感覺,然后我們就猜增加的點至多2個,求最小生成樹。。。然后就對了。不會嚴密證明。
            標程的另一種做法是基于狀態壓縮的DP好像,沒看懂。。。

            Key Task
            簡單的BFS題。

            Gates of Logic
            很麻煩的處理題,暫時沒做。

            Weird Numbers
            負進制轉換。用類似于正進制的方法做,每次保證余數在[0,b)范圍內即可。
            證明如下:
            設我們要轉-b進制,先得到b進制表達式
            N = an*b^n + an-1 * b^(n-1) + ... + a0*b^0
            注意到p為偶數時,ap*b^p = ap * (-b)^p
            p為奇數時,ap*b^p = 1*(-b)^(p+1) + (b - ap) * (-b)^p
            ~~~

            Rectangular Polygon
            由于Polygon的特殊性,我們拉一條平行于x或y軸的直線,則上面一定經過偶數個頂點,并且連邊一定是0-1, 2-3……
            這樣可以construct出邊來,判斷方向可以使用有向面積(即按照當前方向走一遍算面積,根據面積的正負號來判斷是否需要reverse)
            參見SGU 128, Snake

            Reaux! Sham! Beaux!
            簡單題

            Robotic Sort
            需要支持定位某個數和將某一段reverse兩種操作,可以使用分塊處理或者splay_tree。
            因為是按照從小到大的順序把數依次歸位的,所以我們可以理解為每次將這個數歸位后就把這個數刪掉,每次就是reverse從頭開始的一段,這樣可以減少常數 & 編程復雜度。
            用splay_tree的主要想法就是利用樹的中序遍歷來表示序列。利用SplayTree的spaly操作,設當前要歸位的元素為x,把x splay到根,標記根左邊節點為reverse,并刪除根。
            SplayTree的節點需要維護cnt和rev域。在遍歷樹的時候需要應用父節點的rev狀態(類似于線段樹的處理方法)
            CODE


            Tough Water Level
            重心關于含水量的高度是一個單峰函數(感覺比較像~),因此可以三分。
            注意到由于厚度和寬度的函數是一個指定的函數,需要數值積分和表達式求值。
            寫起來還是有點麻煩的~



            posted on 2008-01-28 15:49 FreePeter 閱讀(1237) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC
            Creative Commons License
            This site is licensed under a Creative Commons Attribution-Share Alike 2.5 China Mainland License. 本站采用創作共用版權協議, 要求署名、相同方式共享. 轉載本站內容必須也遵循“署名-相同方式共享”的創作共用協議. This site is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.
            国产91久久综合| 伊人久久无码精品中文字幕| 99久久人妻无码精品系列| 久久99精品久久久久婷婷| 国产91色综合久久免费分享| 久久一本综合| 久久久久久久亚洲Av无码| 色综合久久久久| 久久久久亚洲精品日久生情 | 无码国内精品久久人妻蜜桃 | 欧美色综合久久久久久| 97精品依人久久久大香线蕉97 | 91精品国产91久久综合| 久久久久99精品成人片三人毛片| 伊人色综合久久天天人手人婷 | 亚洲∧v久久久无码精品| 久久这里只精品国产99热| 久久91精品国产91| 国产L精品国产亚洲区久久| 精品国产乱码久久久久久人妻| 99久久99久久精品国产片果冻| 77777亚洲午夜久久多喷| 久久久免费观成人影院| 久久99久久99小草精品免视看| 无码AV波多野结衣久久| 久久综合久久伊人| 久久99精品久久久久久水蜜桃| 99久久人妻无码精品系列| 婷婷久久久亚洲欧洲日产国码AV| 人妻无码精品久久亚瑟影视| 国产成人久久精品麻豆一区| 91视频国产91久久久| 久久久久亚洲AV成人片| 久久综合亚洲欧美成人| 亚洲精品无码久久一线| 亚洲级αV无码毛片久久精品| 久久久久久久久66精品片| 久久福利资源国产精品999| 久久影视国产亚洲| 亚洲人成网站999久久久综合 | 无码人妻久久久一区二区三区 |