Attack Lab
Bomb Lab

各位大佬轻拍

两个版

• 把数组分为两部分，逆序对可能在前半部分、后半部分、一个在前半部分一个在后半部分
• 前两种情况可以递归处理
• 第三种情况：如果没有这种逆序对，那么进行归并排序得到mere时，前半部分就 完全在后半部分前面，否则，一旦一个后部分的 x 排到了前半部分的 index 位置，那么它与 index后面所有的前半部分的元素都形成逆序对

三个版

• 同样的，三个元素可能全在前半部分、后半部分，也可能两个在前一个在后、一个在前两个在后
• 递归处理前两种情况
• 如果只有一个在后半部分，那么这一个就是三元组逆序对的最小元素，在归并排序的mere过程中，如果后半部分 某个元素 x 插入到前半部分的index位置，那么index后的所有两元组逆序对与 x 形成 三元组逆序对，
• 重复上一个步骤，但这次是前半部分插入到后半部分，如果 x 插入后半部分的index位置，那么index前的所有后半部分的二元组逆序对与 x 构成三元组逆对
• 代码中前两个步骤可以合起来

http://www.cs.cmu.edu/~213/exams.html

@诟屍

• 先定义符号，s表示字符串，p表示预处理结果
• 确实用KMP的预处理算法，周期等于n-P[n] （n是最后一个字符）
• 子串那个
  • 因为i-p[i]部分刚好是0到i的字符串的最小周期串
  • 所以，如果我们需要求s[p] 到 s[q] 的这个子串，其中 q-p+1 是 q-p[q]的偶数倍，那么q-p[q]就是最小周期（这里有一个漏洞，就是没有证明 一个串如果有多个周期，那么这些周期中大的是小的整数倍）
  • 如果 q-p+1 不是q q-p[]的偶数倍，那么就得用KMP那个预处理算法单独搞。

Hint == Answer 系列

unsigned replace_byte(unsigned x, int i, unsigned char b)
{
	unsigned t = ~0;//构造0xFFFFFFFF
	t -= (1UL<<(i+1)*8) - (1UL<<i*8);//构造诸如0xFF00FFFF
	x = x&t;//通过&清除相应的byte
	x = x|(b<<i*8);
	return x;
}

记得看过一篇文章，不同语言对负数除法的取整方式不同，有的向0方向取整有的向变小方向取整。
所以负数的整数除法的取整应该只是规则，没有对错。然后csapp讲的是计算机硬件的实现方式。

P104有一段

Integer division always rounds toward zero. To define this precisely, let us
introduce some notation $\cdots\cdots$
Thatis, it should round down a positive result but round up a negative one.