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]*10
T)+i，其中T是i在十進(jìn)制下的位數(shù)，邊界F[0]=0。這個式子是可以矩陣優(yōu)化的，矩陣為
10
T 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)此題可以用這個來搞……就囧掉了）
柯西不等式：(a
12+a
22+...+a
n2)(b
12+b
22+...+b
n2)>=(a
1b
1+a
2b
2+...+a
nb
n)
2 【*】，
等號成立當(dāng)且僅當(dāng)對于任意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個點共線。具體證明的話，把兩邊的乘法列成一個矩陣的形式，去掉主對角線（相同），把關(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ù)……）