竞赛讨论区 > 【题解】吉首大学第九届"新星杯"大学生程序设计大赛
头像
Uncle_drew
编辑于 2020-01-05 17:27
+ 关注

【题解】吉首大学第九届"新星杯"大学生程序设计大赛

A、 被诅咒的WWT

枚举,五重循环,或者图片说明 打表距离能到的点。

B、 Y 老师的井字窗

直接开 的数组会爆内存,考虑只为每块木板单独的定义一个计数变量后,输入时相应累加即可。

C、 始战

题目是说在第一天每个诸侯会对自己的上下左右四个方向进行霸占。如果有一个地方同时会被两个诸侯霸占,那么这个地方就是战争发生地。所以我们只需要把每个诸侯的上下左右四个方向进行标记。如果有一个空地,同时被两个地方所标记,那么这个地方的位置就是战争发生地。

D、 秒速五厘米

因为最后要取整,所以我们直接加起来去除,我们二分出速度,然后遍历算出时间,看是否符合,然后最后算出最小时间

E、 冬天怎么能够没有辣条

直接按题意模拟即可

F、 陪你去流浪,踏遍那四海八荒

题意明了,唯一的坑点在于你是否能够发现图片说明 是不是个质数,mod 其实不是个质数,178 之后的阶层取余mod 就是为0 了。所以我们只需要暴力计算前178 项即可。

G、 芒砀山的神秘数字

我们很容易就可以看出选择上面的那个的字符串的子序列时如果长度超过下面这个一定可以选用,同理长度短于的肯定不能用,长度大的部分我们可以用组合数来进行求解
所以难点就在于我们要求序列长度等于的时候有多少个序列满足要求,因为种数太多我们可以想到应该要用dp 来优化复杂度,想一下,如果当前某一位低于了,那么这个串就肯定比他小了
所以我们要计算两种状态,到当前位置依然相等的个数 0 ,当前已经大于的序列个数 1

当前第一个串的第图片说明 位匹配第二个串的第图片说明 位第图片说明 种状态时有多少个序列
最后 就是长度相等时的答案
当然这里需要降维,把第一维去掉,我们就可以采用01背包 那种做法,把第二种循环遍历顺序取反即可
最后我们还要判断以0 开头的情况,这样是不合法的,但是我组合数时计算了值,所以我们最后还要去掉

H、 小李堆积木

直接按题意模拟
每次从第一阶段推到第图片说明 阶段即可

I、 Y 老师的乐高小镇

将每条街道中相应的小镇数量看作二进制数的每一位,明显地,直接组合图片说明 里对应二进制的每一位是最佳策略,即数图片说明 化为二进制后有多少个 图片说明

J、 小阳排队

细心能发现其实就是求一个最长连续的子序列
例如
1 5 6 2 4 3
我们答案应该是 图片说明
因为我们相当于找到最长连续的,这里是 1 2 3 然后 把 4 5 6插到右边因为4 5 6都没在3后面,所以要操作插到右边
转移方程 ;

K、 小阳数数

其实就是0-9 十个数字有关,我们可以遍历一遍所有字符串,建个图,然后dfs 跑联通快即可,或者暴力去处理计算联通块这一部分

L、 LeeLdler喜欢下棋

dfs 模拟下两步,或者暴力模拟,先判断LeeLdler 是否能动以及满足下棋规则,是否能动判断对方棋子是否构成三个,或者棋盘是否已满,是否满足规则判断ox 的棋子数量,这些情况都是 。对于其他情况,考虑绝杀,即构成两个两个。值得一提的是,如果刚开局棋盘人机已经构成两个且LeeLdler 未构成两个,那第一步必须去堵人机。

M、 来来来 比比咱谁更聪明

当瓶子剩余容量为0 时,此时要倒水的人必输,往后递推,如果有人可以倒完水之后达到必输点,那么此点为必赢点,如果没办法倒完水之后达到必输点,则此点也为必输点。然后一直往后递推。

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐