背景Stoer-Wagner 算法求解非负边权的无向图全局最小割，即不指定源点和汇点。
割：去掉图上的若干边，使得源点 $S$ 和汇点 $T$ 不再连通。去掉的边的集合称为割。
算法12345678910MinimumCutPhase(G, w, a) A ← {a} while A ≠ V 加入和集合 A 连接最紧密的点，即边权和最大的点 记录当前阶段的割值(CutOfThePhase)，并合并最后加入集合 A 的 2 个点 MinimumCut(G, w, a) while |V| > 1 MinimumCutPhase(G, w, a) 基于现阶段割...
450 Ramen Shop
题意
分析 模拟。
449 Dendrograms
题意（画树状图）
分析 按 Y 值从大到小合并并查集。
448 Controlled Tournament
题意 有 $1\le N\le 16$ 个选手参与锦标赛，已知每对选手之间对阵的比赛结果，求冠军是 $1\le M\le N$ 的方案数。
分析 状压 DP。
447 Optimal Rest
题意 Rest command 使用字符 ‘R’ 和一个停留时长 $t$ 表示，其中停留时长 $t\in\{1,2,4,8,16,32,64\}$，’1’ 表示停 1 拍，’2’ 表示停半拍，’4’ 表...
400 The last hour of the contest
题意 已知 ICPC 封榜前的榜单以及封榜后发放的气球总数，求你所在队伍可能的最高排名和最低排名。
分析 贪心+模拟。
399 Berodoskar Development
题意 给 15×15 的网格图，每个格子有 2 种类型：’X’ 表示蓄水池，’.’ 表示空地。有公共边的 ‘X’ 相互连通成一个大蓄水池。现需要从地图边缘搭建管道引流到至少 2 个蓄水池上，管道可复用。求最少需要的管道长度。
分析 贪心。
398 Friends of Friends
题意 给 50 个人的好友列表。若 c 不是 a 的好友，且存在...
350 XOR-omania
题意 有 $1\le N\le 100$ 个未知的整数序列 $1\le A_i\le 2^{31}$，两两异或得到序列 $B_k=A_i\ \bigoplus\ A_j,1\le k\le \frac {N(N-1)} 2$。已知序列 $B_i$，求序列 $A_i$ 的一种解（保证有解）。
分析 从结果角度入手，假设已知有序列 $A’_i$ 可以得到序列 $B_i$，那么序列 $A_i=A’_i\bigoplus A’_1$ 也能得到序列 $B_i$。假设 $A_1=0$ 也能得到一种解。
在 $A_1=0$ 的条件下，则有 $B_k=A...
350 XOR-omania
题意 有 $1\le N\le 100$ 个未知的整数序列 $1\le A_i\le 2^{31}$，两两异或得到序列 $B_k=A_i\ xor\ A_j,1\le k\le \frac {N(N-1)} 2$，数据保证序列 $A_i$ 大于 2 个元素的任意子集的异或和均不为 0。已知序列 $B_i$，求序列 $A_i$ 的一种解（保证有解）。
分析 从结果角度入手，假设使用序列 $A’_i$ 可以得到序列 $B_i$，那么序列 $A_i=A_1\bigoplus A’_i$ 亦能得到序列 $B_i$。在已知 $A_1=0$ 的条件下，对于所有的 $i$...
300 Train
题意 给定水平/垂直方向的火车轨道顶点顺序，在不发生碰撞的前提下，求火车的最大长度。轨道顶点数为 $1\le N\le 4000$，点坐标 $(x_i, y_i), |x_i|, |y_i|\le 10^4$。
分析 模拟。将点坐标离散化成 $N\times N$ 的网格图，记录当前火车所占据的线段以及车头/车尾坐标，模拟火车行进和碰撞。模拟过程中，记录火车的最大长度。
299 Triangle
题意 有 $3\le N\le 1000$ 个大数 $1\le a_i\le 10^{500}$，找出 3 个数使之能构成三角形的边。
分析 模拟+大数。排序，取相邻的 3...
计划计划一年内（截止 2021 年 1 月 1 日）把 SGU 500 刷完，形式以所有题目给出翻译后的简要题意和解题思路概要。
AC 代码库
题目153 Playing with matches
题意 有 $1\le N \le 10^9$ 根火柴，Little 和 Petya 轮流取，每次能取 $1, P_1, P_2, \dots , P_m(2\le P_i \le 9, 0\le m \le 8)$ 根火柴，判断先/后手必胜。
分析 当 $N$ 较小时，可用 dp 计算火柴为 $n$ 时状态（必胜/必败）。由于 $P_i\le 9$，每个点的状态只与前面的 9 个状态有关，从...
背景：带边权的二分图最大权值完美匹配。
顶标概念：顶点权值 $L_x, L_y$。
可行顶标：所有边 $e(x→y)$ ，都满足 $L_x+L_y\ge W_e$。
注：此时还没有开始匹配，是对原图所有边的限制。
相等子图：包含所有顶点；仅包含 $W_{x→y}=L_x+L_y$ 的边。
问题即转化为求相等子图的完美匹配，此时边权和达到上限 $\sum L_x+ \sum L_y$。
初始化：$L_y=0, L_x=\max_{j\in Y}{W_{x→j}}$ 使得初始方案为可行顶标。
交替路：与匈牙利算法类似，在相等子图中搜索增广路时，如果找不到时我们称此时得到一条交替...
题目Part A. Cache Simuator要求将 valgrind 存储跟踪作为输入，在 csim.c 中实现一个缓存模拟器，结果输出：命中，不命中和驱逐的数量（hit, miss, eviction）。需要支持以下参数输入：
-s：用于组索引的位数。
-E：每组行数。
-b：用于块的位数。
-t：保存 valgrind 跟踪记录的文件。
Valgrind 输出格式为：
1234I 0400d7d4,8 M 0421c7f0,4 L 04f6b868,8 S 7ff0005c8,8
每行格式为 [space]operation address,size，L 表示加载数据，S 表...
