ARST打卡第315周

Linmin.Shan included in ARST

2025-05-18 992 words 2 minutes

Contents

Algorithm

lc1931_用三种不同颜色为网格涂色

思路:

这是N皇后的升级版本，需要状态dp。

需要枚举第一行，然后计算剩下n-1行的涂色方案数。

但是dp手法有点生疏了，和题解学一下。

 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
62
63
64
65
66
67
68
69
70
71
72
73
74


use std::collections::HashMap;

const MOD: i32 = 1_000_000_007;

impl Solution {
    pub fn color_the_grid(m: i32, n: i32) -> i32 {
        let m = m as usize;
        let n = n as usize;
        // 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
        let mut valid = HashMap::new();
        // 在 [0, 3^m) 范围内枚举满足要求的 mask
        let mask_end = 3i32.pow(m as u32);
        for mask in 0..mask_end {
            let mut color = Vec::new();
            let mut mm = mask;
            for _ in 0..m {
                color.push(mm % 3);
                mm /= 3;
            }
            let mut check = true;
            for i in 0..m - 1 {
                if color[i] == color[i + 1] {
                    check = false;
                    break;
                }
            }
            if check {
                valid.insert(mask, color);
            }
        }

        // 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
        let mut adjacent = HashMap::new();
        for (&mask1, color1) in &valid {
            for (&mask2, color2) in &valid {
                let mut check = true;
                for i in 0..m {
                    if color1[i] == color2[i] {
                        check = false;
                        break;
                    }
                }
                if check {
                    adjacent.entry(mask1).or_insert(Vec::new()).push(mask2);
                }
            }
        }

        let mut f = HashMap::new();
        for &mask in valid.keys() {
            f.insert(mask, 1);
        }
        // 滚动数组，f是上一行的状态，g是当前行的状态
        for _ in 1..n {
            let mut g = HashMap::new();
            for &mask2 in valid.keys() {
                let mut total = 0;
                if let Some(list) = adjacent.get(&mask2) {
                    for &mask1 in list {
                        total = (total + f.get(&mask1).unwrap_or(&0)) % MOD;
                    }
                }
                g.insert(mask2, total);
            }
            f = g;
        }

        let mut ans = 0;
        for &num in f.values() {
            ans = (ans + num) % MOD;
        }
        ans
    }
}

Review

魔术告诉你！你正掌控着自己做出的选择吗？【TED演讲】

实际上每个人的认知都是被生长环境和教育塑造的。

有多少是自己的选择呢？让自身舒服的选择就一定是对的嘛？不会是 DNA 的选择吗？

当然，这样追问下去可能没有结果，所以经过自己思考后，想干啥干啥吧，活在当下，开心就好。

Tip

推理加速新范式：火山引擎高性能分布式 KVCache （EIC）核心技术解读

《货币未来：从金本位到区块链》有感 💰📚

“BTC就是最大的meme”？这话有点轻率了 🤔

读完此书，我才明白：BTC凭借四大核心特性 ⚙️

稀缺性（增量存量比）💎
工作证明（POW）⛏️
不可篡改性 🔒
点对点共识记账系统 🌐

这些特性共同构建了BTC的反脆弱生态与正向反馈循环 🔄

BTC与meme的发展路径恰恰相反：BTC先有价值后有狂热，而非从注意力转向价格 📈

体验过BTC转账的人都能感受：10分钟到账、仅收10U手续费 ⚡ 与传统电汇动辄几天等待、高额手续费、繁琐审查相比，就是货币革命！🚀

书中指出，BTC将成为大型转账系统，而小额快捷支付则由其他系统承担 🔄

这与我的观点不谋而合：BTC负责储值（数字黄金🥇），Solana负责日常支付（快速、广泛应用🚀）

既见未来，何不梭啦(Sol @Solana_zh)! 🌞

Contents

ARST打卡第315周

Algorithm

Review

Tip

Share