Mutual Training for Wannafly Union #1

比赛链接

题外话:

wannafly union:可能有的学校不能很好得传承……可能某一时间可以进过两三次final ……但是final队过后,这个学校就退出了历史的舞台……

 

说实话我依然记得我入学那年,也就是14年,看到了华科又一次进final,然后15年仿佛已经开始走下坡路,到了16年,icpc连快银都没有….见证了hust的衰落,我的内心是格外凄凉的。

而又不仅仅是见证…内心是有些愧疚的….总觉得自己没能把某些传统传承下去。。。。

曾经我以为学校的荣誉轮不到我去争取,毕竟我实力很弱,高中noip虽然有全省第二…但是大弱省….其实我当年只有275分…

14级的一队…pyy+zk+tm,三个人都是初一就开始参加比赛了….而且湖南+广东+安徽….

其他人,也至少比我发展均衡….

所以之前想着…弱鸡如我好好提高学校的下限就好了….

但是现在发现并不是那么一回事…

其实每个人…都是和学校相关的….

即使最后轮不到我…但是应该仍然有这个想法才对吧….

 

好了正题:

这次比赛只做出了三道题,A题之前遇到过,当时不会,忘记补了。目测E题也可以补,不过明天约了妹子自习估计要早睡,所以考完试再说吧。

A:

题意:有一个3*n的maze,一个人初始在最左边的某个格子里(3个中的一个,用s表示),然后有若干由大写字母组成的火车…

每一次运动中:人先向右移动一个格子,然后选择不动,或者向上或者向下(具体取决于现在处在3行中的哪一行),之后每列火车向左移动2个格子。如果某个时刻人和火车位于同一个格子,那么人就狗带了。人的获胜条件是到达最右边。

思路:比赛的时候脑抽。。。竟然觉得是指数模型。。。。然后就觉得想错了orz

这道题可以考虑物理的相对运动,我们可以认为火车是不动的,而人时先向右一个格子,然后换行(或者不换),然后再向右两个

这样直接bfs搞一下就好咯。。。。果然是水题。。。。

 

B: 题意:一个字符串,长度最长为10,由小写字母组成,恰好插入一个字母使其变成回文串的方法…

思路:一开始竟然傻傻得分情况讨论。。。。各种漏。。日。。。后来一看数据范围。。。直接暴力。枚举插入的位置和插入的字母。。然后check。复杂度。。10×10*10*26.。。

 

D:n*n的格子,初始白皇后在(1,1),黑皇后在(1,n),其他点被士兵覆盖(士兵不会动。。。)皇后每次可以横竖或者对角线,走到一个有士兵(或者地方皇后)的位置并吃掉。。。(每次移动必须吃掉士兵或者地方皇后)

白皇后先走,问双方都最优策略。。。谁必赢。。如果白必赢,输出第一步的走的方案。

思路:其实算是构造题。。。?手画一下发现。。。只和奇偶性有关2333,结论很容易发现。。

 

F:题意:猜数游戏。。四种猜法。。大于,大于等于,小于,小于等于。。。并且给出每次猜得对还是错。。。问最后这个数是否存在。。

思路:维护一个L,R。。。最后看L<=R是否成立即可。。。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz