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

            [Solution] Dhaka 2007

            Bachelor Arithmetic
            秒殺題

            Nested Squares
            模擬題

            The Dumb Grocer
            首先要有1是吧。。。然后我們按照1的個數來分類,我們來計算恰有k1的方案數。
            我們在k1的基礎上加入新的數,顯然第一個數只能是k+1
            然后加入的數只能是k + 1 or 2 * (k + 1)
            如法炮制。。。發現非1的數都具有(k + 1) * t的形式。。。設其依次為(k + 1) * ti
            {ti}這些數也滿足題目的性質。。。共有f((n - k) / (k + 1))種方案。

            f(n)是要求的函數,則f(n) = sigma(f((n - k) / (k + 1)), (k + 1) | (n + 1) , k>=1
            f(0) = 1
            這樣直接做會T...
            我們令g(n) = f(n - 1)
            g(n) = f(n - 1) = sigma(f((n - k - 1) / (k + 1))) = sigma(f(n / (k + 1) - 1)) = sigma(g(n / (k + 1)), (k + 1) | n, k >= 1
            n = p1^a1 * p2^a2 * ... * pr*ar
            h(p1, p2,.., pr, a1, a2...ar) = g(n)
            = h(p1,p2, ...pr, b1, b2, ...br),
            0<=bi <= ai, bi
            不全=ai
            注意對于一個確定的nh()中的p1, p2...pr在計算過程中始終不變。。。所以。。。計算結果與pi無關,只與ai有關
            這樣狀態數就大大減少了。。。直接因式分解后dp就行了。。。

            ACM Puzzles
            狀態壓縮dp


            The Bells are Ringing Photographic Tour
            這三題好像當時沒寫summary。。。所以我們假設比較簡單~~~


            You are around me ...
            首先旋轉坐標,變成平行與xy軸的橢圓,然后坐標伸縮。。。變成圓。。。最近點對。。。貼模板。。。
            ZJU2107 Quoit Design
            一道測最近點對的題。


            Infinite Matrix
            顯然,對于固定的j, Ri, j是一個關于i的多項式。
            注意到數列Ri, j的差分序列R(i + 1, j) - R(i, j)是可以求出來的(利用Mj, k <= 10的條件,可以在O(10*n^2)的時間內算出)
            然后有了差分序列求通項就是O(n^2)的事情。
            然后記S(p, j)(n) = Sigma(i^p * R(i, j)) i <= n
            繼續利用差分序列之類的方法求這個,最后再求一個Sum_S(p, j)
            預處理復雜度大致是O(10*n^3)的。
            后面的就好辦了,對每個詢問,把(i + 1)^p二項式展開,最多10項,然后利用公式直接計算。
            處理詢問復雜度O(p*q*n)
            POJ3529 Matrix Analysis
            ,類似的思想,更簡單~

            Magnetic Train Tracks
            給定n個點,求可以構成多少個銳角三角形。
            n <= 1200
            話說求銳角三角形不太好算是吧。。。補集轉換,我們來求鈍角/直角三角形 <=> 求鈍角/直角個數。。。
            后面的事情就簡單了,是對每個點,將其他點按照極角排序 + 掃描。
            Dhaka 2005 Counting Triangles
            也是一道補集轉換的題~(轉化成求三點共線的個數)
            Shanghai 2004 Amphiphilic Carbon Molecules
            也是一道極角排序+掃描的題。

            posted on 2008-05-01 20:22 FreePeter 閱讀(914) 評論(1)  編輯 收藏 引用 所屬分類: AlgorithmACM/ICPC

            評論

            # re: [Solution] Dhaka 2007 2010-09-10 00:06 Quynh
            Dear FreePeter,
            I dont really understand your solution to Infinite Matrix problem.
            Can you classify it to me ? in more details...?
            Furthermore, if you can explain in English, because I have some problems in translating Chinese into English.
            If okay, show me the solution to "Matrix Analysis" problem.

            Thank you in advance !
            Quynh, Nguyen  回復  更多評論
              

            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精品久久久久久9蜜桃| 国产成人久久精品二区三区| 亚洲欧美成人久久综合中文网| 久久精品无码一区二区三区日韩 | 久久免费观看视频| 青青久久精品国产免费看| 少妇人妻88久久中文字幕| 久久被窝电影亚洲爽爽爽| 香蕉久久夜色精品国产2020| 久久综合狠狠综合久久| 久久国产免费直播| 99精品久久久久中文字幕| 午夜精品久久久内射近拍高清| 日产精品久久久一区二区| 久久久久久亚洲精品无码| 国产美女久久精品香蕉69| 开心久久婷婷综合中文字幕| www.久久精品| 欧美午夜精品久久久久免费视| 久久婷婷色综合一区二区| 日本免费久久久久久久网站 | 九九精品99久久久香蕉| 模特私拍国产精品久久| 久久久久亚洲精品天堂久久久久久 | 国产精品久久久久久久app| 久久国产高清字幕中文| 欧美精品国产综合久久| 一本久道久久综合狠狠躁AV| 欧美久久综合性欧美| 波多野结衣中文字幕久久 | 香蕉久久夜色精品国产2020| 久久丝袜精品中文字幕| 精品久久久久久无码国产| 久久久久国产一级毛片高清版| 久久久久亚洲av无码专区导航| 亚洲伊人久久成综合人影院 | 亚洲中文久久精品无码ww16| 思思久久精品在热线热| 中文字幕日本人妻久久久免费| 色妞色综合久久夜夜| 一本一本久久a久久综合精品蜜桃 一本一道久久综合狠狠老 |