要求
实现单机 key/value 存储服务，一个 server 和若干 clients。
支持 3 种函数
Put(key, value)：保存和替换 (key, value) 对。
Append(key, arg)：将 arg 补充到 key's value 上并返回旧值
value。
Get(key)：返回 key's value，若不存在 key 则返回空字符串。
注意事项
每个操作需要保持顺序执行。
每个操作可以是线性复杂度，便于观察并发问题。
考虑信息丢失，当 client
不断重试需要保证对应的操作只执行一次。可以假设一个请求不会同时出现。
要求 // Rules
Reduce 任务数量为给定的 ，即 mapper 会生产出 个中间文件用于后续的 reduce
任务。
mr-out-X 文件每行包含一个 reduce 函数输出，每行格式为
%v %v 分别表示 key 和 value。
mapper 输出文件放在当前目录下，以便后续 reducer 作为输入读取。
需要实现 Done() 函数用于表明整个 MapReduce
任务完成。
当整个任务都完成时，需要让 worker
进程也应该退出。一种简单的方案是改造 call() 函数：当 worker
联系不上 coordinator 时，就可以假定 coordinat...
背景
Stoer-Wagner
算法求解非负边权的无向图全局最小割，即不指定源点和汇点。
割：去掉图上的若干边，使得源点 和汇点 不再连通。去掉的边的集合称为割。
算法
12345678910MinimumCutPhase(G, w, a) A ← {a} while A ≠ V 加入和集合 A 连接最紧密的点，即边权和最大的点 记录当前阶段的割值(CutOfThePhase)，并合并最后加入集合 A 的 2 个点 MinimumCut(G, w, a) while |V| > 1 MinimumCutPhase(G, w, a) 基于现阶段割值(CutOfThePhas...
450 Ramen Shop
题意
分析 模拟。
449 Dendrograms
题意（画树状图）
分析 按 Y 值从大到小合并并查集。
448 Controlled Tournament
题意 有 个选手参与锦标赛，已知每对选手之间对阵的比赛结果，求冠军是
的方案数。
分析 状压 DP。
447 Optimal Rest
题意 Rest command 使用字符 'R' 和一个停留时长 表示，其中停留时长 ，'1' 表示停 1
拍，'2' 表示停半拍，'4' 表示停 1/4 拍，以此类推。字符 '.'
表示当前停留时长是前一个停留时长的一半，比如 R1. 表示先停 1
拍，...
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
题意 有 个未知的整数序列 ，两两异或得到序列 ，数据保证序列 大于 2 个元素的任意子集的异或和均不为
0。已知序列 ，求序列 的一种解（保证有解）。
分析 从结果角度入手，假设使用序列
可以得到序列 ，那么序列 亦能得到序列
。在已知 的条件下，对于所有的 有 。
假设得到了 ，可以枚举 ，然后检查 是否都存在，但这只是 的必要不充分条件。
但是题目中还保证了序列 大于
2 个元素的任意子集的异或和均不为 0，也就是说不存在 ，上述条件就是 的充要条件。
349 Wolves and Sheep
题意 有 只羊和
只狼，羊和狼...
300 Train
题意
给定水平/垂直方向的火车轨道顶点顺序，在不发生碰撞的前提下，求火车的最大长度。轨道顶点数为
，点坐标 。
分析 模拟。将点坐标离散化成
的网格图，记录当前火车所占据的线段以及车头/车尾坐标，模拟火车行进和碰撞。模拟过程中，记录火车的最大长度。
299 Triangle
题意 有 个大数 ，找出 3 个数使之能构成三角形的边。
分析 模拟+大数。排序，取相邻的 3 个数判断即可。
298 King Berl VI
题意 个变量 ， 个约束：。要求解 ，且最小化 。判断是否有解，若有解输出任一方案。
分析 差分约束。
差分约束系统 是 元一次不等式组，...
计划
计划一年内（截止 2021 年 1 月 1 日）把 SGU 500
刷完，形式以所有题目给出翻译后的简要题意和解题思路概要。
AC 代码库
题目
153 Playing with matches
题意 有 根火柴，Little 和 Petya 轮流取，每次能取 根火柴，判断先/后手必胜。
分析 当
较小时，可用 dp 计算火柴为
时状态（必胜/必败）。由于 ，每个点的状态只与前面的 9 个状态有关，从而每个状态的 SG
值最大为 10。并且根据 SG 值的定义，前面 9 个状态的 SG 值两两不同，因此 9
个状态的总数约为 。通过找出循环节，即可计算
的 SG 值，从...
背景：带边权的二分图最大权值完美匹配。
顶标概念：顶点权值 。
可行顶标：所有边 ，都满足 。
注：此时还没有开始匹配，是对原图所有边的限制。
相等子图：包含所有顶点；仅包含 的边。
问题即转化为求相等子图的完美匹配，此时边权和达到上限 。
初始化： 使得初始方案为可行顶标。
交替路：与匈牙利算法类似，在相等子图中搜索增广路时，如果找不到时我们称此时得到一条交替路。
如果将交替路中 集合的顶标都 ， 集合的顶标都 ，有以下结论：
如果 在相等子图中，
无变化，即该边仍在相等子图中。
如果
不在相等子图中，当
在交替路而
不在交替路时，
将减少 ，意味着该边有可能加入相等...
题目
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
表示加载数据，...
知识点
学习流水线化的 Y86-64
处理器的设计和实现，深刻理解流水线冒险。
学习循环展开，理解其对程序性能的影响。
题目
Part A
要求
使用 Y86-64 指令集，编写关于 sum_list, rsum_list 和 copy_block 函数的
Y86-64 程序。
做法
参考书本图 4-7 即可，实现也较为简单。
Part B
要求
使用硬件控制语言（HCL）修改 sim/seq/seq-full.hcl，使得处理器支持
iaddq 指令。
做法
iaddq 指令将立即数和寄存器相加，并将结果写回寄存器。
具体参考 irmovq 指令的实现即可。
Part C
要求
在...
知识点
在这个实验中，学习利用缓存溢出（buffer
overflow）来改变程序的行为，即完成攻击者的目的效果。
需要掌握 x86-64 的栈和参数传递机制，其结构如下图所示。
图 1. 通用栈帧结构
其中函数 P 调用了函数 Q，返回地址为函数 P
调用位置的下一条指令。实验攻击均修改该返回地址来完成攻击目的。
题目
实验中的程序 CTARGET 和 RTARGET 都调用了函数 test：
12345void test() { int val; val = getbuf(); printf("No exploit. Getbuf returned 0x%...
安装 GDB
问题一
在 Ubuntu 18.04 LTS 中使用 apt-get install gdb
安装失败。替换使用国内 Ubuntu 的镜像源后安装成功。
首先更新
/etc/apt/sources.list，将该文件内容替换为阿里源：
12345678910deb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiversedeb http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe m...
自动测试
使用 dlc 检测代码是否符合题目要求
1unix> ./dlc bits.c
编译并调用自动测试程序
12unix> makeunix> ./btest
题目
bitXor(x, y)
要求：仅使用 ~ 和 & 完成异或运算。
运算：~ &
做法：画出 & 运算符的真值表，配合 ~
运算符易得。
123int bitXor(int x, int y) { return ~(x&y)&~(~x&~y);}
tmin()
要求：返回二进制补码表示的最小整数。
运算： ! ~ & ^ | + <&...
内容基本是翻译自论文《A Subquadratic Algorithm for Minimum
Palindromic
Factorization》，主要对文章进行翻译，力图简化算法的证明过程并给出相应的结论。简化证明过程可能存在不严谨的地方，如有需要可自行查看参考资料中的论文原文。
太长不看版
给定一字符串，对于每个右端点为
的回文子串，将左端点记为 ，记间距 ，结论有：
间距
构成单调递减序列（严格来说，是单调非增序列），即 。
间距 不超过 种。
基于上述 2 点结论，可以在 时间内利用端点 的信息计算得到
的回文左端点，进而对字符串进行回文分解。
时间复杂度 ，...
计划
计划一年内（截止 2021 年 1 月 1 日）把 SGU 500
刷完，形式以所有题目给出翻译后的简要题意和解题思路概要。
AC 代码库
题目
101 Domino
题意 多米诺牌两端标有 0 至 6 的数字，以 <a, b>
形式表示，每张牌均可翻转。要求将 100
个多米诺牌横向放置成一排，相邻的多米诺牌数字需要相同。如 <1,
2><2, 4>。判断是否存在方案，存在的话给出一种排列。
分析 将数字 0 至 6
视为图上的点，多米诺牌视为无向边，则问题转化成找出一条欧拉路径，而欧拉路径使用搜索+剪枝解决。
102 Coprimes
题意...
题目
Necklace of Beads
来源 POJ
1286
题意 使用 RGB 三种颜色对长为
的项链染色，求本质不同的方案数。一种方案如果经过旋转或翻转得到另一种方案，两种方案视为同一种。
注意
在本题中会出现，测试数据输出 0。
分析 使用 Polya 计数公式求解，即对于正 边形的顶点对称群 的循环因子分解。
旋转置换 的循环个数为 证明 旋转置换中的每个元素在一个有向圈 ，其中 是最小正整数。那么 ，令 ，则 。所以有向圈的长度为 ，个数为 个。
根据定理 3 可得，
反射置换 需要根据 的奇偶性考虑。
当 为奇数时，有
个关于角点与其对边中点...
简介
简单来说，B-Tree
是针对大数据存取的平衡树，考虑了磁盘读取对查找效率的影响。
B-Tree
的主要思想是通过减少磁盘读取次数来提高数据存取性能，而磁盘读取次数与树高相关。故B-Tree
允许每个节点拥有多于 2 个的子节点来减小树高。
与二叉平衡树类似，B-Tree
中的每个节点存储若干键值（keys）以及子节点地址。
图 1. B-Tree 结构图
定义和性质
阶（order）：将子节点的允许最大数量定义为阶，如图 1
为 5 阶树。
阶的 B-Tree 满足以下定义：
每个节点最多能有
个子节点。
每个内部节点至少有 个子节点，内部节点（Internal
n...
简介
AhoCorasick 算法（简称 AC
自动机），解决多模式串的字符匹配问题，即给定若干个单词串 ，求在文本串 中的出现位置。KMP
算法解决单模式串的字符匹配，所以 AC 自动机可认为是 KMP 算法的扩展。
预备知识
字典树（Trie）：树上任意节点到根的路径所构成的子串，记为 ，都是某个插入串的前缀。
KMP 算法：利用最长前后缀完成线性匹配。
核心思想
AhoCorasick 本质上与 KMP
算法是一样的，都是通过相同前后缀减少重复计算问题，只是数据结构不同。
对应于 KMP，AC
自动机需要构建最长公共前后缀（LCPS，Longese Common
proper...
KMP 算法解决在文本串（text）快速找出单词（word）的所有出现位置。
暴力匹配的时间复杂度为 ，而 KMP
算法通过引入最长前后缀，将检索的时间复杂度降至线性。
最长前后缀
lps indicates longest proper prefix which is also suffix.
最长前后缀（LPS, Longest proper Prefix and
Suffix）表示既是原串
的真前缀也是后缀的最长子串 ，其中
。
检索过程
假设已知单词串的每个前缀 的最长前后缀长度 ，且已经匹配 。继续匹配有两种情形：
，则匹配长度
+1。
，此时显然要重新找单词串的一...
