• <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>
            題目
            越往前做題目就越簡單了 而且只有4道
            通過省選試題難度的變化 看來JLOI這幾年確實進步了不少
            這次的題目全都做上了
            第一題是一道數學題 在這里就不多說了
            第二題他讓你求的是一個點(x,y)使得sigema(wi*((x-xi)^2+(y-yi)^2))(1<=i<=n 以下同此)最小
            初看這個式子里又有x 又有 y 很復雜不好權衡
            可是乘法是符合結合率的
            所以原式=sigema(wi*(x-xi)^2)+sigema(wi*(y-yi)^2)
            所以當sigema(wi*(x-xi)^2)、sigema(wi*(y-yi)^2)都取道最小時既為所求
            則就好辦了就是一個帶權平均數問題(這個好像有學名不過忘了)
            以x為例x=sigema(wi*xi)/sigema(xi) y同理
            第3題:
            如果枚舉任意2個為c的方塊然再bfs或并查集找最長曲線顯然是要超時的(O((n*m)^3),1<=n,m<=30)
            發現由于只改動兩個方塊而每次都求一邊最長曲線會造成許多重復運算
            如果現將整個矩陣先用并查集做一遍然后枚舉該邊哪兩個為c的方塊再算最長曲線就可以在常數時間內完成最長曲線的求解
            如果你總是覺得用什么不對勁的地方 沒關系(其實我一開始也是這樣的)
            我還有一種人那你放心的方法:先枚舉一個c然后做一次并查集然后再枚舉另一個c再用并查集求解 這回不亂了吧(能合并的最多有2條曲線) 這個方法只是將常數增大了 而讓算法清晰了 不失為一種不錯的選擇
            第4題
            想了好久差點放棄了 因為只想到了O((n+m)*(n*m)^2)的算法
            但后來一看1<=n,m<=10這個時間復雜度是綽綽有余的
            顯然任意一個被切下來的矩形都與其他矩形再無干系 這就使得這個模型沒有后效性
            提到后效性不由得讓我們想到DP
            狀態為f[x1][y1][x2][y2]表示把左上角為(x1,y1) 右下角為(x2,y2)的矩形分割成題目中要求的形態最少需要的切割長度 轉移只需要枚舉切割線就好了
            posted on 2009-03-11 01:10 250 閱讀(771) 評論(0)  編輯 收藏 引用 所屬分類: oi
            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            留言簿(6)

            隨筆分類

            隨筆檔案

            文章檔案

            相冊

            搜索

            •  

            最新評論

            伊人久久精品无码av一区| 亚洲精品国产自在久久| a级成人毛片久久| 中文字幕久久波多野结衣av| 久久伊人中文无码| 精品国产91久久久久久久a| 国产精品久久久久久久| 久久久精品一区二区三区| .精品久久久麻豆国产精品| 久久精品国产精品亚洲毛片| 欧美激情精品久久久久久久九九九| 91久久精品91久久性色| 成人综合伊人五月婷久久| 2021久久精品国产99国产精品| 亚洲精品国产字幕久久不卡| 精品久久亚洲中文无码| 无码伊人66久久大杳蕉网站谷歌| 麻豆精品久久久久久久99蜜桃| 亚洲国产婷婷香蕉久久久久久| 深夜久久AAAAA级毛片免费看| 国内精品久久久久影院亚洲| 久久久久久夜精品精品免费啦| 91久久精品视频| 国产国产成人精品久久| 亚洲中文字幕无码久久2017| 国产真实乱对白精彩久久| 久久精品国产亚洲av麻豆图片| 国产亚洲精品久久久久秋霞 | 久久露脸国产精品| 久久中文字幕精品| 亚洲精品乱码久久久久久按摩| 国产亚洲精品自在久久| 国产毛片久久久久久国产毛片| 久久久国产精品亚洲一区| 久久久久久人妻无码| 亚洲成色WWW久久网站| 国产精品久久免费| 91精品久久久久久无码| 国产精品丝袜久久久久久不卡| 久久久久国产精品麻豆AR影院| 久久久久久无码国产精品中文字幕|