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

            HNOI2011 部分題題解

            Posted on 2012-04-24 21:25 Mato_No1 閱讀(846) 評論(0)  編輯 收藏 引用 所屬分類: HNOI
            【最近很想被各種省選題虐……于是,就開始找各種省選題……發(fā)現(xiàn)能虐本沙茶的實在是太多了(誰叫我是沙茶呢囧)】

            homework:
            很能令人想歪的題目……想到某種數(shù)論模型……
            正解是遞推+矩陣優(yōu)化??梢赃@么想,本題如果暴力遞推的話,設(shè)F[i]為1到i組成的數(shù)(具體的數(shù),不是取模以后的結(jié)果,雖然這個值是無法存儲的),則有F[i]=(F[i-1]*10T)+i,其中T是i在十進(jìn)制下的位數(shù),邊界F[0]=0。這個式子是可以矩陣優(yōu)化的,矩陣為
            10T 0 0
            1 1 0
            1 1 1
            則1*3矩陣[F[i-1], i-1, 1]乘以這個矩陣之后就是[F[i], i, 1],然后對于各個T分開處理一下就行了……這里的取模完全就是個幌子……
            (另外,矩陣優(yōu)化遞推是一個很重要的專題……)

            race:
            (最近剛好在某MO神犇的資料里面看到了柯西不等式……發(fā)現(xiàn)此題可以用這個來搞……就囧掉了)
            柯西不等式:(a12+a22+...+an2)(b12+b22+...+bn2)>=(a1b1+a2b2+...+anbn)2  【*】,
            等號成立當(dāng)且僅當(dāng)對于任意1<=i, j<=n, i≠j,有aibj-ajbi=0,也就是(a1, b1), (a2, b2)...(an, bn)這n個點共線。具體證明的話,把兩邊的乘法列成一個矩陣的形式,去掉主對角線(相同),把關(guān)于主對角線對稱的位置對應(yīng)相減,得到類似叉積的平方和的形式即可。

            對于本題,假設(shè)不考慮耗油量為負(fù)時取0的情況,設(shè)F0=(F-Σ(b*Li*Si))/a,則問題就轉(zhuǎn)化為求一組vi使得ΣLivi=F0且Σ(Li/vi)的值最小。這樣,可以設(shè)ai=sqrt(Li/vi),bi=sqrt(Livi),代入【*】式……傻眼了囧……不僅能得到最小值,還能發(fā)現(xiàn)取得最小值時所有的v都相等,且可以算出來……當(dāng)然如果F0<0就無解了囧……
            不過本題最囧的問題是對于耗油量為負(fù)的情況。最好的處理辦法是,如果按照【*】式得到的v值會導(dǎo)致某些s<0的路段耗油量為負(fù),則對于這些路段單獨處理,使得它們的耗油量剛好為0(除非此時的速度已超過上限),并將它們刪去,然后對于剩下的路段,重新代入(*)式計算v,直到不出現(xiàn)耗油量為負(fù)的情況即可。當(dāng)然,如果在此過程中出現(xiàn)F0<0,就無解了。

            brackets:
            這個應(yīng)該不用再說了,直接看這里。

            rectangle:
            思想比較巧妙的話說……應(yīng)該枚舉線段,按照中點和線段長度進(jìn)行排序(因為兩條線段若能組成矩形的兩對角線,則它們必然等長,且中點重合),然后掃一遍,順帶枚舉就是了……表面上來看時間復(fù)雜度可能到O(N3)級別,其實根本無法出卡這種方法的數(shù)據(jù)……

            canon:
            這個沒什么好說的,就是硬推公式,結(jié)果為
            (C(2n, m) - C(2n-1, m/2)) / 2n + C(2n-1, m/2) (當(dāng)m % 4 == 0或3時)
            (C(2n, m) + C(2n-1, m/2)) / 2n - C(2n-1, m/2) (當(dāng)m % 4 == 0或3時)
            對于當(dāng)中的取模問題:加、乘直接取模;減法要在取模后判定是否小于0,若小于0再加上待取模數(shù);除法要轉(zhuǎn)化為乘逆元(反正這里的MOD都是質(zhì)數(shù)……)

            国产精品久久久久久久久免费| 久久综合精品国产一区二区三区| 久久婷婷五月综合97色直播| 精品久久久无码中文字幕| 亚洲国产成人久久综合一区77| 天堂无码久久综合东京热| 亚洲国产精品无码久久久不卡| 人妻精品久久久久中文字幕69 | 国产精品美女久久久久av爽| 亚洲国产成人久久综合区| 亚洲欧美日韩久久精品第一区| 韩国无遮挡三级久久| 人妻少妇久久中文字幕一区二区| 久久中文娱乐网| 国产精品久久久久久久久免费| 久久一区二区三区免费| 狠狠色丁香婷综合久久| 中文字幕无码精品亚洲资源网久久| 色成年激情久久综合| 无码久久精品国产亚洲Av影片 | 国产精品99久久久精品无码| 国产精品久久久久9999高清| 精品久久久无码人妻中文字幕| 亚洲人成网站999久久久综合| 国产午夜福利精品久久2021| 欧美熟妇另类久久久久久不卡 | 国产91久久综合| 国产精品久久久亚洲| 久久久久久午夜成人影院| 麻豆亚洲AV永久无码精品久久| 亚洲国产成人久久综合一区77| 国产精品成人99久久久久 | 国内精品久久久久久野外| 伊人久久大香线蕉av不卡| 无码人妻久久一区二区三区蜜桃| 国内精品久久国产| 亚洲精品午夜国产va久久 | 欧美黑人又粗又大久久久| 久久久久亚洲AV无码专区体验| 亚洲va中文字幕无码久久| 亚洲国产精品无码成人片久久|