查看文章 |
ZOJ Monthly, February 2010
这次月赛又是和LCC以及AC两位牛组队的。。 不过遗憾的是。。。这次被完虐了。。qzc神牛单挑以及qinz阿姨单挑都将我们三人的组合给狠狠的踩掉。。。 于是在过了一天之后在这个即将到达8个2的珍贵时刻(2010/2/22 22:22)写下这个总结。。
I题Prison Break：表示没有看题，LCC秒掉了。 F题Make Pair ：水题。排个序扫一遍即可。不过不知道为什么那么多人挂。而且也不知道为什么AC牛最开始也挂了那么久。 B题Cookie Choice II：这个规模。。这个数据量。。脑袋卡了很久才想到用滑动窗体： 维护窗体[i,j]，始终保证窗体内的每一种物品总数大于等于下界。 这是最原始的想法，但是这个窗体的条件很有可能是不能保证的，于是可以折中一下，就是每一次固定窗体左端点的时候，枚举物品，将右端点移动到达到该物品下界的地方，如果期间遇到某一个物品超出上界就跳出枚举物品的这重循环，否则继续直到所有物品满足。如果所有物品都能够满足个数在要求的范围之内的话就更新最优值。 写完之后完全不敢交。。交上去挂了。。于是查代码。。看了好几遍之后才确定了正确性，不过还是在又挂了一次之后才过。 E题Mahjong：这题也是水题，只是我们最开始没有发现。。可是当我写完之后居然wa了。郁闷之中我妈又来叫我吃饭了，心里烦得慌。最后顶住了压力，调试了十多分钟之后终于过了。 G题More Sweets!：概率题。组合数学，题目很显然。给出n种物品，每次可以取一个，问至少取多少个能保证会出现两个相同的，再问至少取多少个能保证所有物品至少出现一次。第一个问题就是鸽笼原理，显然就是n+1了，第二个也很简单，要保证所有物品都取到，那么就是单独挑出总数最少的那个物品最后取，其他的先拿完，这样就肯定可以保证每种物品都至少一个。之后还要输出取这么多才出现那些情况的分别得概率，这也不难，可是令人郁闷的是居然是输出概率中二的幂次。。。样例看了老半天没看懂。。。LCC比赛时过了这题，我下来之后听他讲了很久才理解了概率输出的方式。。。真费神。。。 A题Connecting the Segments：这题上来就被qzc神牛给秒了，于是很早就将注意力放过去了，本来想法不多的，后来LCC说了个DP的方法，觉得很逼真，只是需要的东西有点多：SA+RMQ+DP+ST。。。当时写玩过样例之后就交，居然wa了，囧然发现调试信息没有删完，果断改掉交就过了。。。可是下来了LCC再次问我那题的时候才发现当时的那个DP虽然是正确的可是我的那个写法是错误的。。。我在求最长回文的时候只更新了最后一个端点，而没有对其它点进行处理。很奇怪的是居然过了。。。 记得比赛结束的时候AC说qinz阿姨用SA+贪心过的A题。由于贪心的正确性（这个应该不需要我证明吧），我的那种错误的做法侥幸“正确”了。。 D题Fall the Brick：标准的线段树，不过开场的时候我看了感觉有点恐怖没有拍，后来过了A题后LCC去拍了，他说要拍一个小时。。结果真被他说准了，他确实搞了那么久才过。。 比赛完之后晚上我去做那题，发现那就是个区间更新区间和查询的线段树，晕了很久才写过去。。。 C题Crack：这题很有意思，不过数据水了。。我的做法是先KMP一次然后找到和长度为N的串匹配的最长的串的结束位置，我们用数组L存下来，可以证明将N的串循环右移后的串和长度为M的串的最长匹配的结束位置肯定出现在L之中。于是在第一次KMP之后将N的串循环右移N-1次，每一次根据上一次的最长匹配前后移动来得到当前的最长匹配。 比赛完之后qinz阿姨要了我的代码，结果在他的慧眼之下发现了我的程序的问题，用一个很简单的数据将我的代码给cha掉了。。。确实，那个数据的情况很简单，但是我当时就是没有考虑。本来我在代码中有一个剪枝使得我的算法的复杂度降到了O(n+m)，也就是KMP的复杂度，可是由于这个数据所代表的情况的存在，我的那个剪枝完全错误了。。于是我上面的那个算法的复杂度就超出预期了。。还好数据不是很强大。。所以C题其实是被我给水过去的，不过貌似很多人也是用hash去水的。。 不知道正确的做法是啥，但是有一个很好的方法就是正反KMP各一次，其实在比赛过程中LCC说了这个做法的，我当时就觉得很逼真，就放掉了手中的上面那个暴力的算法，可是写完之后却发现一直过不了样例，其实当时已经很晕了（本来学KMP就很容易晕的），所以果断放弃了继续用我之前的那个代码，还好在最后十分钟水过去了。。 后来也就是今天下午终于用正反两次KMP过掉了。。不过貌似还比我上面那个暴力代码慢，杯具。。。
这次月赛是我和LCC以及AC组队的最后一次，过几天就开学了。这一个月和这两位神牛组队比赛学习到了很多东西，在和他们的配合之中自我感觉也长进不少。这一个月来的几次TC都做的还挺好的，除了最后一次的比较杯具外，其他几次都是暴涨状态，这肯定和这一段时间的比赛训练分不开的。 LCC的聪明让我折服，相信这位大二的神牛会有很好的发展。同样，AC神牛在数论上的造诣是少有人可以比拟的，以后还要多多向他请教。而且，这两位牛十分好学，学习起来也很快，这让我这个菜鸟十分佩服。期待他们今后比赛的优异成绩，同样，我也期待与他们的下次合作~~~ |
