Posted on 2012-04-24 21:25
Mato_No1 閱讀(847)
評論(0) 編輯 收藏 引用 所屬分類:
HNOI
【最近很想被各種省選題虐……于是，就開始找各種省選題……發現能虐本沙茶的實在是太多了（誰叫我是沙茶呢囧）】
homework：
很能令人想歪的題目……想到某種數論模型……
正解是遞推+矩陣優化。可以這么想，本題如果暴力遞推的話，設F[i]為1到i組成的數（具體的數，不是取模以后的結果，雖然這個值是無法存儲的），則有F[i]=(F[i-1]*10
T)+i，其中T是i在十進制下的位數，邊界F[0]=0。這個式子是可以矩陣優化的，矩陣為
10
T 0 0
1 1 0
1 1 1
則1*3矩陣[F[i-1], i-1, 1]乘以這個矩陣之后就是[F[i], i, 1]，然后對于各個T分開處理一下就行了……這里的取模完全就是個幌子……
（另外，矩陣優化遞推是一個很重要的專題……）
race：
（最近剛好在某MO神犇的資料里面看到了柯西不等式……發現此題可以用這個來搞……就囧掉了）
柯西不等式：(a
12+a
22+...+a
n2)(b
12+b
22+...+b
n2)>=(a
1b
1+a
2b
2+...+a
nb
n)
2 【*】，
等號成立當且僅當對于任意1<=i, j<=n, i≠j，有a
ib
j-a
jb
i=0，也就是(a
1, b
1), (a
2, b
2)...(a
n, b
n)這n個點共線。具體證明的話，把兩邊的乘法列成一個矩陣的形式，去掉主對角線（相同），把關于主對角線對稱的位置對應相減，得到類似叉積的平方和的形式即可。
對于本題，假設不考慮耗油量為負時取0的情況，設F0=(F-Σ(b*Li*Si))/a，則問題就轉化為求一組vi使得ΣLivi=F0且Σ(Li/vi)的值最小。這樣，可以設ai=sqrt(Li/vi)，bi=sqrt(Livi)，代入【*】式……傻眼了囧……不僅能得到最小值，還能發現取得最小值時所有的v都相等，且可以算出來……當然如果F0<0就無解了囧……
不過本題最囧的問題是對于耗油量為負的情況。最好的處理辦法是，如果按照【*】式得到的v值會導致某些s<0的路段耗油量為負，則對于這些路段單獨處理，使得它們的耗油量剛好為0（除非此時的速度已超過上限），并將它們刪去，然后對于剩下的路段，重新代入(*)式計算v，直到不出現耗油量為負的情況即可。當然，如果在此過程中出現F0<0，就無解了。
brackets：
這個應該不用再說了，直接看這里。
rectangle：
思想比較巧妙的話說……應該枚舉線段，按照中點和線段長度進行排序（因為兩條線段若能組成矩形的兩對角線，則它們必然等長，且中點重合），然后掃一遍，順帶枚舉就是了……表面上來看時間復雜度可能到O(N3)級別，其實根本無法出卡這種方法的數據……
canon：
這個沒什么好說的，就是硬推公式，結果為
(C(2n, m) - C(2n-1, m/2)) / 2n + C(2n-1, m/2) （當m % 4 == 0或3時）
(C(2n, m) + C(2n-1, m/2)) / 2n - C(2n-1, m/2) （當m % 4 == 0或3時）
對于當中的取模問題：加、乘直接取模；減法要在取模后判定是否小于0，若小于0再加上待取模數；除法要轉化為乘逆元（反正這里的MOD都是質數……）