题目传送门：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 […]

题目传送门：A-蕾凹娜的哀伤_喜迎暑假多校联赛第二场（欢乐AK找回自信） (nowcoder.com) 题意 / Problem 中文题意不解释了。 思路 / Thought 多重背包问题，加上二进制优化后复杂度为O(N * V * log(S))。 代码 / Code

题目链接：Problem - 7163 (hdu.edu.cn) 题意 / Problem 有一个人要打Boss，他有n个技能且每个技能最多释放一次，怪物有H血量，问这个人打败Boss最短时间，如果不能打败输出-1。 思路 / Thought 因为要求最短时间，如果给定一个时间可以用较小的复杂度O(2 ^ n)算出这个时间是否可以打败Boss，所以考虑用二分。找到分界点就找到了答案，因为题目要求的 […]