• <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 閱讀(1233) 評論(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.
            久久婷婷人人澡人人| 99久久99久久精品国产片果冻| 精品少妇人妻av无码久久| 国产精品久久久久影院色| 久久久久久亚洲精品不卡| 伊人久久国产免费观看视频| 久久午夜伦鲁片免费无码| 国产一区二区三精品久久久无广告| 日本精品一区二区久久久| 久久午夜无码鲁丝片| 天天影视色香欲综合久久| 精品久久8x国产免费观看| 亚洲精品无码久久毛片| 久久国产精品久久国产精品| 2021国产精品午夜久久| 精品欧美一区二区三区久久久| 久久A级毛片免费观看| 久久乐国产综合亚洲精品| 91精品日韩人妻无码久久不卡| 久久婷婷国产综合精品| 欧美久久久久久| 婷婷久久综合九色综合九七| 国产精品久久久久久一区二区三区| 99精品国产免费久久久久久下载 | 午夜精品久久久久| 日韩精品久久久久久| 99国产欧美久久久精品蜜芽| 国内精品九九久久精品| 久久人人爽人人爽人人片AV不| 岛国搬运www久久| 国产精品日韩深夜福利久久| 久久精品免费一区二区三区| AV色综合久久天堂AV色综合在| 久久婷婷五月综合国产尤物app| 中文成人久久久久影院免费观看| 国内精品久久久久久不卡影院 | 久久综合鬼色88久久精品综合自在自线噜噜| 久久香蕉国产线看观看乱码| 91精品国产综合久久香蕉| 国产成人精品久久亚洲| 久久综合色之久久综合|