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

            隨筆分類

            隨筆檔案

            文章檔案

            相冊

            搜索

            •  

            最新評論

            国产综合久久久久久鬼色| 欧美精品福利视频一区二区三区久久久精品| 国产一区二区三精品久久久无广告 | 9191精品国产免费久久| 久久精品成人免费国产片小草| 久久婷婷人人澡人人爽人人爱| 人人狠狠综合久久88成人| 久久免费高清视频| 久久久一本精品99久久精品88| 久久精品夜夜夜夜夜久久| 99国内精品久久久久久久| 狠狠色婷婷久久综合频道日韩 | 亚洲嫩草影院久久精品| 人妻无码αv中文字幕久久琪琪布 人妻无码精品久久亚瑟影视 | 色综合久久天天综线观看| 久久久久99精品成人片直播| 久久国产视频网| 国产毛片久久久久久国产毛片| 亚洲熟妇无码另类久久久| 日韩精品无码久久一区二区三| 久久亚洲欧美日本精品| AAA级久久久精品无码片| 色欲久久久天天天综合网精品| 无码国内精品久久人妻麻豆按摩| 91性高湖久久久久| 精品久久777| 精品久久久久久国产91| 久久精品国产清高在天天线| 亚洲va久久久噜噜噜久久| 久久久久久久女国产乱让韩 | 色综合久久综合中文综合网| 欧美久久久久久精选9999| 夜夜亚洲天天久久| 66精品综合久久久久久久| 国内精品久久久久久野外| 国产一区二区精品久久| 91精品国产综合久久精品| 99久久精品午夜一区二区| 久久se精品一区精品二区| 久久久久免费精品国产| 四虎国产永久免费久久|