目录
2023
12月往前的应该就不会补题解了,大概有时间会往前一直补到12/1的题解
12/25
题目分析：
数学题，解二元一次方程即可
具体过程有$$\left { \begin{array}{c}4x+2y=tomatoSlices\x+y=cheeseSlices \end{array}\right.$$
解得$$\left { \begin{array}{c}y=(4*cheeseSlices-tomatoSlices)/2\x=cheeseSlices-y \end{array}\right.$$
另外，我们还需要判断y是否为整数，否则没法刚好配完
Rust代码
impl Solution {
pub fn num_of_burgers(t: i32, c: i32) -> Vec<i32> {
if t >= 2 * c && (t - 2 * c) % 2 == 0 && 4 * c >= t && (4 * c - t) % 2 == 0 { vec![(t - 2 * c) / 2, (4 * c - t) / 2] } else { vec![] }
}
}
C++代码
class Solution {
public:
vector<int> numOfBurgers(int t, int c) {
return (4 * c - t) % 2 || (t - 2 * c) / 2 < 0 || (4 * c - t) / 2 < 0 ? vector<int>{} : vector<int>{(t - 2 * c) / 2, (4 * c - t) / 2};
}
};
12/26
困难的一道困难题，暂时没有敲出代码，题解里有两种思路，动态规划的代码相对简短，但是时间复杂度到了 \(O(2^n)\) ，这里暂时贴出LightT大佬的将原问题看成二分图最大独立集的思路，大概是到寒假有时间补上代码。
动态规划思路：
- 每次计算第 i 行取 j 个座位时，前 i 行的最大值
- 采用位运算减少判断次数：
- 首先假设第 i 行的状态是010010 ,我们将其记为 j
- 将其做 左移|右移 运算后，得到 101101 ，其中1的位置不能坐人,这个座位状态我们将其记为 t
- 那么 $$dp(i,j)=\max_{s\subseteq j}\lbrace dp(i-1,t)+|s|\rbrace$$
- 最后得到前 n 行的最大值
最大二分独立集思路：
- 同一列上的人座位可以随便坐
- 奇数列向源节点 \(s\) 连边，偶数列向汇点 \(t\) 连边
- 冲突的奇偶列再连边
- 算出最大流(即能抄到答案的座位匹配最大数)
- 计算：所有可坐人的座位-最大流（得到的就是不能互相抄答案的最大匹配数
12/27
题目分析：
模拟计算出总分即可
对于每个计算：
一次遍历，同时判断前两个是否包含 10 ，如果包含，则当前值 *2
Rust代码
impl Solution {
pub fn is_winner(player1: Vec<i32>, player2: Vec<i32>) -> i32 {
let sore_sum = |player: &Vec<i32>| -> i32 {
(0..player.len()).fold(0, |x, i| { //求和
(x + player[i] * (if i > 0 && player[i - 1] == 10 || i > 1 && player[i - 2] == 10 { 2 } else { 1 })) //当前两个中存在==10时 *2
})
};
match sore_sum(&player1).cmp(&sore_sum(&player2)) {
std::cmp::Ordering::Equal => 0, //相等返回0
std::cmp::Ordering::Greater => 1, //player1胜
std::cmp::Ordering::Less => 2, //player2胜
}
}
}
C++代码
class Solution {
public:
int isWinner(vector<int>& player1, vector<int>& player2) {
auto f = [](vector<int>& player) { //lambda表达式
int s = 0;
for (int i = 0, n = player.size(); i < n; ++i) {
int k = (i && player[i - 1] == 10) || (i > 1 && player[i - 2] == 10) ? 2 : 1; //判断是否需要 *2
s += k * player[i];
}
return s;
};
int a = f(player1), b = f(player2); //计算
return a > b ? 1 : (b > a ? 2 : 0);
}
};
持续更新ing……