你以为你CF过了四题

编辑于 2019-01-29 18:39

+ 关注

【题解】牛客寒假算法基础训练营4

Problem A

TAG：脑洞，博弈

这是一道经典的博弈问题。
~~可以使用动态规划来解决：dp[i][j]表示进行了 i 轮，从前面取走了 j 个时候的最大收益。这个老师上课的时候教过。~~

实际上，由于题面中的两个限制条件，可以得出先手有必胜策略：即选择所有的奇数项或者偶数项。

如果奇数项的和较大，先手就取第一个，这样每一次轮到后手都只能取到偶数项。反之亦然同理。
因此，作为本场比赛的签到题之一，直接输出Applese即可通过。

Problem B

TAG：构造，分类讨论

这道题的做法比较开放。只要按题意构造就好了。
大体思路参照下图。
图片说明
根据 n 和 m 的奇偶分类讨论。

特殊的边界数据：1行2列或2行1列的情况。

Problem C

TAG：搜索，模拟

BFS 求最短路。
注意点是状态要三维。d[x][y][0/1]表示在(x, y)处，属性为水/火的最短路。
按题意模拟，分类讨论转移即可。

Problem D

TAG：状态压缩，轮廓线DP

好多6x6被骗去写暴搜的.jpg。实际上6x6全是?的答案高达1e18.

解法一：By 野鸡验题人
用 dp[x][state] 表示考虑到第 x 行，该行填写的数字的十进制状态为state的方案数。
这样的复杂度有点大，但是由于题目中的要求和为素数存在很强的限制，因此可以先预处理出所有符合条件的一行的state以及每个state可以转移的状态。加上本题宽松的时限，足以通过。
当然第一维是可以滚动掉的（然而并没有什么卵用）。

解法二：标程
用 dp[x][state] 表示考虑到第 x 个格子，它所在的轮廓线上所有数字的十进制状态为state的方案数。其中state的最高位存它前一行的那一格，最低为存它前一列的那一格。
如图所示，这样状态的转移就是一个“带溢出的十进制左移并补上填的数字“。
当然第一维是可以滚动掉的。
图片说明

By另一个野鸡验题人：不滚动数组MLE了。

Problem E

TAG：数学，智商

一个比较显然的结论是，对于每一列，有 2n 种涂色方法。
我们可以发现，当确定了第一列之后，由于左右相邻不能同色，所以后面每一列的涂色方案也随之确定。因此答案就是 2n 。
注意本题的 n 为高精度，需要使用指数循环节降幂或者十进制快速幂。（或者python）

Problem F

TAG：图论，二分，拓扑排序

题意是想让大家判断有向图是否存在环。判断有向图是否有环可以使用拓扑排序。
但是不能每次加边的时候就进行判断。
由于不存在撤销操作，所以可以发现答案一定是一连串的Yes后再有一连串的No。
只需要二分最后一个Yes的位置，用拓扑排序/DFS判环即可。
（虽然卡了一部分乱搞的，不过还是有牛逼乱搞的过了……）

Problem G

TAG：图论，MST

看成一张图，就是把同类元素的试剂当作一个点之后，求这个图的最小生成树。
然后用你最喜欢的求MST的算法求解就好。注意判不连通的情况。

Problem H

TAG：组合，概率

枚举 Applese 的名次，分别计算概率。答案为：
$\sum_{i = 0} ^ {k - 1} \binom{n-1}{i} p ^ i (1 - p) ^ {n - i - 1}$
其中𝑝为随机到的数不大于 Applese 的概率。

预处理逆元递推组合数。

Problem I

TAG：思维，想法

可以认为插入和删除是等价的操作。想到这一点，这题就会好做很多。
如果这个串本身就是回文串，答案一定是Yes。
否则我们只需要考虑串中对称的位置不相等的两个字符，分别尝试把它们删掉后判断一下是不是回文的就行了。

Problem J

TAG：物理

温暖的签到题。

由余弦定理，合力大小为 $\sqrt{f_1^2 + f_2^2 + 2f_1f_2cos\alpha}$ 。

标程

2025最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(3) 回帖

加载中...

话题同步到我的动态回帖