Rust算法练习-LC2092/997/787/980/2646

yyi
yyi
2024-02-24 / 0 评论 / 39 阅读 / 正在检测是否收录...

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里也常用。我不扫两遍,我扫到没有更新为止。这样复杂度肯定是不对的,但是没准能骗

img

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

评论 (0)

取消