• <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不| 久久笫一福利免费导航| 香蕉99久久国产综合精品宅男自 | 欧美黑人又粗又大久久久| 久久精品国产第一区二区三区| 久久婷婷国产麻豆91天堂| 久久嫩草影院免费看夜色| 中文精品久久久久人妻不卡| 欧美激情精品久久久久| 久久男人中文字幕资源站| 亚洲精品乱码久久久久久蜜桃图片| 91精品国产综合久久四虎久久无码一级| 久久国产视屏| 国产99久久久久久免费看| 亚洲va国产va天堂va久久| 久久夜色tv网站| 国产精品久久新婚兰兰| 精品久久久久久国产免费了| 国产精品久久久久AV福利动漫| 思思久久99热免费精品6| 国产亚洲精品自在久久| 久久久久久精品免费免费自慰 | 99久久精品国内| 久久国产乱子精品免费女| 日本欧美久久久久免费播放网 | 国产精品久久久久久久久软件| 狠狠88综合久久久久综合网| 欧美亚洲国产精品久久久久| 久久强奷乱码老熟女网站| 99久久精品国产一区二区| 99久久免费国产精精品| 久久AV高清无码| 久久久噜噜噜久久熟女AA片| 久久人人爽人人人人片av| 亚洲国产精品狼友中文久久久| 亚洲国产精品成人久久蜜臀 | 久久精品亚洲中文字幕无码麻豆| 久久亚洲中文字幕精品一区| 欧美一级久久久久久久大| 久久久精品日本一区二区三区 |