Mcginn's Blog

Mcginn's Blog

make a better version of self

SGU 153-252
计划计划一年内(截止 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 个状态有关,从...
Kuhn-Munkres Algorithm
背景:带边权的二分图最大权值完美匹配。 顶标概念:顶点权值 $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}}$ 使得初始方案为可行顶标。 交替路:与匈牙利算法类似,在相等子图中搜索增广路时,如果找不到时我们称此时得到一条交替...
CSAPP - cachelab
题目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 表...
CSAPP - archlab
知识点 学习流水线化的 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要求在 ncopy.ys ...
CSAPP - attacklab
知识点 在这个实验中,学习利用缓存溢出(buffer overflow)来改变程序的行为,即完成攻击者的目的效果。 需要掌握 x86-64 的栈和参数传递机制,其结构如下图所示。 其中函数 P 调用了函数 Q,返回地址为函数 P 调用位置的下一条指令。实验攻击均修改该返回地址来完成攻击目的。 题目实验中的程序 CTARGET 和 RTARGET 都调用了函数 test: 12345void test() { int val; val = getbuf(); printf("No exploit. Getbuf returned 0x%x\n", val...
CSAPP - bomblab
安装 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 mul...
CSAPP - datalab
自动测试 使用 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》,主要对文章进行翻译,力图简化算法的证明过程并给出相应的结论。简化证明过程可能存在不严谨的地方,如有需要可自行查看参考资料中的论文原文。 太长不看版给定一字符串,对于每个右端点为 $r$ 的回文子串,将左端点记为 $l_1\lt l_2\lt \dots \lt l_k$,记间距 $Δ_i=l_i-l_{i-1}$,结论有: 间距 $Δ_i$ 构成单调递减序列(严格来说,是单调非增序列),即 $\forall i>1,Δ_i\ge Δ...
SGU 100~152
计划计划一年内(截止 2021 年 1 月 1 日)把 SGU 500 刷完,形式以所有题目给出翻译后的简要题意和解题思路概要。 AC 代码库 题目101 Domino 题意 多米诺牌两端标有 0 至 6 的数字,以 形式表示,每张牌均可翻转。要求将 100 个多米诺牌横向放置成一排,相邻的多米诺牌数字需要相同。如 。判断是否存在方案,存在的话给出一种排列。 分析 将数字 0 至 6 视为图上的点,多米诺牌视为无向边,则问题转化成找出一条欧拉路径,而欧拉路径使用搜索+剪枝解决。 102 Coprimes 题意 给定 $1\le N \le 10^4$,求 $[1, N)$ 范围...
Pólya计数法
题目Necklace of Beads来源 POJ 1286 题意 使用 RGB 三种颜色对长为 $0\le n\le 23$ 的项链染色,求本质不同的方案数。一种方案如果经过旋转或翻转得到另一种方案,两种方案视为同一种。 注意 $n=0$ 在本题中会出现,测试数据输出 0。 分析 使用 Polya 计数公式求解,即对于正 $n$ 边形的顶点对称群 \{ρ_n^0=\iota,ρ_n,\dots, ρ_n^{n-1}, τ_1, τ_2, \dots, τ_n \}的循环因子分解。 旋转置换 $ρ_n^i,i=0,1,\dots n-1$ 的循环个数为 \gcd(n, i)证明 ...
avatar
Mcginn
just go