P1119 灾后重建 我理解的题目意思 给出n个点、m条双向边、点存在的最早时间ti。做查询t时刻点x和y之间的最短距离，若此时无法连通，则输出-1。 $$t_0​≤t_1​≤⋯≤t_{N−1}​$$ $$查询的 t 是不下降的$$ $$1≤N≤200，0≤M≤N×(N−1)/2​，1≤Q≤50000,所有输入数据涉及整数均不超过 10^5$$解题思路 每次查询时遍历小于t的tk,使用floyd算法计算加入点k之和的最短路径长度数组，初始化最短路径长度数组为一个较大的数inf，若f[x][y]=inf则输出-1，否则输出f[x][y]。 代码： #include <iostream> #include <algorithm> #define len 205 using namespace std; int a[len]; int f[len][len]; int n, m; void update(int k) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[i][k] + f[k][j]; } } return; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; f[i][i] = 0; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) f[i][j] = 1e9; } } for (int s = 1; s <= m; s++) { int x, y, w; cin >> x >> y >> w; f[x][y] = f[y][x] = w; } int q; int k = 0; cin >> q; for (int s = 1; s <= q; s++) { int x, y, t; cin >> x >> y >> t; while (a[k] <= t && k < n) { update(k); k++; } if (t < a[x] || t < a[y]) cout << -1 << endl; else { if (f[x][y] == 1e9) cout << -1 << endl; else cout << f[x][y] << endl; } } return 0; } 参考 Time_Rune

P1118 [USACO06FEB] Backward Digit Sums G/S 我理解的题目意思 给两个正整数 n,sum 。将数字从 1 到 n 按某种顺序写下来，然后将相邻的数字相加，得到一个数字更少的新列表,重复这个过程，直到只剩下一个数字,若这个数字等于sum，则输出满足这个条件的字典序最小的序列1~n;否则不输出。 $$1≤N≤12，1≤sum≤12345$$解题思路 数组ai每次相邻相加的过程，最终结果的系数就是杨辉三角的对应行。所以先预处理出c记录杨辉三角系数，再进行深度优先搜索尝试所有顺序，设置一个pos，按字典序尝试数字填入a[pos]，结合剪枝优化时间，在字典序尝试之前先判断已经填入的 a[i]*c[i] 之和是否大于sum，大于则停止搜索。当pos等于n时，判断 a[i]*c[i] 之和是否等于sum。 代码： #include <iostream> #include <algorithm> using namespace std; int n, sum; int a[15],c[15]; bool vis[15]; void ini(){ for(int i=0;i<n;i++){ c[i]=1; for(int j=1;j<=i;j++){ c[i]=c[i]*(n-j)/j; } } } int calc(){ int res=0; for(int i=0;i<n;i++){ res+=a[i]*c[i]; } return res; } bool dfs(int pos){ if(pos==n)return calc()==sum; int csum=0; for(int i=0;i<pos;i++){ csum+=a[i]*c[i]; } if(csum>sum)return false; for(int i=1;i<=n;i++){ if(!vis[i]){ vis[i]=true; a[pos]=i; if(dfs(pos+1))return true; vis[i]=false; } } return false; } int main() { cin >> n >> sum; ini(); if(dfs(0)){ for(int i=0;i<n;i++){ cout<<a[i]<<" "; } } return 0; }

P1115 最大子段和 我理解的题目意思 给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大,输出最大值。 $$1≤n≤2×10^5，−10^4≤a_i​≤10^4$$解题思路 用贪心来做，初始化 ans 为 a1 。从前往后想，维护 bi 记录末尾是 ai 的最大连续子段和，从 a2 开始，设 c=ai+bi ,若 ai≤c ，则 bi=c ；若 ai>c ，则 bi=ai ，每次判断后，维护 ans 为 ans 和 bi 的较大者。 为什么可以这么做？ 第一个数为一个有效序列。 如果一个数加上上一个有效序列得到的结果比这个数大，那么该数也属于这个有效序列。 如果一个数加上上一个有效序列得到的结果比这个数小，那么这个数单独成为一个新的有效序列。 在执行上述处理的过程中实时更新当前有效序列的所有元素之和并取最大值。 代码： #include <iostream> using namespace std; int n,a,b,ans=-0x7fffffff; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a; if(i==1)b=a; else { b=max(b+a,a); } ans=max(ans,b); } cout<<ans; return 0; } 参考 Arahc

P1114 “非常男女”计划 我理解的题目意思 给出一个数组由n个 0 或 1 组成，找出包含相同数目的0和1的最长子数组的长度。 $$1≤n≤10^5$$解题思路 一开始想的很简单，维护一个前缀和数组a记录到当前位置一共多少1，再用一个嵌套for循环遍历子数组，$a[j]-a[i-1]=(j-i+1)/2,j-i+1%2=0$ 满足的条件下输出最大的 j-i+1。注意到 $1≤n≤10^5$ ，O(n²)的复杂度下会超时，需要改换复杂度更低的方法。 O(n)解法：将女视为-1，将男视为1，问题转换为最长的和为0的子数组。用哈希表fs记录前缀和sum，先插入一个 fs[0]=0,再遍历查找是否有 fs[i]=sum ,若有则输出最大的 i-fs[sum] ,否则插入 fs[sum]=i 。 代码： #include <iostream> #include <unordered_map> using namespace std; int n; int main() { cin >> n; unordered_map<int,int>fp; fp[0]=0; int ans=0,sum=0; for (int i = 1; i <= n; i++) { int x; cin >> x; sum+=(x==1)?1:-1; if(fp.find(sum)!=fp.end()){ ans=max(ans,i-fp[sum]); } else{ fp[sum]=i; } } cout<<ans; return 0; }

P1113 [USACO02FEB] 杂务 我理解的题目意思 这是一个图论问题：拓扑排序，题目给出了一个 DAG（有向无环图），n个顶点之间通过有向边连接，顶点具有点权len，要求出任意初始点到任意点之间的任意路径上所有顶点的最大总点权和。 $$3≤n≤10000，1≤len≤100$$解题思路 按照题意模拟即可，维护一个数组v记录任意初始点到点i之间任意路径上所有顶点的最大总点权和，初始点x的v[x]等于自身点权。递归查询（记忆化搜索）非初始点y的所有前缀点qi的v[qi]，v[y]=点权y+max(v[qi])。最后遍历查询v的最大值输出。 代码： #include <iostream> #include <vector> #include <cstring> using namespace std; struct th { int t; vector<int> pre; } sh[10005]; int n; int v[10005], ans = 0; int find(int i) { if (v[i] == 0x3f3f3f3f) { int k = 0; for (int p : sh[i].pre) { k = max(k, find(p)); } v[i] = sh[i].t + k; } return v[i]; } int main() { cin >> n; memset(v, 0x3f, sizeof(v)); for (int i = 1; i <= n; i++) { int x, tx; cin >> x >> tx; sh[i].t = tx; cin >> x; int cnt = 0; while (x != 0) { sh[i].pre.push_back(x); cin >> x; cnt++; } if (cnt == 0) v[i] = tx; } for (int i = 1; i <= n; i++) { ans = max(ans, find(i)); } cout << ans; return 0; }

P1112 波浪数 我理解的题目意思 波浪数是在一对不同数字之间交替转换的数,双重波浪数则是指在两种进制下都是波浪数的数。特别地，只有一位的数也算作波浪数，例如 1。 输入单独一行包含五个用空格隔开的十进制整数 l,r,L,R,k。[l,r] 表示应当考虑的进制的范围，[L,R] 表示应当考虑的数字的范围，k 表示你应该找的波浪数的重数。 输出从小到大以十进制形式输出指定范围内的指定重数的波浪数。一行输出一个数。 $$2≤l≤r≤32，1≤L≤R≤10^7，k∈{2,3,4}。$$解题思路 最暴力的方法肯定是遍历[L,R]的每个数进行[l,r]进制的波浪数检查，然后输出符合需要重数的数。但这样大概率会超时，而且不美观，肯定有更聪明的解法。 我不找数，让数来找我，构造符合[l,r]进制的波浪数，维护一个数组来记录数的波浪数重数，最后顺序输出就可以了。怎么构造呢，枚举两个不同的k进制数i、j，使得在数中i、j交替出现，设置一个标志用于判断何时应该放i何时放j。细节：i从1开始枚举，j从0开始枚举，先在数中放i。 代码： #include <iostream> using namespace std; int v[10000005]; int m, n, l, r, c; int main() { cin >> m >> n >> l >> r >> c; for (int k = m; k <= n; k++) { for (int i = 1; i < k; i++) for (int j = 0; j < k; j++) { if (i != j) { int x = 0, t = 0; while (x <= r) { if (t % 2 == 0) { x = x * k + i; t++; } else { x = x * k + j; t++; } if (x >= l && x <= r) { v[x]++; } } } } } for (int i = l; i <= r; i++) { if (v[i] == c) cout << i << endl; } return 0; } 参考 Crazily

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 引入符号表统一记录常量、变量的属性与内存标识 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 }; 测试遇到一个问题， ...

目的 实现一个能够处理表达式 (一元/二元) 的编译器，编译器将可以处理如下的 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 ...