LC2646. Minimize the Total Price of the Trips Hard
袜，这题还是挺有挑战的。
给定一棵树，每个点有权值，给定M组点对 (ai, bi)，求Sum(dis[ai, bi])。
如果只到这，好像还没啥，树剖LCA就能解决，别说N=50了，N=10^5也行
但是多了个条件，可以把一些不相邻的点的权值减半，让我们求最小的结果
我目测得把路径离线，先统计出来每个点要走多少次。
树可以染色吗，所有点一定是可以分成两组的么，如果是，那就简单了，无非是选组1或者组2，但是显然不是（考虑链：1-2-3-4，我可以染1和4）
考虑树形dp，一个节点能染色要求它的子节点都没有染色，那好像就好做了，我们预先确定一个根root
dpi表示到节点i，节点有半价/无半价的最小值
dpfa = Sum(min(dp[son])) + price[fa] * freq[fa]
dpfa = Sum(dpson) + price[fa]/2 * freq[fa]
边界是叶子节点，直接处理自己的值就行，考虑这样是不是能覆盖所有状态。不相邻的话应该是恰好覆盖
0ms，一遍过，讲真，现在一遍过的概率高很多，我还是蛮高兴的，证明自己下手越来越有准头了。
impl Solution {
pub fn minimum_total_price(
n: i32,
edges: Vec<Vec<i32>>,
price: Vec<i32>,
trips: Vec<Vec<i32>>,
) -> i32 {
let n = n as usize;
let mut fa = vec![0; n];
let mut freq: Vec<i32> = vec![0; n];
let mut dep: Vec<i32> = vec![0; n];
let edges: Vec<Vec<i32>> = edges.iter().fold(vec![vec![]; n], |mut acc, e| {
acc[e[0] as usize].push(e[1]);
acc[e[1] as usize].push(e[0]);
acc
});
let mut dp: Vec<Vec<i32>> = vec![vec![0; 2]; n];
let root = 0;
dfs(root, &mut fa, &mut dep, &edges);
for trip in trips.iter() {
let mut x = trip[0] as usize;
let mut y = trip[1] as usize;
while x != y {
if dep[x] < dep[y] {
std::mem::swap(&mut x, &mut y);
}
freq[x] += 1;
x = fa[x] as usize;
}
freq[x] += 1;
}
dfs2(root, &edges, &freq, &mut dp, -1, &price);
dp[root as usize][0].min(dp[root as usize][1])
}
}
fn dfs(p: i32, fa: &mut Vec<i32>, dep: &mut Vec<i32>, edges: &Vec<Vec<i32>>) {
for &to in edges[p as usize].iter() {
if to == fa[p as usize] {
continue;
}
fa[to as usize] = p;
dep[to as usize] = dep[p as usize] + 1;
dfs(to, fa, dep, edges);
}
}
fn dfs2(
p: i32,
edges: &Vec<Vec<i32>>,
freq: &Vec<i32>,
dp: &mut Vec<Vec<i32>>,
fa: i32,
price: &Vec<i32>,
) {
let mut res0 = 0;
let mut res1 = 0;
for &to in edges[p as usize].iter() {
if to == fa {
continue;
}
dfs2(to, edges, freq, dp, p, price);
res0 += dp[to as usize][0];
res1 += std::cmp::min(dp[to as usize][0], dp[to as usize][1]);
}
dp[p as usize][0] = res1 + freq[p as usize] * price[p as usize];
dp[p as usize][1] = res0 + freq[p as usize] * (price[p as usize] >> 1);
}LC62. Unique Paths/63. Unique Paths II/980. Unique Paths III Med Med Hard
62是从左上走到右下的不重复路径数，63是带障碍的，980是从起点到终点，且走过全部空格子的路径数，难度陡增啊
62、63都是比较简单的dp，dpi表示走到(i, j)的方案数，dp[unreachable] = -1, ans = dpm, dpi = dpi-1 + dpi; 常规到我不打算贴代码了，主要关注980
数据范围 20*20, 这个能直接搜么，搜的复杂度是多少？最讨厌算搜索的复杂度了。不过看上去400个格子，4^400肯定不可做的。但是应该也不是dp，状态太多了，也压不了。我还是倾向于搜索+剪枝，先搜一发试试
有个小插曲：你觉得这好看么，我望着这排迭代器沉思了几秒，决定还是乖乖遍历
impl Solution {
pub fn unique_paths_iii(grid: Vec<Vec<i32>>) -> i32 {
let target = grid
.iter()
.map(|row| row.iter().filter(|&&x| x == 0).count())
.sum::<usize>();
let (x, y) = grid
.iter()
.enumerate()
.flat_map(|(i, row)| {
row.iter()
.enumerate()
.find(|&(_, &x)| x == 1)
.map(|(j, _)| (i, j))
})
.next()
.unwrap();
}
}没想到0ms是真的。。
impl Solution {
fn dfs(grid: &mut Vec<Vec<i32>>, x: usize, y: usize, now_step: i32, target_step: i32) -> i32 {
if grid[x][y] == 2 {
return match now_step == target_step {
true => 1,
false => 0,
};
}
let mut res = 0;
grid[x][y] = -1;
let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];
for i in 0..4 {
let nx = x as i32 + dx[i];
let ny = y as i32 + dy[i];
if nx >= 0 && nx < grid.len() as i32 && ny >= 0 && ny < grid[0].len() as i32 {
let nx = nx as usize;
let ny = ny as usize;
if grid[nx][ny] == 0 || grid[nx][ny] == 2 {
res += Self::dfs(grid, nx, ny, now_step + 1, target_step);
}
}
}
grid[x][y] = 0;
res
}
pub fn unique_paths_iii(mut grid: Vec<Vec<i32>>) -> i32 {
let mut target_steps = 1;
let (mut sx, mut sy) = (0, 0);
for i in 0..grid.len() {
for j in 0..grid[0].len() {
if grid[i][j] == 0 {
target_steps += 1;
} else if grid[i][j] == 1 {
sx = i;
sy = j;
}
}
}
Self::dfs(&mut grid, sx, sy, 0, target_steps)
}
}LC787. Cheapest Flights Within K Stops Med
求两点之间最短路，但是有个限制，最多走K条边，感觉挺难的，一看N范围100。EMM是不是BFS K层就可以了。
这个复杂度是啥样的，应该就是KM能搞，好像也能用类似Dij的思路堆优化，但是优化起来考虑的更多。
先写个BFS试试，就是贝尔曼福德吧
impl Solution {
pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
let mut dis = vec![0x3f3f3f3f; n as usize];
dis[src as usize] = 0;
let mut now_dis = Vec::with_capacity(n as usize);
for _ in 0..=k {
now_dis.clear();
now_dis = dis.clone();
for flight in &flights {
let u = flight[0] as usize;
let v = flight[1] as usize;
let w = flight[2];
if now_dis[u] != 0x3f3f3f3f {
now_dis[v] = now_dis[v].min(dis[u] + w);
}
}
std::mem::swap(&mut dis, &mut now_dis);
}
match dis[dst as usize] {
0x3f3f3f3f => -1,
_ => dis[dst as usize],
}
}
}LC997. Find the Town Judge Ez
找到一个入度n-1，没有出度的点，都懒得开IDE
本期每日一题将在今天开始变成每日一题+一道Hard
我发现每日一题总刷Ez，一点用没有，Ez等级能用到的语法我基本上已经熟悉了。
并将会在近期开rust kernel的
impl Solution {
pub fn find_judge(n: i32, trust: Vec<Vec<i32>>) -> i32 {
let n = n as usize;
let (mut ind, mut oud) = (vec![0;n+1], vec![0;n+1]);
trust.iter().for_each(|t| {
oud[t[0] as usize] += 1;
ind[t[1] as usize] += 1;
});
(1..=n as i32).find(|&x| oud[x as usize] == 0 && ind[x as usize] == n-1).unwrap_or(-1)
}
}LC2092. Find All People With Secret Hard
10^5个人，10^5的时间，最多10^5的会，N^2是没戏了，应该是哪一维要log
这东西要我想的话肯定是一个并查集，按时间就把人塞到并查集里了。
哎好像能直接做奥，主要就是同一时间的传播怎么处理这个问题。
先不考虑同时开会传播的问题。把会议按时间排个序。对每对x、y，看看是不是有一边持有Secret，如果是，把没有那边并进firstPerson这个集合里。
好像考虑的话也没问题。。对同一时间的遍历两遍就行了。
既然不能只遍历两遍，考虑这块怎么优化。一个比较显然的优化是，如果能把当前时间的人也划分联通块，就不会是链式传播了。但是这样要写一个离散化并查集，好麻烦。。。（不然初始化是N的，如果离散化，应该是均摊N）
但是我考虑一个暴力，在sys里也常用。我不扫两遍，我扫到没有更新为止。这样复杂度肯定是不对的，但是没准能骗
struct Union {
parent: Vec<i32>,
}
impl Union {
fn new(n: usize) -> Self {
Union {
parent: (0..n as i32).collect(),
}
}
fn find(&mut self, x: i32) -> i32 {
if self.parent[x as usize] != x {
self.parent[x as usize] = self.find(self.parent[x as usize]);
}
self.parent[x as usize]
}
fn union(&mut self, x: i32, y: i32) {
// println!("merge {} {}", x, y);
let x = self.find(x);
let y = self.find(y);
if x != y {
self.parent[x as usize] = y;
}
}
}
impl Solution {
pub fn find_all_people(n: i32, mut meetings: Vec<Vec<i32>>, first_person: i32) -> Vec<i32> {
let mut union = Union::new(n as usize);
union.union(0, first_person);
let mut meetings_by_time = vec![vec![]; 100001];
for i in 0..meetings.len() {
let m = &meetings[i];
meetings_by_time[m[2] as usize].push((m[0], m[1]));
}
// println!("{:?} {:?} {:?}", meetings_by_time[5], meetings_by_time[8], meetings_by_time[10] );
for i in 0..meetings_by_time.len() {
let mut changed = true;
while changed {
changed = false;
for j in 0..meetings_by_time[i].len() {
let m = meetings_by_time[i][j];
let root = union.find(first_person);
let (dx, dy) = (union.find(m.0), union.find(m.1));
if dx == dy || (dx != root && dy != root) {
continue;
}
union.union(m.0, m.1);
changed = true;
}
}
}
let mut ans = vec![];
let root = union.find(first_person);
for i in 0..n {
if union.find(i) == root {
ans.push(i);
}
}
ans
}
}
评论 (0)