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