CCPC2015小记

这周末(Oct 17-18 2015)，第一次参加了ACM类的比赛，感触颇深，小记一番。

这次比赛是第一届的ACM国赛，充满着对目前ICPC区域赛的怨念（开幕式上各种高级黑）不过也造福了长春赛区的ACMer们（榜惨不忍睹，好可惜我们没有拿到长春的名额啊），和我土力学实验、校庆志愿者、毛概实践课、计算机等级考试都重起来了，一天之内怒请五个假。晚上和张老师去火车站和阿洁哥良哥他们汇合，然后就是不出意料的火车晚点，不出意料的CCPC专列（上海到南阳的K1106），不出意料的上铺很冷，不出意料地发现自己身高不咋地。
早上的Face++神牛们的会被我们睡过了，下午开幕式之后直接热身赛，三条题目。A题Googol String（这次比赛Google命题）意思是要找一个特定生成的二进制字符串序列的第Googol项。这条我一开始的思路是把它的每一项理解成一个序列，然后求出他的通项公式。后来良哥找到了循环节

(001 0) (110 0)

顺着这个思路想下去将每组中的第四项提出发现依然具有相同的循环节(001 0) (110 0)。这条AC。
B题New Years Eve给出了如下的酒杯排布

第1层
	1
第2层
		1
	2		3
第3层
		1
	2		3
4		5		6

这条最后硬上模拟做了出来。
第二天是正式赛。12条。签到题两条L和A。L的意思是一串瓶子都相同，里面的东西不同，问如何用最少的瓶子去区分。答案显而易见，就是把瓶子摆成一个对称的形状，这样无论拿正拿反都一样了。如

D-C-B-A-B-C-D

答案就是2n+1。不过因为我们当时题目意思没理解对，导致一直不敢交，白浪费了20min。
A题就是两个2x2矩阵

a b  e f
c d  g h

叫你判断旋转之后是否相同，其实只要硬写四个if就好了。当时搞了两个数组，反而复杂了，WA了两次。不过因为这条我体验了一把主敲和现场A题的滋味。爽。
下面是H，二阶数独，阿洁哥A了。我和良哥讨论CDG三条。
C题是在一个1000长度的串N中找出所有的上升子列，问有多少种方法，这一条现场把case由10个增到了100个，按照朴素的N³算法，达到了10¹¹的计算量，后来良哥又想了个N²LogN的算法，不过还是有10⁹的量，良哥觉得并不能在1s内解决（不过仔细优化下应该还是可以的，我记得当时对面的陕西师范大学的人说这条题目卡常数，应该他们也是这个复杂度类的），不过题解说是N²复杂度就可以了，这具体怎么做，还不是太明白的。
D题是一个扩展的背包问题。意思就是把一些线段（golden stick）去覆盖另一条线段（container segment），不过多了一个限制条件，也就是这些golden stick可以有一部分超出container segment的外面，只要整个的重心在里面。如图所示： 这条良哥先提出一个想法，
G是这次比赛最蛋疼的一条，因为它真的很简单，我们的思路很清晰，然后中坑的也是这一条，WA了7次。先说题目就是围棋，问走一步能不能吧对方的棋子吃掉。这一条的思路就是BFS/DFS找出所有的连通分量，然后逐个棋子检测有多少个“气”。我们错在后来的优化上面，忽略了多个棋子可能公用一个“气”的情况，直接把每个棋子的“气”加起来看大于不大于1。
赛题说完了，谈一下比赛的一些感受。
首先是学习到了一些经验，比如说弱队看着榜选题A，比如说ACM的一些专用的调试工具，比如说切题的一些技巧。
其次是失败的原因。首先我们学校这方面不是很强，对，不过这次也不至于输的这个憋屈吧？南大女队都比我们高到不知道哪里去了。究其原因我觉得我们还是在简单题上，没有做好，难题，我们确实不会，不过别人也不会，6A就可以上银牌区，4A就可以上铜牌区，而AGHL都属于签到题，CDK也是属于有时间可以想出来的题目，有难题，像BIJ，但是全场AK也就SJTU一个。所以我们差在哪里。签到题L，别人2min过，我们20min才过，为什么呢？只是一个对称的构造，原理很简单，但是我们一直在怀疑自己的判断 。接下来签到题A，WA了三次？为什么呢？代码写错了。为什么代码写错了呢？一个简单问题，用了一个比较复杂的方法来做（用了数组，WA的话可能是wrap上问题）,换成简单的实现就可以了。其实题目没这么难。

最后给出zhihu上面的评价 http://www.zhihu.com/question/36617747?rf=36617203
–未完待续–
PS 其实我只是先先看看这个模板效果2333
2016-12-04 我决定不续了，马上都退役了