Elian's blog page

Dynamic Programming Notes1. 动规五部曲做动态规划题时，可以按下面五步检查： 找 dp[i] 或 dp[i][j] 的含义。 先用一句话说清楚状态表示什么。 状态没定义清楚时，不要急着写递推。 初始化，并思考 dp[0]、dp[1] 等边缘情况。 注意题目数组长度的最小值。 尤其要考虑边界越界的情况。 找中间状态的递推公式。 当前状态从哪些更小或更早的状态转移过来？ 是取最大值、最小值、累加方案数，还是维护真假？ 根据递推公式和思路，确定遍历顺序。 0-1 背包容量倒序。 完全背包容量正序。 区间 DP 按区间长度从小到大。 树形 DP 常用 DFS 回溯。 检查：必要时打印 DP 数组。 dp 可以是一维数组，也可以是二维数组 dp[i][j]。 调试时打印小样例的 DP 表，往往能发现初始化或遍历顺序问题。 2. 0-1 背包2.1 状态定义1dp[i][j]：表示装第 i 件物品为止，在总容量不超过 j 的情况下，物品的最大总价值。 二维转移： 1dp[i][j] = max(dp[i-1][j],...

1. 初始化仓库与关联远程仓库1git init 在当前目录初始化一个 Git 仓库。 12git remote add origin <url>git remote -v git remote add origin <url>：把远程仓库地址添加为 origin。 git remote -v：查看当前关联的远程仓库。 首次推送主分支： 1git push -u origin main -u 会设置本地 main 与远程 origin/main 的跟踪关系，之后可以直接使用 git push / git pull。 2. 查看状态与差异123git statusgit diffgit diff --staged 命令 作用 git status 查看工作区、暂存区状态 git diff 查看工作区尚未暂存的修改 git diff --staged 查看已经暂存、即将提交的修改 3. 添加、移动、删除文件1234git add <file1> <file2>git add .git mv...

Go and Python Environment Management1. Go 常用命令 命令 用途 go run . 编译并运行当前模块 go build ./... 编译所有包 go test ./... 运行测试 go mod init <module> 初始化模块 go mod tidy 清理并同步依赖 go get <pkg> 添加或更新依赖 go fmt ./... 格式化 go vet ./... 静态检查 go doc <pkg> 查看文档 推荐提交前组合： 123go mod tidygo fmt ./...go test ./... 2. Python 环境迁移导出依赖： 1pip freeze > requirements.txt 新环境安装： 123456python -m venv .venv# Linux/macOSsource .venv/bin/activate# Windows...

Hungarian Algorithm Notes二分图定义：一个图是二分图，当且仅当它不包含奇数长度的环。可以使用两种颜色（通常为黑和白）对二分图的顶点进行染色，使得任意一条边的两个端点的颜色不同。 最大匹配数：从图中选出尽可能多的边，使得每条边连接的两个顶点都只被选中一次，即选出最大匹配的边数（即对数）。 最小点覆盖数：选出尽可能少的顶点，使得每条边的两个顶点中至少有一个顶点被选中。 König 定理：二分图中，最大匹配数等于这个图中的最小点覆盖数。 实现匈牙利算法的具体代码下面代码中，左部点可以理解为“男生”，右部点可以理解为“女生”。pr[y] 表示右部点 y 当前匹配的左部点编号。 123456789101112131415161718192021222324252627const int N = 509;vector<int> g[N]; // 邻接表表示的图：g[x] 存储左部点 x 能连接到的右部点int pr[N]; // pr[y] 表示与右部点 y 匹配的左部点编号；0 表示尚未匹配int vis[N]; //...

LCA NotesLCA(Lowest Common...

JavaScript Basics易错点先记 点 结论 let / const / var 现代 JS 优先 const，需要重新赋值时用 let，尽量不用 var。 typeof null 返回 'object'，这是历史遗留问题，不表示 null 真的是普通对象。 Number(undefined) 得到 NaN。 Boolean("0") 和 Boolean(" ") 都是 true，因为非空字符串为真。 ?? 只把 null / undefined 当作“没有值”。 函数声明 vs 函数表达式 函数也是值，可以赋给变量，也可以作为回调传入另一个函数。 箭头函数 适合短回调，但没有自己的 this。涉及对象方法或构造器时要小心。 基础内容1. hello, world!在.html中： 我们可以使用一个 <script> 标签将 JavaScript 代码添加到页面中。 外部的脚本可以通过 <script...

Linux IndexNotes 主题 笔记 适合查什么 文件系统与基础命令 Linux-Filesystem-and-Basic-Commands pwd、cp、rm、cat、less、find、mount、tar、权限、环境变量、APT/Snap 文本处理与管道 Linux-Text-Processing-Pipelines head、tail、wc、grep、sort、uniq、cut、tr、sed、awk、xargs、tee 进程、作业、性能与调试 Linux-Processes-Jobs-Performance-and-Debugging ps、top、jobs、fg、pidof、kill、pkill、time、strace、objdump 网络与 HTTP 调试 Linux-Networking-and-HTTP ss、netstat、ip addr、ip route、ping、dig、curl、wget、端口、DNS、HTTP 状态码 Command...

Prefix Sum and Two Pointers Notes1. 前缀和区间求和类题，问求和满足某某性质的区间有多少个。 如果直接暴力求解大概率超时。 但是，可以进行预处理，比如，将所有前缀求和，得到一个新的数组。 这样，一个区间和就变成了前缀和数组少量的元素间加减的结果。 一维前缀和：1.k倍区间 - 蓝桥云课 二维前缀和：小美的平衡矩阵__牛客网 在构造前缀和数组时候，为了边界处理的方便，数组大小会大一点。然后遍历从idx=1开始 前缀和可以将暴力法的$O(n^{2})$下降到$O(n)$ 1.1 一维前缀和模板1234567vector<long long> pre(n + 1, 0);for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + a[i];}// 区间 [l, r] 的和long long sum = pre[r + 1] - pre[l]; 1.2 二维前缀和模板123456s[i][j] = a[i][j] + s[i - 1][j] +...

SSH Connections and File Transfer本文记录 SSH 登录、密钥认证、端口转发，以及 scp / rsync 远程传文件。 1. 基本连接123ssh username@hostssh -p 2222 username@hostssh username@192.168.1.10 远程执行一条命令： 12ssh user@host "CMD"ssh user@host "uname -a && uptime" 常用调试： 1ssh -v username@host -v 会输出详细连接过程，适合排查认证失败、密钥不匹配、配置文件未生效等问题。 2. 密钥认证生成密钥： 1ssh-keygen -t rsa -b 4096 -C "your_email@example.com" 也可以使用更现代的 Ed25519： 1ssh-keygen -t ed25519 -C...

Tarjan 算法常用于求解： 有向图中的强连通分量（SCC, Strongly Connected Components）； 无向图中的割点； 无向图中的割边，又称桥。 核心思想是 DFS 时间戳和 low 数组。 1. 核心数组 数组 含义 dfn[u] 节点 u 第一次被 DFS 访问到的时间戳 low[u] 从 u 或 u 的子树出发，经过树边和返祖边能到达的最小 dfn 可以直观理解为： dfn 记录“访问顺序”； low 记录“最多能往祖先回到哪里”。 2. 有向图强连通分量 SCC强连通分量指的是有向图中的一个最大点集，其中任意两个点都可以互相到达。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <bits/stdc++.h>using namespace std;const int N = 100005;vector<int> g[N];int dfn[N], low[N],...