Computer olympiad training

Common functions

#![allow(unused)]
fn main() {
#[allow(warnings)]
pub mod lib {
    pub fn hexadecimal_to_decimal(h: &str) -> i32 {
        let mut result = 0;
        for c in h.get(2..).unwrap().to_string().chars() {
            match c.to_digit(16) {
                Some(d) => result = result * 16 + d as i32,
                None => return -1,
            }
        }
        result
    }
    pub fn parse_to_int(b: &str) -> Option<i32> {
        if b.len() == 0 {
            return None;
        }
        let mut res = 0;
        for c in b.chars() {
            res *= 10;
            res += c as i32 - 48;
        }
        return Some(res);
    }
    pub fn binary_to_decimal(num: &str) -> Option<i64> {
        if num.len() == 0 {
            return None;
        }
        let mut sum = 0;
        let vec = num
            .chars()
            .map(|x| i64::from(x.to_digit(10).unwrap()))
            .collect::<Vec<i64>>();
        for (index, item) in vec.iter().rev().enumerate() {
            sum += i64::pow(2, index as u32) * item;
        }
        Some(sum)
    }
    pub fn input_string() -> String {
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        input.trim().to_string()
    }
    pub fn input_num<T>() -> T
    where
        <T as std::str::FromStr>::Err: std::fmt::Debug,
        T: std::str::FromStr,
    {
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        input.trim().to_string().parse::<T>().unwrap()
    }

    pub fn input_vec_string(split_by: &str) -> Vec<String> {
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        input
            .trim()
            .split(split_by)
            .filter(|s| !s.is_empty())
            .map(|s| s.trim().to_string())
            .map(|s| s.to_string())
            .collect::<Vec<String>>()
    }
    pub fn input_vec_num<T>(split_by: &str) -> Vec<T>
    where
        <T as std::str::FromStr>::Err: std::fmt::Debug,
        T: std::str::FromStr,
    {
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        input
            .trim()
            .split(split_by)
            .filter(|s| !s.is_empty())
            .map(|s| s.trim().to_string())
            .map(|s| s.parse::<T>().unwrap())
            .collect::<Vec<T>>()
    }
    pub fn input_loop() -> std::io::Lines<std::io::StdinLock<'static>> {
        use std::io::{self, *};
        let stdin = io::stdin();
        stdin.lock().lines()
    }
}
}

贪心算法

1.1 活动安排

设有 n 个活动的集合 E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。选择出由互相兼容的活动组成的最大集合。

Simplify: 输出没有交集的区间的总数,Outputs the total number of intervals that do not intersect

输入格式
第一行一个整数 n；
接下来的 n 行，每行两个整数 s_i 和 f_i。

输出格式
输出互相兼容的最大活动个数。

in:
4
1 3
4 6
2 5
1 7
out:
2

#[allow(warnings)]
fn main() {
    let n = lib::input_num::<usize>();
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(lib::input_vec_num::<usize>(" "));
    }
    vec.sort_by_key(|s| s[1]); //sort by end time
    let mut ended = 0;
    let mut count = 0;
    for i in 0..n {
        if vec[i][0] >= ended {
            count += 1;
            ended = vec[i][1];
        }
    }
    println!("{:?}", count);
}

1.2 种树

某条街被划为 n 条路段，这 n 条路段依次编号为 1\dots n。每个路段最多可以种一棵树。现在居民们给出了 h 组建议，每组建议包含三个整数 b,e,t，表示居民希望在路段 b 到 e 之间至少要种 t 棵树。这些建议所给路段的区间可以交叉。请问：如果要满足所有居民的建议，至少要种多少棵树。

输入格式
第一行为 n，表示路段数。
第二行为 h，表示建议数。
下面 h 行描述一条建议：b, e, t，用一个空格分隔。

输出格式
输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。

in:
9
4
1 4 2
4 6 2
8 9 2
3 5 2
out:
5

in:
9
4 
1 4 2 
4 6 1 
8 9 2 
3 5 2 
out:
4