竞赛讨论区 > 【题解】牛客小白月赛7

【题解】牛客小白月赛7

头像
牛客网小运营
编辑于 2019-04-11 18:59:27 APP内打开
赞 0 | 收藏 0 | 回复1 | 浏览1143

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 送分题

直接把代码复制提交并不能通过此题。

但是如果你仔细分析代码的递归过程,可以发现:

当 n ≥ 20180001 时,答案永远是 20182017。


T2 ***游戏

将必胜态和必败态的转移用 DP 递推或者记忆化搜索出来即可。

一个必败态的后继状态全部是必胜态,一个必胜态的后继存在比败态。


T3 谁是神射手

先手获胜的概率是:先手和后手均失败了 n 次后先手成功。即

 

同理,后手获胜的概率为

                    

需要注意特判公比为 1 的情况,否则可能因为除以 0 造成 Wrong Answer。


T4 明七暗七

考虑这样一个问题:在 [1,n] 内含有 7 或者能被 7 整除的数有多少个。

这个问题是经典的数位 DP 问题,将状态设计成三维即可。

那么对于原问题:若 [1,m] 中要拍手的有 t 个。设答案为 x,则 x 是第一个满足 [1,x] 中恰好有t + n 个的数。显然 x 是具有二分性质的。


T5 Applese的超能力

判断 n − 1 能否被 m − 1 整除即可。

需要注意特判 n = 1 和 m = 1 的情况。


T6 BFS

把大小写转换一下以后,暴力匹配即可。

std::string::find 了解一下。


T7 CSL分苹果

做一个容量为的01 背包即可得到 Wavator 分到苹果。

数据范围较小,各种正确的姿势都可以过。

T8 CSL的校园卡

BFS 搜索即可。难点在于合理的状态表示。

d[S][x1][y1][x2][y2] 表示目前已经走过的坐标集合和两个人对应的坐标的状态的最短时间。其中S 需要使用二进制状态压缩进行存储。转移则需要枚举两个人的 4 × 4 = 16 种走法。

这样的空间复杂度是 。如果搜索的处理不合理或者数组开多了一点(如果是高维开多了一点可能就不是一点了),可能会导致 Memory Limit Exceeded。

可以借助以下例子来理解为什么其他的状态表示是不合理的。

3 3

XOX

OSO

XOX


T9 新建MIcrosoft Office Word文档

可以用一个 std::set<int> 来维护可用的编号,按题意模拟即可。


T10 方格填色

每列有 种状态;容易想到使用状压DP。

令白色为 1,黑色为 0。表示前列,最后一列的填色方法为的方案数。

转移就是枚举下一列的状态:如果按为与为 0(左右相邻不能同时为白色)且按为或不为 0(相邻两列不能全部为黑色)即可转移。

很容易可以写出 算法

但是这里的 n 很大,需要使用矩阵快速幂加速递推。比如 的情况:



其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

1条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐