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