P1111 修复公路 我理解的题目意思 这是一个图论问题，给出N个点(x,y)、M个双向边及边权t。若无法生成连通图则输出-1，若可以连通则给出连通时最大边权的最小值。 $$1≤x,y≤N≤10^3，1≤M,t≤10^5。$$解题思路 使用并查集进行点的合并查找，维护s:并查集数组，初始化并查集，每个节点指向自己,合并操作: void together(int *b, int a, int *s) { if (s[*b] == *b) { // b没有祖先时 s[*b] = a; // 令a为b的父亲 } else { together(&s[*b], a, s); // 否则继续找b的祖先 } } a为要成为父节点的节点，b为要合并的节点，一直找直到b没有祖先即指向自己的节点，令a为b的父亲。 查找操作： int findfather(int *s, int x) { if (x != s[x]) { // 不是最老祖先 s[x] = findfather(s, s[x]); // 路径压缩，直接指向最老祖先 } return s[x]; // 返回最老祖先 } 即查找最老祖先并返回，加一个路径压缩，查找到后直接指向最老祖先。 使用Kruskal算法生成最小树，先对边按边权排序，然后遍历所有边，检查两个顶点是否属于同一集合，否则合并两个集合，更新最大边权。 同时记录已连接的边数，用于判断是否连通。 代码： #include <iostream> #include <vector> #include <unordered_map> #include <algorithm> #include <cstring> #include <set> using namespace std; // 全局变量 int N, M, ans; // N:村庄数, M:道路数, ans:最小树中的最大通路时间 // 图的边结构 struct E { int a; // 顶点a int b; // 顶点b int t; // 修复时间 }; // 快速排序函数（对边按权重从小到大排序） void SORT(E *e, int left, int right) { if (left >= right) return; int i = left, j = right; E pivot = e[left]; while (i < j) { while (i < j && e[j].t >= pivot.t) j--; if (i < j) e[i++] = e[j]; while (i < j && e[i].t <= pivot.t) i++; if (i < j) e[j--] = e[i]; } e[i] = pivot; SORT(e, left, i - 1); SORT(e, i + 1, right); } // 并查集的合并操作 // b:要合并的节点, a:要成为父节点的节点, s:并查集数组 void together(int *b, int a, int *s) { if (s[*b] == *b) { // b没有祖先时 s[*b] = a; // 令a为b的父亲 } else { together(&s[*b], a, s); // 否则继续找b的祖先 } } // 并查集的查找操作（路径压缩） int findfather(int *s, int x) { if (x != s[x]) { // 不是最老祖先 s[x] = findfather(s, s[x]); // 路径压缩，直接指向最老祖先 } return s[x]; // 返回最老祖先 } // Kruskal算法生成最小树 int TREE(E *e, int *s) { int i, total = 0; // 对边按权重从小到大排序 SORT(e, 1, M); // 遍历所有边 for (i = 1; i <= M; i++) { // 检查两个顶点是否属于同一集合 if (findfather(s, e[i].a) != findfather(s, e[i].b)) { // 合并两个集合 together(&s[e[i].a], s[e[i].b], s); total++; // 记录已连接的边数 ans = e[i].t; // 更新最大边权（因为边已排序，最后加入的就是最大的） } } return total; } int main() { int i; int s[100010]; E e[100010]; // 输入村庄数和道路数 cin >> N >> M; // 初始化并查集，每个节点指向自己 for (i = 1; i <= N; i++) { s[i] = i; } // 输入每条道路的信息 for (i = 1; i <= M; i++) { cin >> e[i].a >> e[i].b >> e[i].t; } // 生成最小树，并返回边数 int c = TREE(e, s); // 判断是否所有村庄都连通 if (c != N - 1) { // N个节点的树需要N-1条边 ans = -1; // 无法连通所有村庄 } // 输出结果 cout << ans << endl; return 0; } 参考 Euler_Pursuer
编译实践Lv4~Lv9
Lv4 引入符号表统一记录常量、变量的属性与内存标识 1 2 3 4 5 6 struct SymbolInfo { bool is_const; // 常量 or 变量 int const_val; // 常量值（编译期已知） string alloc_name; // 变量的 alloc 指令名，如 "@x" }; unordered_map<string, SymbolInfo> symtab; 操作： AddConst(name, val) — 插入常量（同时做重复定义检查） AddVar(name, ...) — 插入变量 + 生成 alloc i32 指令 Lookup(name) — 查询符号 当前仅支持单层作用域（函数体 Block），无嵌套 Block，因此使用单一 unordered_map。若后续实验引入嵌套作用域，可扩展为栈式符号表（进入 Block 时 push 新表，离开时 pop）。 Lv5 Lv4 用 is_return bool 区分两种语句，Lv5 需要支持 4 种，改用 kind 枚举，重构StmtAST : 1 2 3 4 5 6 7 8 9 class StmtAST : public BaseAST { public: enum Kind { RETURN, ASSIGN, EXP_STMT, BLOCK }; Kind kind; unique_ptr<BaseAST> exp; // RETURN / EXP_STMT unique_ptr<BaseAST> lval; // ASSIGN unique_ptr<BaseAST> assign_exp; // ASSIGN unique_ptr<BaseAST> block; // BLOCK }; 测试遇到一个问题， ...
编译实践Lv3.表达式
目的 实现一个能够处理表达式 (一元/二元) 的编译器，编译器将可以处理如下的 SysY 程序： int main() { return 1 + 2 * -3; } 实现 Lv3.1. 一元表达式 新增/变更的语法规范： Stmt ::= "return" Exp ";"; Exp ::= UnaryExp; PrimaryExp ::= "(" Exp ")" | Number; Number ::= INT_CONST; UnaryExp ::= PrimaryExp | UnaryOp UnaryExp; UnaryOp ::= "+" | "-" | "!"; 设计 AST 时，我只为 ::= 左侧的符号设计一种 AST, 使其涵盖 ::= 右侧的所有规则。 AST.h 添加 ExpAST, PrimaryExpAST, UnaryExpAST，我使用bool标志区别实现右侧的多种规则，更新 StmtAST，原来只支持num，改成exp。 sysy.y 添加语法规则 for Exp, UnaryExp, PrimaryExp, UnaryOp; 更新 Stmt rule ...
编译实践Lv2.初试目标代码生成
目的 实现一个能处理 main 函数和 return 语句的编译器, 同时输出编译后的 RISC-V 汇编。 编译器会将如下的 SysY 程序: int main() { // 摊牌了, 我是注释 return 0; } 编译为对应的 RISC-V 汇编: .text .globl main main: li a0, 0 ret 或: .text .globl main main: li t0, 0 mv a0, t0 ret 实现 Lv2.1. 处理 Koopa IR 这一节的任务是建立内存形式的 Koopa IR。 libkoopa 中的接口并没有我定义的AST数据类型，所以可以先把 Program Dump 到 string 中，再用koopa_parse_from_string解析这个 string，得到内存形式的 Koopa IR。 Lv2.2. 目标代码生成 这一节的任务是生成 RISC-V 汇编。 可以写一个头文件和cpp文件（ASMGenerator.h,ASMGenerator.cpp）专门用来生成汇编。在ASMGenerator.h中声明需要用到的函数， class ASMGenerator { public: ASMGenerator(std::ostream &os) : os(os) {} void Generate(const koopa_raw_program_t &program); private: // DFS 遍历族 void Visit(const koopa_raw_program_t &program); void Visit(const koopa_raw_slice_t &slice); void Visit(const koopa_raw_function_t &func); void Visit(const koopa_raw_basic_block_t &bb); void Visit(const koopa_raw_value_t &value); // 辅助 void EmitPrologue(); void EmitEpilogue(); // 共享状态 std::ostream &os; int frame_size = 0; // 对齐后的栈帧大小 std::string cur_func; // 当前函数名（已去 @） }; 在ASMGenerator.cpp分别实现这些函数， ...
博客框架迁移：从 Jekyll 到 Hugo
前言 之前的博客基于 Jekyll + Hux Blog 主题，用了快一年，总觉得不太顺手。Jekyll 是 Ruby 生态，本地构建慢，主题样式偏重（大图背景、多栏布局），对我这种只想简洁写文章的人来说有点臃肿。 于是决定迁移。目标是： 🚀 更快的构建速度 🎨 极简的页面风格 —— 无背景图、干净利落 🔧 少折腾 —— 配置简单，开箱即用 📝 保留所有文章和资源 最终选择了 Hugo + PaperMod 主题。 为什么选 Hugo？ 特性 Jekyll Hugo 语言 Ruby Go 构建速度 ~5-10 秒 ~250ms 安装 需 Ruby + Gem 单二进制 配置 _config.yml hugo.toml 主题生态 丰富 丰富 Hugo 最大的优势就是快——单二进制文件，没有任何依赖，构建 55 篇文章只要 250ms。PaperMod 主题默认就是白色极简风格，没有大图背景，几乎没有需要改动的地方。 迁移做了什么 1. 文章转换（55 篇） 原来的 Jekyll 文章格式： 1 2 3 4 5 6 7 8 9 --- layout: post title: "Introduction to Linear Programing" date: 2025-09-14 23:54:39 +0800 author: "farmer3-c" header-img: "img/post-bg-2015.jpg" mathjax: true tags: [] --- 转换为 Hugo 格式： ...
wsl2到wsl1
前因 之前想在Windows上使用Linux系统，wsl很方便（为Windows用户提供了Linux环境，不需要装系统什么的）。但是不知道为什么，启动wsl的时间越来越长，从一开始的十几秒到后来的几分钟，实在让我不能忍受。我原来使用的是WSL 2，发现WSL 1 不依赖 Hyper-V 虚拟化，它直接共享 Windows 主机的 IP，启动会很快，所以试试转为 WSL 1。 过程 在 PowerShell 中逐条执行以下命令： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # 1. 备份当前环境 wsl --export Ubuntu-22.04 D:\wsl-backup.tar # 2. 转换为 WSL 1 wsl --set-version Ubuntu-22.04 1 # 3. 彻底重启 WSL wsl --shutdown # 4. 测试启动速度 Measure-Command { wsl -d Ubuntu-22.04 --exec true } # 5. 测试网络 wsl -d Ubuntu-22.04 # 进入 WSL 后，运行： ping baidu.com 结果： ...
本地文件目录推送到GitHub上同名空repository
在 GitHub 建同名、完全空的仓库（不要勾选 README/.gitignore），本地目录用 git init→git add .→git commit→git remote add origin→git push -u origin main 即可一次性推上去。 下面是完整操作（Windows/Mac/Linux 通用）： 一、准备工作 安装 Git： 终端输入： 1 git --version 能显示版本就说明已安装；没有就先装 Git。 在 GitHub 建同名空仓库 右上角点 + → New repository Repository name：和你本地文件夹同名 不要勾选：Add a README file、.gitignore、License 点 Create repository 复制仓库地址（HTTPS 或 SSH），例如： 1 https://github.com/你的用户名/仓库名.git 二、本地操作 打开终端（Git Bash / Terminal / PowerShell），进入你要上传的本地目录根目录： 1 cd /path/to/你的本地文件夹 # Windows 示例：cd D:\my-project 1. 初始化为 Git 仓库 1 git init 2. 添加所有文件到暂存区 1 git add . （想忽略某些文件，新建 .gitignore 写规则，比如 node_modules/、*.log） ...
编译实践Lv1.main函数
目的 实现一个能处理 main 函数和 return 语句的编译器.编译器可以将如下的 SysY 程序: int main() { // 注释也应该被删掉哦 return 0; } 编译为对应的 Koopa IR: fun @main(): i32 { %entry: ret 0 } 实现 Lv1.2. 词法/语法分析初见 我使用项目提供的c++模板，直接执行： make build/compiler -koopa hello.c -o hello.koopa 输出： int main() { return 0; } 这是因为默认的模板使用string存放ast，所以输出的ast也是string形式： CompUnit : FuncDef { ast = unique_ptr<string>($1); } ; Lv1.3. 解析 main 函数 这里设计一个ast用于输出程序的语法结构，教程写的已经很详细了：写一个头文件来定义AST,对于头文件重复声明的问题，加上#pragma once就可以解决。 我是这样定义基类和子类进行构造的： // 所有 AST 的基类 class BaseAST { public: virtual ~BaseAST() = default; virtual void Dump() const = 0; }; // CompUnit 是 BaseAST class CompUnitAST : public BaseAST { public: // 用智能指针管理对象 std::unique_ptr<BaseAST> func_def; void Dump() const override { std::cout << "CompUnitAST { "; func_def->Dump(); std::cout << " }"; } }; …… 同时，修改参数类型的相关声明：比如%parse-param { std::unique_ptr<string> &ast } 改为%parse-param { std::unique_ptr<BaseAST> &ast } ...
Windows磁盘合并
前因 C盘越来越满，D盘和E盘还有许多空间，磁盘合并理所当然的成为了一个缓解C盘压力的解决方案。 想法 我的想法是将D盘的文件都挪到E盘，然后腾出D盘的空间来分配到C盘和E盘。考虑到我习惯使用D盘存放应用，所以我打算之后将E盘的盘符改成D。 处于方便和迅捷考虑，我使用robocopy "D:\" "E:\D盘备份" /E /J /MT:8 /R:3 /W:1复制D盘文件到E盘的一个文件夹，效果还不错。于是在完成修改后我同样使用robocopy D:\D盘备份 D:\ /E /MIR来将配置带到新的D盘，殊不知这会带来怎么样的灾难😭 过程 我使用MiniTool Partition Wizard进行磁盘操作。由于原来D盘删除后的内存与C盘之间存在恢复分区，C盘只能合并它右侧的空间，所以要move恢复分区，这就为C盘扩容了。 然后是将剩余空间合并到E盘，结果因为BitLocker而合并不了，解密之后顺利合并。 最后，灾难性的一幕发生了，使用robocopy D:\D盘备份 D:\ /E /MIR后，修改后D盘空了。 可能的原因是：带 /MIR 的 robocopy 命令在执行时，先清空了 D 盘根目录，再尝试复制备份文件，但中途因为 $RECYCLE.BIN 报错中断，导致备份文件也被系统误删了。 数据恢复工具需要的时间太长了，被删除的数据也没有很重要的，我就先配置了日常要用的工具草草了结了，剩下的日后再说。
Flex 和 Bison 教程
说明：本篇内容译自 Santa Clara University COEN 259 编译原理课程讲义，用于学习 Flex 和 Bison 编译器工具。 本篇内容为个人学习，不构成任何商业用途。 Flex Flex 是一个用于词法分析的扫描器生成工具，它基于有限状态机 (FSM)。输入是一组正则表达式，输出是根据输入规则实现扫描器的代码。 为了实现计算器的一个扫描器，我们可以将文件 “cal1.l” 编写如下： /* this is only for scanner, not link with parser yet */ %{ int lineNum = 0; %} %% "(" { printf("(\n"); } ")" { printf(")\n"); } "+" { printf("+\n"); } "*" { printf("*\n"); } \n { lineNum++; } [ \t]+ { } [0-9]+ { printf("%s\n", yytext); } %% int yywrap() { return 1; } int main () { yylex(); return 0; } 这是用于构建扫描器的 Makefile： ...