# 2022-11-03：给定一个数组arr，和一个正数k 如果arr[i] == 0，表示i这里既可以是左括号

2022-11-03：给定一个数组arr，和一个正数k

2 <= arr长度 <= 5000
1 <= k <= 1000
0 <= arr[i] <= k。
2022.8.7笔试第三道。来自猿辅导。

``````use std::iter::repeat;

use rand::Rng;
fn main() {
let nn: i32 = 5;
let kk: i32 = 4;
let test_time: i32 = 1000;
println!("测试开始");
for _i in 0..test_time {
let n = (rand::thread_rng().gen_range(0, nn) + 1) << 1;
let k = rand::thread_rng().gen_range(0, kk) + 1;
let mut arr = random_array(n, k);
let ans1 = ways1(&mut arr, k);
let ans2 = ways2(&mut arr, k);
if ans1 != ans2 {
println!("arr = {:?},k = {}", arr, k);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
println!("出错了!");
break;
}
}
println!("测试结束");
}

// 暴力方法
// 为了验证
fn ways1(arr: &mut Vec<i32>, k: i32) -> i32 {
if arr.len() & 1 != 0 {
return 0;
}
return process1(arr, 0, k);
}

fn process1(arr: &mut Vec<i32>, index: i32, k: i32) -> i32 {
if index == arr.len() as i32 {
let n = arr.len() as i32;
let mut stack: Vec<i32> = repeat(0).take(n as usize).collect();
let mut size = 0;
for i in 0..n {
if arr[i as usize] > 0 {
stack[size as usize] = arr[i as usize];
size += 1;
} else {
if size == 0 {
return 0;
}
size -= 1;
if stack[size as usize] != -arr[i as usize] {
return 0;
}
}
}
return if size == 0 { 1 } else { 0 };
} else if arr[index as usize] != 0 {
return process1(arr, index + 1, k);
} else {
let mut ans = 0;
for color in 1..=k {
arr[index as usize] = color;
ans += process1(arr, index + 1, k);
arr[index as usize] = -color;
ans += process1(arr, index + 1, k);
arr[index as usize] = 0;
}
return ans;
}
}

fn ways2(arr: &mut Vec<i32>, k: i32) -> i32 {
let n = arr.len() as i32;
if n & 1 != 0 {
return 0;
}
let a = combines(arr);
let mut b = 0;
for num in arr.iter() {
if *num != 0 {
b += 1;
}
}
return if ((n - (b << 1)) >> 1) < 0 {
0
} else {
a * k.pow(((n - (b << 1)) >> 1) as u32)
};
}

// 忽略染色这件事，求合法的括号结合数量
fn combines(arr: &mut Vec<i32>) -> i32 {
let n = arr.len() as i32;
let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take(n as usize).collect())
.take(n as usize)
.collect();
return f(arr, 0, 0, &mut dp);
}

// arr[i....]范围上，去做决定
// j : arr[0..i-1]已经做完决定的部分，左括号比右括号，多几个
// 返回：
// arr[i....]范围上，去做决定，
// 已经做完决定的部分，左括号比右括号多j个
// 这样的情况下，最终合法的括号结合，多少个！
// process(arr, 0, 0)
fn process(arr: &mut Vec<i32>, i: i32, j: i32) -> i32 {
if i == arr.len() as i32 {
return if j == 0 { 1 } else { 0 };
}
if j < 0 {
return 0;
}
// 这个不写也行
// 锦上添花的剪枝条件
if arr.len() as i32 - i < j {
return 0;
}
// arr[i] != 0
if arr[i as usize] != 0 {
// (
return process(arr, i + 1, j + 1);
} else {
// arr[i] 0 ? ( )
let p1 = process(arr, i + 1, j + 1);
let p2 = process(arr, i + 1, j - 1);
return p1 + p2;
}
}

// 在arr[i...]范围上做决定
// 之前在arr[0...i-1]上的决定，使得左括号比右括号多了j个
// 最终合法的括号结合是多少
fn f(arr: &mut Vec<i32>, i: i32, j: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
let n = arr.len() as i32;
if i == n {
return if j == 0 { 1 } else { 0 };
}
if j < 0 {
return 0;
}
if n - i < j {
return 0;
}
// 如果缓存命中，直接返回答案
if dp[i as usize][j as usize] != -1 {
return dp[i as usize][j as usize];
}
let mut ans = 0;
if arr[i as usize] > 0 {
ans = f(arr, i + 1, j + 1, dp);
} else {
ans = f(arr, i + 1, j + 1, dp) + f(arr, i + 1, j - 1, dp);
}
dp[i as usize][j as usize] = ans;
return ans;
}

// 生成长度随机的数组
// 值在0~K之间，但是50%的概率值是0，50%的概率值是1~k中的一个
fn random_array(n: i32, k: i32) -> Vec<i32> {
let mut ans = vec![];
for _ in 0..n {
ans.push(if rand::thread_rng().gen_range(0, 2) == 0 {
0
} else {
})
}
return ans;
}
``````

(=￣ω￣=)··· 暂无内容！

172

10

16

5