Algorithm
lc1411_给Nx3网格图涂色的方案数
思路:
这类题目都是递推优化，但是有点生疏了，学习一下题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int numOfWays(int n) {
// 预处理出所有满足条件的 type
vector<int> types;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (i != j && j != k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.push_back(i * 9 + j * 3 + k);
}
}
}
}
int type_cnt = types.size();
// 预处理出所有可以作为相邻行的 type 对
vector<vector<int>> related(type_cnt, vector<int>(type_cnt));
for (int i = 0; i < type_cnt; ++i) {
// 得到 types[i] 三个位置的颜色
int x1 = types[i] / 9, x2 = types[i] / 3 % 3, x3 = types[i] % 3;
for (int j = 0; j < type_cnt; ++j) {
// 得到 types[j] 三个位置的颜色
int y1 = types[j] / 9, y2 = types[j] / 3 % 3, y3 = types[j] % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 != y1 && x2 != y2 && x3 != y3) {
related[i][j] = 1;
}
}
}
// 递推数组
vector<vector<int>> f(n + 1, vector<int>(type_cnt));
// 边界情况，第一行可以使用任何 type
for (int i = 0; i < type_cnt; ++i) {
f[1][i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < type_cnt; ++j) {
for (int k = 0; k < type_cnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j]) {
f[i][j] += f[i - 1][k];
f[i][j] %= mod;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
int ans = 0;
for (int i = 0; i < type_cnt; ++i) {
ans += f[n][i];
ans %= mod;
}
return ans;
}
};
|
优化版本:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int numOfWays(int n) {
int fi0 = 6, fi1 = 6;
for (int i = 2; i <= n; ++i) {
int new_fi0 = (2LL * fi0 + 2LL * fi1) % mod;
int new_fi1 = (2LL * fi0 + 3LL * fi1) % mod;
fi0 = new_fi0;
fi1 = new_fi1;
}
return (fi0 + fi1) % mod;
}
};
|
Review
Curiosity Is Compound Interest for Your Brain
- 对某件事情的好奇心探索的反馈迭代，可以让人保持热情，形成复利。
- 熟悉热爱的事情和不熟悉不热爱的事情交叉做，从而让人完成掉不得不做的不熟悉不热爱的事情。
- 利用AI解决繁琐的事情，然后自己专注于知识学习中各种知识网络连接的部分。
Tip
Web3 招聘求职 2025 年终回顾：谁在赚钱，谁在付费打工 ？
可以看出来，国语用户在工资上还有巨大的提升空间，所以保持探索，day1global。
Share_Antigravity爽退cursor
Antigravity相对cursor的优劣：
- Antigravity的Sonnet4.5Thinking不用开特定地区的全局虚拟网卡才能用，虐了cursor
- Antigravity的各种ui细节虐了cursor
- cursor的自动补全内容上还是比Antigravity牛逼
- Antigravity的Sonnet4.5Thinking不会像cursor那样动不动就创建过多的总结文档消耗用户token，虐了cursor
- Antigravity Pro 5小时更新一次配额，而 cursor Pro需要一个月一次，虐了cursor
- Antigravity 对多Agent模式,多workspace协同和网页浏览模式支持得更自然，虐了cursor
- Antigravity 的planning模式可以任意点评，不像cursor那样只有指定选择题
- cursor能够直接结果复制markdown格式，而Antigravity没有复制键
- Antigravity 完美继承cursor里面的vim的自定义的按键配置，比cursor继承不了vscode的vim自定义配置好多了。
- Antigravity 的终端运行以及ssh连接vps运行都比cursor流畅，不会用sandbox把自己卡死。
- cursor缺省设置了中文回复，但是Antgravity没有，默认英文回复我的。
- cursor中断概率好像没Antgravity那么高。
整体优过点远大于不足点，所以退订cursor，转投Antigravity Pro，舒服了。