[Rust学习:二]变量和传参
[Rust学习:二]变量和传参
- 一、前言
- 二、练习
- 1. 前置：a:&T、a:&mut T、mut a:&T、mut a:&mut T的区别
- 2. 例题： F - LIS on Tree
- 3. 题解。
- 三、 代码实现
- 六、参考链接
一、前言
- 在本文通过写一题实战，初步探索了这些技能：
- Cargo.toml引入库的配置
- main中使用外部库：proconio、itertools、superslice。
- 函数声明的形参实参写法以及注意点。
- 如何方便的读入(proconio::input!)。
- 如何方便的数组join(引入itertools::Itertools后ans.iter().join(“\n”))。
- 有序数组的二分查找(引入superslice::Ext后dp.lower_bound(&x))。
- 基础整型使用（优先usize吧）。
- Rust的变量、传参、权限控制真的反人类。
- 碎碎念:
- 实现时通常会使用数组下标作为特征，如：a是点权数组，点化作0~n-1下标来索引点权，这就导致了点的类型必须是usize。那么负值
就不能用，导致dfs初始fa参数反习惯，很难受。 - 后来复盘代码发现很多行尾忘记写分号，也过了，观察了一下发现基本都是
代码块的末行，如大括号{}内最后一行。
这是因为末行如果不写分号默认会帮你把这个表达式作为return的值。
- 实现时通常会使用数组下标作为特征，如：a是点权数组，点化作0~n-1下标来索引点权，这就导致了点的类型必须是usize。那么负值
二、练习
1. 前置：a:&T、a:&mut T、mut a:&T、mut a:&mut T的区别
- a:&T：引用不可变，且引用指向的内容不可修改。
- a:&mut T：引用不可变，引用指向的内容可修改。
- mut a:&T：引用可变（a可重新赋值），但引用指向的内容不可修改。
- mut a:&mut T：引用可变，引用指向的内容可修改。
2. 例题： F - LIS on Tree
F - LIS on Tree
https://atcoder.jp/contests/abc165/tasks/abc165_f
输入 n (2≤n≤2e5) 和长为 n 的数组 a (1≤a[i]≤1e9)，表示每个节点的点权。
然后输入一棵树的 n-1 条边（节点编号从 1 开始）。
输出 n 个数，第 i 个数为从节点 1 到节点 i 的路径上点权的 LIS 长度。
注：LIS 指最长上升子序列。
输入
10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10
输出
1
2
3
3
4
4
5
2
2
3
这是一道atc上的题，题意比较清楚，写个DFS在路径上跑LIS即可。
3. 题解。
- 我们套用LIS的二分优化模板，需要一个单调递增的dp数组：
let mut dp: Vec<usize> = vec![0; 0];
注意这里需要声明dp是mut，后边的vec!宏可以直接创建一个内容是全是0且长度为0的vector。 - 建图时，本题无边权有点权，因此可以两层int的vector即可：
let mut g = vec![Vec::new(); n];这里省略了g的类型声明。 - 读入时，使用input!宏，这个宏在proconio包中，注意加入Cargo.toml。
Cargo.toml:[dependencies] proconio = "0.4.2"main.rs:use proconio::input; input! { n:usize, a:[usize;n], es:[(usize,usize);n-1] } - 输出时，由于要输出n行答案，实测用回车拼完一起输出会快很多。这里需要用到
use itertools::Itertools;这个库，注意加Cargo.toml：itertools = "0.10.0"
main.rs:println!("{}", ans.iter().join("\n")); - 注意，vector原来不支持二分，需要引入一个库：
use superslice::Ext;,Cargo.toml：superslice = "1.0.0";, main.rs:p = dp.lower_bound(&x);
- 准备工作做好了接下来是最烦的dfs函数编写。
- rust的fn支持写在main外边或里边，目前没看出什么区别。即使写在里边也用不了main里的变量，需要显式传参。
- 为了运行速度，显然所有非基础类型（比如集合等）都要传引用&。坑就在这些地方。
- 来看函数头：
fn dfs( u: usize, // 当前节点 fa: usize, // 父节点 g: &Vec<Vec<usize>>, // 图 dp: &mut Vec<usize>, // dp ans: &mut Vec<usize>, // 答案 a: &Vec<usize>, // 点权 ) {}- 其中u和fa是基础类型，函数体内也不会变，直接传值即可。这里fa我在其他语言里一般初始传-1，但是这里必须是usize，因此要传入一个不会存在的节点。由于节点被我转化成0~n-1,因此初始传n以上即可。
- g是不会变的图，用来dfs路径，因此形参直接声明引用。
- dp是会变的，大小变push、pop和内容修改。因此形参要声明为
&mut Vec<usize>。 - ans同dp。
- a是用来查询点权，又不变，声明引用即可。
- 当main里进dfs时，所有实参要显式的传递引用即：
main:dfs(0, 2000000, &g, &mut dp, &mut ans, &a); - 但在dfs内部自我调用时，由于这些参数本身传进来已经是引用了，因此不加&标志，即：
dfs:dfs(v, u, g, dp, ans, a);
三、 代码实现
- 实现时，由于dfs需要回溯，我使用x变量来储存修改的dp[p]的值，这里可以使用
std::mem::swap(&mut x,&mut dp[p]);这个方法，它不会初始化双方的绑定。
/***
https://atcoder.jp/contests/abc165/tasks/abc165_f
输入 n (2≤n≤2e5) 和长为 n 的数组 a (1≤a[i]≤1e9)，表示每个节点的点权。
然后输入一棵树的 n-1 条边（节点编号从 1 开始）。
输出 n 个数，第 i 个数为从节点 1 到节点 i 的路径上点权的 LIS 长度。
注：LIS 指最长上升子序列。
输入
10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10
输出
1
2
3
3
4
4
5
2
2
3
*/
use proconio::input;
// use std::collections::VecDeque;
//
use itertools::Itertools;
// use petgraph::{Graph, data::Build};
use superslice::Ext;
const MOD:usize = 1000000000+7;
const INF:usize = 1<<60;
fn main() {
input!{
n:usize,
a:[usize;n],
es:[(usize,usize);n-1]
}
let mut g = vec![Vec::new();n];
for (u,v) in es {
g[u-1].push(v-1);
g[v-1].push(u-1);
}
let mut dp:Vec<usize> = vec![0;0];
// let mut dp:Vec<usize> = vec![INF;n];
fn dfs(
u:usize,
fa:usize,
g:&Vec<Vec<usize> >,
dp: &mut Vec<usize>,
ans:&mut Vec<usize>,
a: &Vec<usize>
){
let mut x = a[u];
let p ;
if dp.len() == 0 || x>dp[dp.len()-1] {
dp.push(x);
p = a.len();
}
else {
p = dp.lower_bound(&x);
// let t = x;
// x = dp[p];
// dp[p] = t;
std::mem::swap(&mut x,&mut dp[p]);
}
// ans[u] = dp.lower_bound(&INF);
ans[u] = dp.len();;
for &v in g[u].iter(){
if v != fa{
dfs(v,u,g,dp,ans,a);
}
}
if p == a.len() {
dp.pop();
}
else {
dp[p] = x;
}
}
let mut ans = vec![1usize;n];
dfs(0,2000000,&g,&mut dp,&mut ans,&a);
// for v in ans {
// println!("{}",v)
// }
println!("{}", ans.iter().join("\n"));
}
六、参考链接
- https://atcoder.jp/contests/abc165/submissions/36201793