链接:G-生蚝接柿子_"夜莺杯"武汉理工大学第四届新生程序设计竞赛 (nowcoder.com) 去年新生赛的一道题。 现在补一下。 分析 不难定义出状态dp[i][j]表示,到从下往上第i个柿子的时候,此时左手在j位置可以接到的最多柿子个数。 状态的转移也比较简单,dp[i][j] -> dp[i + 1][L ~ R],其中L, R是可以j到达的最远的位置。 当然从i - 1转移到i也可以,只 […]
链接: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 […]
Eriktse
18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。
COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.
Theme Kratos | Hosted In TENCENT CLOUD