搜索结果
查询Tags标签： 题解，共有 1043条记录-
【题解】[CCO2021] Travelling Merchant
先口胡一个，明天再来补代码（ 先考虑 \(-1\) 的情况，显然没有出边的点是 \(-1\)，将这样的点和对应的边删掉，直到每个点都有出边。显然被删掉的点都是 \(-1\)，其余的点都不是 \(-1\)。 对于剩下的边，显然 \(r_i\) 最大的边如果走了，那么其他的边随便走，所以对应的 …
2021/8/24 23:36:33 人评论 次浏览 -
[题解]787. K 站中转内最便宜的航班(C++)
题目 有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 \(flights[i] = [from_i, to_i, price_i]\) ，表示该航班都从城市 \(from_i\) 开始，以价格 \(price_i\) 抵达 \(to_i\)。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一…
2021/8/24 17:06:34 人评论 次浏览 -
[题解]787. K 站中转内最便宜的航班(C++)
题目 有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 \(flights[i] = [from_i, to_i, price_i]\) ，表示该航班都从城市 \(from_i\) 开始，以价格 \(price_i\) 抵达 \(to_i\)。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一…
2021/8/24 17:06:34 人评论 次浏览 -
[题解]剑指 Offer 13. 机器人的运动范围(C++)
题目 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，…
2021/8/24 14:05:39 人评论 次浏览 -
[题解]剑指 Offer 13. 机器人的运动范围(C++)
题目 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，…
2021/8/24 14:05:39 人评论 次浏览 -
题解 数数
传送门 除了我基本都A了……就很丢人 考场上先猜了个结论：\(k=i\) 的情况是 \(k=i+1\) 的最优解删掉一个数 发现有这个结论就可以做了 那么我们可以设法维护每个点与其它点差的绝对值的和 每次取这个和最小的那个数删掉就可以了 现在的难点在于动态维护每个数与其它数的绝…
2021/8/24 6:35:35 人评论 次浏览 -
题解 数数
传送门 除了我基本都A了……就很丢人 考场上先猜了个结论：\(k=i\) 的情况是 \(k=i+1\) 的最优解删掉一个数 发现有这个结论就可以做了 那么我们可以设法维护每个点与其它点差的绝对值的和 每次取这个和最小的那个数删掉就可以了 现在的难点在于动态维护每个数与其它数的绝…
2021/8/24 6:35:35 人评论 次浏览 -
Valley Numer II 题解(状压dp)
题目链接 题目大意 给定一张 N 个点 M 条边的无向图，其中有 K 个点被标记为高点，剩下的 (N-K) 个点是低点。图中的山谷 定义为三元组 <X,Y,Z>，满足X和Y之间有边，Y与 Z之间也有边，同时X和Z是高点，Y是低点。问这个图中 最多有几个山谷（一个点只能出现在一个山谷…
2021/8/23 23:36:20 人评论 次浏览 -
Valley Numer II 题解(状压dp)
题目链接 题目大意 给定一张 N 个点 M 条边的无向图，其中有 K 个点被标记为高点，剩下的 (N-K) 个点是低点。图中的山谷 定义为三元组 <X,Y,Z>，满足X和Y之间有边，Y与 Z之间也有边，同时X和Z是高点，Y是低点。问这个图中 最多有几个山谷（一个点只能出现在一个山谷…
2021/8/23 23:36:20 人评论 次浏览 -
Mondriaan's Dream 题解(棋盘状压问题)
题目链接 题目大意 现在有一个 nm 的方格棋盘，和无限的 12 的骨牌。 问有多少种方法可以用骨牌铺满棋盘。1 ≤ n,m ≤ 11 题目思路 这种算是状压dp的模板题目 主要是思考上一行和这一行的转移即可 需要两个连续的空位，并且上一行的这两个位置也得已经被覆盖。 如果竖着：…
2021/8/23 23:09:15 人评论 次浏览 -
Mondriaan's Dream 题解(棋盘状压问题)
题目链接 题目大意 现在有一个 nm 的方格棋盘，和无限的 12 的骨牌。 问有多少种方法可以用骨牌铺满棋盘。1 ≤ n,m ≤ 11 题目思路 这种算是状压dp的模板题目 主要是思考上一行和这一行的转移即可 需要两个连续的空位，并且上一行的这两个位置也得已经被覆盖。 如果竖着：…
2021/8/23 23:09:15 人评论 次浏览 -
【题解】[CCO2021] Swap Swap Sort
对于初始排列，就是求原序列的逆序对数。 对于逆序对我们可以拆开来算，用 \([i,j]\) 表示满足 \(a_u =i,a_v=j,i>j\) 二元组 \((u,v)\) 个数。 那么初始答案可以表示为 \(\sum\limits_{i = 1}^{k}\sum\limits_{j = i + 1}^{k}[i,j]\)。 推导之后可以得到，对于一次交换…
2021/8/23 23:08:59 人评论 次浏览 -
【题解】[CCO2021] Swap Swap Sort
对于初始排列，就是求原序列的逆序对数。 对于逆序对我们可以拆开来算，用 \([i,j]\) 表示满足 \(a_u =i,a_v=j,i>j\) 二元组 \((u,v)\) 个数。 那么初始答案可以表示为 \(\sum\limits_{i = 1}^{k}\sum\limits_{j = i + 1}^{k}[i,j]\)。 推导之后可以得到，对于一次交换…
2021/8/23 23:08:59 人评论 次浏览 -
Pieces 题解(状压dp+$3^n$枚举子集)
题目链接 题目大意 有一个长度不超过 16 的字符串。每次你可以从中删除一个子序列，但是要求这个子序列是回 文的。问最少删除几次可以把这个字符串删光。 题目思路 这个数据很小 很明显是状压\(dp\) 设\(dp[i]\)表示删除\(i\)的最小操作数 那么答案显然为\(dp[(1<<…
2021/8/23 23:08:58 人评论 次浏览 -
Pieces 题解(状压dp+$3^n$枚举子集)
题目链接 题目大意 有一个长度不超过 16 的字符串。每次你可以从中删除一个子序列，但是要求这个子序列是回 文的。问最少删除几次可以把这个字符串删光。 题目思路 这个数据很小 很明显是状压\(dp\) 设\(dp[i]\)表示删除\(i\)的最小操作数 那么答案显然为\(dp[(1<<…
2021/8/23 23:08:58 人评论 次浏览
