第八届湖南省大学生程序设计大赛 - 笑不语@USC 随笔,感想,解题报告
第八届湖南省大学生程序设计大赛原题+最终榜单: http://pan.baidu.com/share/link?shareid=87473&uk=1124339433/
南华大学终于在省里拿到了一等奖！继续向着省内一流队伍迈进！
其实这一向水题的手感都怪怪的..包括赛前一天的试机..状态一直都不好..直到试机中有道题..晚上想通了..瞬间感觉豁然开朗...
解题报告1 - 热身赛某题:
题意回顾:
此题给定一列数..个数最多10^5..codeforces风格...不断询问中间的段有没有那个数出现的次数大于这段长度的一半...如
2 1 1 3 3 3 4
问 1 3 ... 回答1...因为1的个数大于3/2....
问 2 6 ... 回答3...因为3的个数大于5/2.....
但问 1 2 ... 回答-1..因为没有那个数的个数大于2/2...
解题思路:
做三次kth number...如果在长度为len段中有数k出现的次数大于len/2..那么在次数必定是这段的(len/2+1)大数...所以可以用kth number快速求出这个数是什么...但是这个数也不一定是符合要求的...但如果有符合要求的一定是这个数...如 1 2 3 ..这段长度为3的串中本身就没有符合要求的....所以第一次用kth number确定这个数.还要判断此数是否符合要求..再用两次( 二分+kth number) 确定这个数的上下界..以检验是否长度>len/2....
正式比赛我们队发挥超常...从开始到结束没有掉出过前5..并且大部分时间排在榜首...比较霸气啊....
A,B,C题语言题...D题用JAVA可以秒...可我们压根就没准备JAVA!!!...E题字典树...F题和2008年北京rigional一题雷同..状态DP也好..最小生成树也好..各种水了...G题数学题.虽不明但觉厉...H感觉上好做.数据量小..但没一个队碰....
解题报告2 - I
本题只有4个队做出来...呃..我觉得还简单吧...由于'O'的个数最多5个..又'O'移动一次后不能移了...所以状态总数最多4^5=1024种..很弱嘛..DFS+BFS..对于一张地图..先将所有的'O'也看成'X'...用BFS遍历能遍历的点..拿完能拿的'C'..然后来移动'O'...而当前'O'能移动的条件是一侧的点当前遍历到了..而另一侧是'.'时..可以试着移动..就带着更新的地图进入下一层搜索..由于最多5个石头..所以搜索的深度最多5层...
解题报告3 - J
本题我的方法很不科学啊...最坏的情况可能达到O(n^3)...还好数据弱..状态一维的dp...在上面的串中做dp....dp[i]..代表该数为末.最长能符合题目要求的长度..初值为0...从下面串的第一个数扫到最后一个数..每次找到上面串的相同数..假设其在上面串的一个位置为k...那么再扫描上面串的1~k-1..找到其数值小于a[ k ]..并且dp值最大的数..更新dp[k]..但由于这个数在上面串可能不止一个..所以都要更新..如果此时不做任何优化..裸的O(n^3)了..可以加个优化..将所有上面串种所有相同的数用一个next数组连起来..但是要是上下两串全都是相同的某个数..长度都是1000..那么我的算法也将达到O(n^3)..超时..不过还好没有这样的数据...
后面的题也没想法了...总共做出7题..
最后一小时..冠军还是没守住..湖南师范的Smile 与 国防科大的 ALPC_MAGI 分别夺得冠亚军..咱们队第三名..不过已经很大的突破了！！
下周要去天津了..南华第一次进入现场赛..也是我ACM/ICPC最后一场正式比赛了..期待完美收官！！
