【CSDN竞赛】第八期解题报告

这应该是站内相对详细的解题报告吧。
转载思路请@本人。

感想

关于自己

这一次又考差了（指第二）
由于第一题调了半天没调出来，所以没拿满分，只有$90$
总的来说，时间安排不合理
期待下次各位dalao能手下留情留我一个第一

关于平台

这次的题目质量说不清楚（拉掉了许多人）
有些地方描述不清楚/错误，如第二题数据范围应该是$n\le 10^3$
第一题是真的奇怪，本人用了$Java$、$C$、$C++$全部过不去，唯独$C++$拿了$90$
有时候的自测调试会把警告也提示错误，导致本来可以运行的程序只能在保存运行处提交
并且有些本来时间复杂度很低的程序莫名其妙运行无结果，也没有提示时间超限，非常疑惑
此外，由于本人的考试报告空白，所以无法提供当时的考试代码。
总而言之，系统有提升，但不多；题目有改进，但也不多。

第一题 （难度：入门但是不完全入门）

题目描述

给你两个字符串$S$，$T$，让你从$S$中剪下字符组成$T$，问是否可行。

90分做法

发现数据范围很小，就直接暴力匹配。
对于每一个$T$串中的字母，我们都在$S$中找其对应的字母，然后删除。
注意只考虑有效字符。
如果找不到，就输出$No$。否则输出$Yes$。

100分做法

我也不知道，也许是什么奇怪的判断之类的。
听说不能要空格

第二题 （难度：中等）

题目描述

给定一个只包含大小写字母的字符串$S$，你现在可以往字符串的任意一个位置插入字符，并且可以插入若干次，问最少插入多少次可以使得$S$变为回文串。

100分做法

因为回文串是从两端到中间都相同，所以我们考虑从两端开始匹配。
设$d{p}_{i,j}$表示$[i,j]$没有匹配的最小插入字符数。
转移：
当$S_{i-1}=S_{j+1}$时，可以直接匹配：
$$d{p}_{i,j}=min(d{p}_{i,j},d{p}_{i-1,j+1})$$
对于任意情况，都可以添加字符来匹配任意一端：
$$d{p}_{i,j}=min(d{p}_{i,j},min(d{p}_{i-1,j},d{p}_{i,j+1})+1)$$
最后答案就在所有$d{p}_{i,i}$和$d{p}_{i,i-1}$里面，枚举所有$i$求最小值即可。
注意初始化$d{p}_{i,j}=inf,d{p}_{1,n}=0$

第三题 （难度：简单~中等）

题目描述

给你一个矩阵，从左上角开始走，每次只能向下走一步或向右走一步，求走过路径的和的最小值。

100分做法

动态规划入门题，或者说是递推。
设$d{p}_{i,j}$表示到达点$(i,j)$的最小和。则：
$$d{p}_{i,j}=min(d{p}_{i-1,j},d{p}_{i,j-1})+a_{i,j}$$
最后输出$d{p}_{n,n}$即可。

第四题（难度：中等+）

题目描述

$A$和$B$轮流从袋子里取糖果，糖果分为甜的和普通的。
$A$每次取一颗，$B$每次取一颗顺带扔掉一颗。
如果上述取/扔的操作概率均匀随机，求$A$先取到甜糖果的概率。

100分做法

一道概率动态规划题，也可以记忆化搜索。
我们设$d{p}_{i,j,0/1}$表示甜糖果剩下$i$个，普通糖果剩下$j$个，当前是$A$/$B$先手，当前状态的概率。
当$A$先手时：

1. 如果他摸到了甜糖果，游戏结束，累加答案：
   $$ans+=d{p}_{i,j,0}\times \frac{i}{i+j}$$
2. 如果他摸到了普通糖果，游戏继续：
   $$d{p}_{i,j-1,1}+=d{p}_{i,j,0}\times \frac{j}{i+j}$$

当$B$先手时：

• 如果他摸到了甜糖果，游戏结束，无转移；
• 如果他摸到了普通糖果，扔掉了甜糖果：
  $$d{p}_{i-1,j-1,0}+=d{p}_{i,j,1}\times \frac{j}{i+j}\times \frac{i}{i+j-1}$$
• 如果他摸到了普通糖果，扔掉了普通糖果：
  $$d{p}_{i,j-2,0}+=d{p}_{i,j,1}\times \frac{j}{i+j}\times \frac{j-1}{i+j-1}$$

至此，转移结束。
最后答案就是$ans$。
记得初始化$d{p}_{n,m}=1$。