链接：G-生蚝接柿子_"夜莺杯"武汉理工大学第四届新生程序设计竞赛 (nowcoder.com) 去年新生赛的一道题。 现在补一下。 分析 不难定义出状态dp[i][j]表示，到从下往上第i个柿子的时候，此时左手在j位置可以接到的最多柿子个数。 状态的转移也比较简单，dp[i][j] -> dp[i + 1][L ~ R]，其中L， R是可以j到达的最远的位置。 当然从i - 1转移到i也可以，只 […]

比赛传送门：Dashboard - The 2021 CCPC Weihai Onsite - Codeforces A. Goodbye, Ziyin!（签到 + 树） 签到题。 给定一颗无根树（没有指定根的，意味着任何一点都可以为根），问有多少个点作为根可以使得整棵树为一颗二叉树。 对于签到的树题，一般都不需要建树，只需要记录度数。我们想一下二叉树的特征：根的度数\(\le 2\)，其余点的度 […]

题目传送门：P1521 求逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 / Thought 用dp[i]j[j]表示选取[1, i]的数组，且有j个逆序对的排列方案数。 dp[i]可以从dp[i - 1]转移过来，假设现在的数字是i，那么对于dp[i - 1]的所有状态，i可以插入到i个位置中去，如果插入到第1个位置，那么逆序对会增加i - 1个，如果插入第2个位 […]

题目传送门：第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海） D Strange_Fractions（解方程，数论） 解方程，设\(t = \frac{b}{a}\)，将方程两边同时乘\(t\)可以得到\(qt^2 - pt + q = 0\)，通过小学二年级学的一元二次方程求根公式可知：当\(p^2 - 4q^2 \ge 0\)时方程有解。由求根公式可以得到\(t = \frac […]

可以在PTA补题。 题目大意 / Problem 给定两个字符串s和t，求一个s的子串s'使得s'和t的最大公共子串长度不超过1，问s'的最大长度。 子串可以不连续。 思路 / Thought 先把字符转换成[0, 25]的数字方便处理。 根据题意判断应该是个DP。由于是一个和位置和字符有关的dp，状态可以设为\(dp[i][j]\)，表示到s的第i个位置为止，最后一个敏感字符（定义为存在于t中的 […]

题目传送门：E - Warp (atcoder.jp) 题意 / Problem 在二维平面中，从原点(0, 0)出发，进行N次移动，每次移动可以选择3个方向，分别是从\((x, y)\)移动到\((x + A, y + B)、(x + C, y + D)、(x + E, y + F)\)，只在整数点上运动。 有M个障碍点是不能走的。问N次移动后一共可以有多少种运动轨迹。 思路 / Thought […]

题目传送门：乐团派对 (nowcoder.com) 思路 / Thought 首先对能力值数组进行排序，因为选人的时候顺序没要求，升序的话方便考虑，如果i可以组成乐队的话，比i小的肯定可以组成。 定义dp[i]表示到i为止可以组成的最大合法乐团数量。 接下来就可以写状态转移方程 第i个人，要么分到前面的乐队，要么分到后面的乐队。 但是第N个只能分到前面的乐队，所以输出的答案应该是dp[N - a[ […]

题目传送门：Problem - 7191 (hdu.edu.cn) 题目 / Problem 给定一个[1, n]的排列p和一个数字K，求[1, n]的子集T的个数。 子集T的大小为K，对于集合T中的任意一个元素x，p[x]不在该集合中。 思路 / Thought 排列的题很容易想到将i与p[i]连接起来，一定能组成若干个环，这里要求对于T中任意一个元素x，p[x]不能在T中，也就是说在若干个环中 […]

题目传送门：F - Tournament (atcoder.jp) 题意 / Problem 有\(2^N\)个人，从\(1 ~ N\)进行编号，进行N轮操作，每轮操作将第\(2i-1\)和第\(2i\)个人进行对战，每次对战都有一个人胜出，失败的人淘汰。 编号为i的人如果赢了j次，那么就可以获得\(C[i][j]\)的奖励。求所有人获得的最大的奖励之和。 思路 / Thought 显然是一颗完美 […]

题目传送门：E - Sugoroku 3 (atcoder.jp) 题目大意 / Problem 有N个点（位置），其中从1到N - 1个点上各有一个骰子，在第i个点上可以投掷第i个骰子，假设在x位置上投到y，下一步就走到y上。保证下一个位置不会大于N。 问从位置1到位置N的步数期望，对998244353。 思路 / Thought 之前有写过期望的题《[LightOJ]Race to 1 Aga […]