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