Posted on 2012-05-09 22:58
Mato_No1 閱讀(1757)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
CTSC
【首先熱烈祝賀一下進(jìn)入國家隊(duì)的神犇：
chnlich
sevenkplus
zw7840
plokzfadai
（雅禮再次屠場不解釋)也祝賀一下雖然未能進(jìn)入國家隊(duì)，但已經(jīng)足夠虐爆全場的神犇：
WJMZBMR
s-quark
】
CTSC2012得出的最主要的幾條道理：
（1）實(shí)力強(qiáng)≠比賽成績好，實(shí)力弱≠比賽成績差；
（2）現(xiàn)在所有的比賽都不是比誰得分多，而是比誰丟分少；
（3）每個(gè)人都會(huì)遇到頹廢、迷茫、進(jìn)步慢的時(shí)期，關(guān)鍵是如何尋求出路，以及如何通過自己與外界共同的力量來解決；
（4）在將某個(gè)東東講給別人之前，首先要考慮一下自己是否熟練掌握了這個(gè)東東；
（5）在分析問題，解決問題的過程中，可以通過很多另類的途徑，找到又好想又好寫的辦法。
部分總結(jié)：
【一試】
showhand：
可以將所有的牌型（C(52, 5)=2598960種）全部存儲(chǔ)起來，按照題目中的規(guī)則進(jìn)行排序，存儲(chǔ)在一個(gè)線性表里，然后，枚舉A的所有可能的牌型，從上面的線性表中找到比A大且不和A共用同一張牌的方法總數(shù)，可以使用容斥原理（方法：設(shè)F[i][t]為牌型i及比i大的牌型中，與i共用牌的屬性壓縮值為t，0<=t<=31表示5位二進(jìn)制數(shù)，對(duì)應(yīng)位為1表示與i共用，0表示不共用）。而對(duì)于B的某些牌一開始就被定死了的情況，用求出的F類似辦法也可搞；
shortest：
很好的一道提交答案題。
先說一下各個(gè)測試點(diǎn)的特點(diǎn)：
點(diǎn)1：N<=20，K=10，從1到N的最長路徑若要成為最短路徑，需要?jiǎng)h掉至少11條邊；
點(diǎn)2~3：N、M較大，K較小（分別為20和10）；
點(diǎn)4：N<=20，邊可以想腫么刪就腫么刪；
點(diǎn)5~7：原圖分為若干塊，每塊的點(diǎn)數(shù)相等且較小（分別為20、10、10），相鄰兩塊之間有唯一的一條邊相連，點(diǎn)5的邊可以想腫么刪就腫么刪，點(diǎn)6、7刪邊有限制；
點(diǎn)8：是一個(gè)完整的100*100的網(wǎng)格，邊權(quán)均為1，從左上角走到右下角；
點(diǎn)9：是一個(gè)2*1000的網(wǎng)格，中間隨機(jī)刪掉了約20條邊，邊權(quán)是隨機(jī)值，從左上角走到右下角；
點(diǎn)10：圖中存在一條從1到N的鏈（稱為主鏈），附加了一些邊，邊可以想腫么刪就腫么刪。
解決辦法：
點(diǎn)1：搜索（當(dāng)然，狀壓求出最長路+將這11條邊列出來，枚舉保留哪條邊，可以得到一個(gè)僅比最優(yōu)解小1的解）；
點(diǎn)2、3：貪心+隨機(jī)化（每次找一條從1到N的最短路，從中隨機(jī)刪掉一條邊，這樣做K次就得到一個(gè)方案，然后多次隨機(jī)化后取最優(yōu)方案即可；對(duì)于點(diǎn)2，隨機(jī)幾千次就能找到最優(yōu)解了，對(duì)于點(diǎn)3，RP好的話需要隨機(jī)1000W次，RP差的話可能需要上億次，估計(jì)總共得耗掉1h以上，因此得早寫）；
點(diǎn)4、5：狀壓DP；
點(diǎn)6、7：塊內(nèi)狀壓（當(dāng)然由于只有10，暴搜也可），塊之間DP（設(shè)F[i][j]為前i塊刪掉j條邊的最優(yōu)解……）
點(diǎn)8：直接構(gòu)造……（可以構(gòu)造出一個(gè)只有一個(gè)點(diǎn)走不到的方案，且可以證明不存在走完所有點(diǎn)的方案）；
點(diǎn)9：搜索/DP + 構(gòu)造（具體的實(shí)現(xiàn)細(xì)節(jié)比較難搞啊囧）；
點(diǎn)10：這個(gè)是Hamilton路徑問題，NPC的，因此這個(gè)點(diǎn)根本木有辦法搞囧……（當(dāng)然或許有某些經(jīng)過優(yōu)化的搜索能較快找到解）
【二試】
cheat：
80分做法1：首先將所有的字符串拼在一起，中間依次用不同的分隔符隔開，然后對(duì)這個(gè)大串求后綴數(shù)組求出height，然后就很容易求得每個(gè)屬于待查詢串部分的位置i與模板串的最大LCP（直接正著掃一遍、反著掃一邊即可，注意邊界）長度，設(shè)為D[i]，接下來就是二分L然后DP了：F[i] = min{F[i+1]+1, F[j]}，其中0<=i<len，i+L<=j<=i+D[i]，邊界F[len]=0，這個(gè)東東顯然是可以用線段樹優(yōu)化的。總時(shí)間復(fù)雜度O(Nlog2N)；
80分做法2：可以發(fā)現(xiàn)，對(duì)于同一個(gè)待匹配串，隨著i的減小，(i+D[i])是不增的，因?yàn)镈[i]最多比D[i+1]大1……這樣可以用單調(diào)隊(duì)列進(jìn)行優(yōu)化，而不需使用線段樹，總時(shí)間復(fù)雜度降為O(NlogN)，但是由于后綴數(shù)組常數(shù)過大，還是只有80分囧……
100分做法：將后綴數(shù)組改為后綴自動(dòng)機(jī)（詳見WJMZBMR空間）……
（另外講題的時(shí)候某神犇說可以把后綴數(shù)組的長度減半，從而結(jié)合單調(diào)隊(duì)列得到90分，不過本沙茶木有理解到底是腫么搞的囧……）
rev：
點(diǎn)1~2：N=1或M=1，可以暴力搞（要開-O2啊啊啊啊啊啊啊啊啊啊……否則慢死）
點(diǎn)6：整個(gè)矩陣從左到右、從上到下都嚴(yán)格遞減，只要滿足坐標(biāo)限制的都是逆序?qū)Γ梢灾苯佑?jì)算得到；
點(diǎn)7：只有5和9，且相鄰的兩個(gè)格子分別是5和9（其實(shí)可以把5和9看成0和1，相當(dāng)于黑白染色），可以通過枚舉不同情況分類討論計(jì)算得到；
點(diǎn)8、9：N=M=1000，詢問的區(qū)間都是從頂?shù)降椎模梢酝ㄟ^預(yù)處理得到一個(gè)O(N2M)近似暴力的算法，在約5min內(nèi)跑出（開-O2）；
點(diǎn)10：N=M=80，隨機(jī)數(shù)據(jù)，可以直接暴力遞推得到；
點(diǎn)3~5就比較難搞了，本沙茶至今木有搞懂囧……