T1 送分题

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

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

当 $n\ge 20180001n\; \ge \; 20180001$ 时，答案永远是 $2018201720182017$。

T2 ***游戏

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

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

T3 谁是神射手

先手获胜的概率是：先手和后手均失败了$nn$次后先手成功。即

$\alpha {\sum }_{i=0}^{\mathrm{\infty }}(1-\alpha {)}^i(1-\beta {)}^i=\frac{\alpha }{1-(1-\alpha )(1-\beta )}\backslash alpha\; \backslash sum\_\{i=0\}^\{\backslash infty\}(1-\backslash alpha)^\{i\}(1-\backslash beta)^\{i\}=\backslash frac\{\backslash alpha\}\{1-(1-\backslash alpha)(1-\backslash beta)\}$

同理，后手获胜的概率为

$\beta {\sum }_{i=0}^{\mathrm{\infty }}(1-\alpha {)}^{i+1}(1-\beta {)}^i=\frac{\beta (1-\alpha )}{1-(1-\alpha )(1-\beta )}\backslash beta\; \backslash sum\_\{i=0\}^\{\backslash infty\}(1-\backslash alpha)^\{i+1\}(1-\backslash beta)^\{i\}=\backslash frac\{\backslash beta(1-\backslash alpha)\}\{1-(1-\backslash alpha)(1-\backslash beta)\}$

需要注意特判公比为 $11$ 的情况，否则可能因为除以 $00$ 造成 Wrong Answer。

T4 明七暗七

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

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

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

T5 Applese的超能力

判断$n\mathrm{-}1n\; -\; 1$ 能否被$m\mathrm{-}1m\; -\; 1$整除即可。

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

T6 BFS

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

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

T7 CSL分苹果

做一个容量为$\lfloor \frac{\sum w_i}{2}\rfloor \backslash left\backslash lfloor\backslash frac\{\backslash sum\; w\_\{i\}\}\{2\}\backslash right\backslash rfloor$的$0101$背包即可得到 Wavator 分到苹果。

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

T8 CSL的校园卡

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

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

这样的空间复杂度是$O\left(2^{nm}{n}^2{m}^2\right)O\backslash left(\; 2^\{nm\}\; n^\{2\}m^\{2\}\backslash right)$。如果搜索的处理不合理或者数组开多了一点（如果是高维开多了一点可能就不是一点了），可能会导致 Memory Limit Exceeded。

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

3 3

XOX

OSO

XOX

T9 新建MIcrosoft Office Word文档

可以用一个来维护可用的编号，按题意模拟即可。

T10 方格填色

每列有 $2^{m}2^\{m\}$种状态；容易想到使用状压DP。

令白色为 $11$，黑色为$00$。$d{p}_{i,j}dp\_\{i,j\}$表示前$ii$列，最后一列的填色方法为$jj$的方案数。

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

很容易可以写出$O\left(n{4}^m\right)O\backslash left(\; n4^\{m\}\; \backslash right)$的算法。

但是这里的$nn$ 很大，需要使用矩阵快速幂加速递推。比如$2\times n2\times n$的情况：

他疑问可加以下交流群（加入一个即可啦~）

牛客多校算法训练营1：453799454

牛客全国算法训练营2：330766563

牛客多校算法训练营3：934889305