题意 题目链接：Problem - D - Codeforces 给你一个字符串$s$，每个位置都有一个权值$a_i(1\leq n\leq 10^5)$，这个权值是删除代价，请问删除若干个字符最后没有"hard"字符的子序列的最小代价是多少？ 思路 看到子序列就要往DP方面想 这是一道DP题，首先定义一个二维数组dp[i][j]。表示是到第i个字符j状态的最小值。 - dp[i][1]：不能有h - dp[i][2]：不能有ha,可以有h - dp[i][3]：不能有har,可以有ha - dp[i][4]：不能…
写在前面 这是去年ICPC上海站，我们队伍获得铜尾的比赛，曹佬手撕三维DP怒秀我和郎队，现在来看，好像也没有那么难嘿嘿，可能是自己刷了一些DP题。 题意 题目链接：I-Steadily Growing Steam 给你一个$n$个物品，每个物品有$v,t$两个属性，$v$是值，$t$是点数，现在你需要从里面取出若干份分成两堆（也就是说有的可以不选），求两堆的点数相等的时候的两堆的值的最大值。嘿嘿，没这么简单，还有一个条件，你最多有$k$次操作，可以使其中一个点数翻倍，也就是说，有可能让其翻倍之后正好两堆相同，这个时…
写在前面 这个题是去年打沈阳站我队没有做出来的题目，我觉得算铜牌题吧，当时要是做出来了我们就是铜牌了，差一点做到一赛季都是铜没有铁的“壮举”哈哈。 周日（4.24）的训练我还是避开了这个题，做别的题去了，可能是内心的恐惧吧，现在来赛后补题 题意 题目链接：J-Luggage Lock_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） (nowcoder.com) 给你两个由'0'...'9'组成的长度为$4$的字符串$s1$,$s2$，每次可以选择连续的部分进行$+1$或者$-1$，其实就是类似于我…
题目 2022年天梯赛决赛的前一晚，来几道二叉树的题目(RP++) 给你一个完美二叉树的前N项的后序遍历，求它的层序遍历 我的思考 我的思路是根据每个点往下有多少个子结点，因为给我的最后一个肯定是根，然后递归往下找。 我用一个我自己的样例，就是上图的10个 10 91 83 71 14 2 34 10 15 55 18 这个18肯定是根，前一个肯定是它的右结点，但是每一个数的前一个不一定是右结点，因为有可能不存在，所以我们判断一下： inline void dfs(int x,int p) { if (p<=…
题意 比赛链接：Problem - F - Codeforces 给你一个长度为$n(3\leq n\leq 2\times 10^5)$序列，问你是否能够将其分成三段使其满足如下条件：第一段Max=第二段Min=第三段Max，如果存在则输出"YES"和每段的长度，否则输出"NO"。 思路 看到这个数据我第一反应是双指针+贪心，但是wa2中的testcase721...最终放弃，去补题了，后来发现是自己贪心的方法不对，这里用二分+贪心过的。 这里枚举第一段的范围（时间复杂度$O(n)$），然后去二分第二个区间的长度…
题意 给你一个$N$个点，形成如下的图，求删除$i=\lbrace 1...N-1 \rbrace $条边，$N$个点依然联通的方案数，对$P$取模，数据范围：$2\leq N \leq 3000$ 这样的图是有$N$个点，$3N-2$条边，例如样例$N=3$的时候，当分别删除$1,2$条边的时候的方案数如下： 思路 我们用dp[i][j][0/1]来表示前i个点已经删除了j条边的连通性，0代表没联通，1代表联通的方案数。 注意我这里说的没联通代表前面i个虽然是不连通的，但是在今后的情况下是有可能连通的，比如不存在…
题目 题目来源于大连大学2022年4月程序设计竞赛，我和伍老师合砍12题rk23，差两题ak。 题目链接：F-旅行_大连大学2022年4月程序设计竞赛（同步赛） (nowcoder.com) 一句话题意：给你n点m边的有向图，每条边有边权，点没有点权，q次询问，每次询问点x是否在点1到点n的最短路径上，最短路径可能有多条。 如上图，从1到4的话，最短路当然是"1->3->4"，这三个点都是，而2不是。 思路 我们先用一个二维数组dis[i][j]来表示点i到点j之间的最短距离，那么对于起点是1，终点是n来说，询问一…
题意 题目链接：1064. 小国王 - AcWing题库 在 $n×n$ 的棋盘上放 $k$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。 数据范围 $1≤n≤10,$ $0≤k≤n^2$ 样例输入 3 2 样例输出 16 思路 这是一个状压DP，数据范围比较小，状压DP主要思想就是：state转化成二进制，每一位的0或1代表一个状态。 比如我们对一层$1×8$的棋盘，每一位如果放了国王，那么就是1，那么如下图的状态，我们可以用42(2+8+32)表示 先定义状态：f[i][j][s]…
题意 题目链接：1020. 潜水员 - AcWing题库 你需要m的氧气，n的氮气，在你面前有若干个瓶子（里面装氧气和氮气），每个瓶子都有质量，求满足你需要的条件下，最少重量是多少，例如： 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 你需要5的氧气和60的氮气，最少情况下是249，选择1，2或者4，5号气缸。 数据范围： $1≤m≤21,$ $1≤n≤79,$ $1≤k≤1000,$ $1≤a_i≤21,$ $1≤b_i≤79,$ $1≤c_i≤800$ 思路 二维背…
题意 给定一个长度为 $N$ 的数组 $A=[A_1,A_2,⋅⋅⋅,A_N]$，数组中有可能有重复出现的整数。 现在小明要按以下方法将其修改为没有重复整数的数组。 小明会依次修改 $A_2,A_3,⋅⋅⋅,A_N$。 当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1∼A_{i−1}$ 中出现过。 如果出现过，则小明会给 $A_i$ 加上 $1$；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 $1$，直到 $A_i$ 没有在 $A_1∼A_{i−1}$ 中出现过。 当 $A_N…
