第八届湖南省大学生程序设计大赛 - 笑不语@USC 随笔,感想,解题报告

第八届湖南省大学生程序设计大赛 - 笑不语@USC 随笔,感想,解题报告

第八届湖南省大学生程序设计大赛原题+最终榜单:  ​​ -  热身赛某题:

题意回顾:

此题给定一列数..个数最多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最后一场正式比赛了..期待完美收官！！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。