Posted on 2012-05-09 22:58
Mato_No1 阅读(1723)
评论(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就比较难搞了，本沙茶至今木有搞懂囧……