《算法竞赛进阶指南》笔记

发表于 2023-07-04 更新于 2025-01-28

《算法竞赛进阶指南》笔记

0x00基本算法

0X01位运算

计算机读入原码A，然后将读入的原码转为补码B，接下来对补码进行运算得到运算后的补码C，最后将补码C转换为原码D输出。
要注意%1这种特殊情况。任何数%1都是0。
回忆这道题：$1 \le a \le 10^{18},1 \le b \le 10^{18}$,$1 \le p \le 10 ^ {18}$,输出$a \times b$。这道题有两种解法。
回忆：起床困难综合症
写状压动规时，如果遇到不知道按照什么顺序遍历状态的情况，可以直接for (int i=0; i<(1 << n); i++)来遍历，可以保证求解后继状态时前驱状态已经求解完毕。
注意如果要读入一个$n$行$m$列的字符矩阵，要用$n$个字符数组来读，切忌不可用单个字符读入，在linux系统下会出错。
x >> 1会将x向下取整，而x / 2会将x向零取整。

0x02递归与递推

数组要开大开大开大！！！
求一个数的约数和，可以先将其质因数分解。如要求$n$的约束和，质因数分解得到$n = \prod_{i = 1}^np_i ^{s_i}$，然后$n$的约数个数为$\prod_{i = 1}^n(s_i + 1)$,约数和为$\prod_{i = 1}^n \sum_{j = 0}^{s_i}p_i^j$。
将一个数分解质因数的时候要注意处理$ > $的质因数。这类质因数如果有就只有1个，但千万要注意！！！！

0x03前缀和与差分

回忆一下这道题。
要用abs函数的话还是引用cmath库，不要手写。手写abs函数可能会引发ambiguous编译错误。
回忆一下这道题。

0x04二分

初赛的考点。二分的写法要么是mid = (l + r) >> 1,l = mid + 1,r = mid，要么是mid = (l + r + 1) >> 1,l = mid,r = mid - 1。
实数域上的二分，通常eps设为$10^{-(k + 2)}$,其中$k$是要保留的小数位数。有时候精度不易确定，就干脆固定循环次数，可以这样写：
1
2
3
4
5
6
for (int i=0; i<100; i++) {
double mid = (l + r) / 2；
if (check(mid))
l = mid; else
r = mid;
}
回忆一下这道题。
如果你的答案是一个实数，而题目要求你向下取整，你就要小心，不能直接用floor(),因为你的浮点数会有误差，比如1.5会变成1.499999999999999999999075。所以如果题目要求你保留4位，你就直接将整个计算过程用整数来实现，同时将整数扩大1000倍来保证精度。
用这种写法
1
2
3
4
5
6
while (l < r) {
mid = (l + r) >> 1;
if (check(mid))
l = mid + 1; else
r = mid - 1;
}
$\hspace{1cm}$ 要注意while循环外面最后还要check一下l，因为最后l也是一个可能的答案，但是你的while条件是l < r,当l = r时会扼杀这种可能性。
证明：对于任意有向完全图存在Hamilton路径
三分求单峰函数最值时，对于区间$[l,r]$,三分得到两个点$m1,m2$。则接下来枚举的是** “较差” **的那个点与离这个点较远的一个端点（l或r)构成的区间。

0x05排序

lower_bound用法：int p = lower_bound(a + 1,a + n + 1,x) - a。注意返回的是第一个小于等于x的数的下标。
unique用法:int p = unique(a + 1,a + n + 1) - a - 1。
可以用一个大根堆和一个小根堆来维护一个不断加数的序列的第$k$大数。比如这道题和这道题.
回忆这道题。
遇到要开long long的时候还是define int long long比较保险。
两个相邻的数之间的交换最多只会增加或减少一个逆序对，也有可能逆序对个数没有变化。Problem for this.
回忆一下这道题。这题的结论是：
- 对于奇数码问题，两个局面可互相到达当且仅当将两个局面写成一维序列后两个序列的逆序对个数奇偶性相同。
- 对于偶数码问题，两个局面可互相到达当且仅当将两个局面写成一维序列后两个序列的“逆序对数之差”和“两个局面下空格所在的行数之差”奇偶性相同。
该结论的充分性尚未证明。
一个启示：一些移动问题都可以弄成一维来看，环的话可以断成链来考虑。
运用奇偶性时的技巧：如果操作值是累加/减的，那么使正确的操作值为偶数，因为偶数 $\pm$ 偶数 = 偶数。如果操作值是累乘,则使正确的操作值为奇数，那么这样可以保证只要一个错误的操作出现，最后的结果可以显示为错误。

0x06倍增

回忆这道题。
回忆这道题。

0x07贪心

回忆problem 1和problem 2和problem 3。
problem 4 problem5.
vector的size()返回值是一个unsigned int,所以对其-1或减去一个数时要慎重。

0x00习题集

开long long!!!!!!
problem 1
problem 2
problem 3
problem 4 (这道题虽然你做出来了，但是还是要看一下的！）
problem 5(注意取值范围！）

0x10基本数据结构

0x11栈

problem 1回忆这道题以及它的思想！
后缀表达式计算方式：

遇到数就入栈，遇到符号就取出栈顶两数运算，并将运算结果重新入栈。
中缀表达式转后缀表达式：

遇到数就输出。

遇到左括号就入栈。

遇到右括号就一直弹出并输出栈中符号，直到遇到左括号。

遇到运算符，若栈顶运算符等级不低于新符号，则一直去除栈顶并输出，最后把新符号入栈。

最后依次取出并输出栈中的剩余符号。

0x12 队列

0x13 链表

problem 1

0x14 Hash

0x15 字符串

p75 最小表示法

0x16 Trie

0x17 二叉堆

0x18 Huffman 树

problem 1

习题集

problem 1
problem 2
problem 3
problem 4
算了都看一遍吧。

0x30数学知识

0x31 质数

阶乘分解

0x32约数

problem1
神仙题
problem2
欧拉函数：详见《欧拉函数学习笔记》
problem 3
(a & b) ^ (a & c) = a & (b ^ c)。

0x40 数据结构

线段树你的写法要开8倍空间！！！
留坑：cdq分治，莫队，可持久化数据结构

0x50动态规划

注意：最大值和最小值一定要初始化，不能任其为0，否则会出问题。
建图的first，last，nxt数组在多组数据时都要初始化！！！！

0x60图论

注意：hash是关键字，不要用它作为变量名或函数名！！！
很巧妙的一道题！

Tips

遇到和式一定要分开来考虑，就是说$\sum_{i = l}^ r(A + B) = \sum_{i = l}^rA + \sum_{i = l}^rB$,可以保证，分开来考虑一定更简单。

0xFF 血的教训

对$n$进行质因数分解时，先找到在1到根号n之间的所有质数，然后，千万不要忘记，n还可能有一个大于根号n的质因数，这个质因数可以是n，也可以不是n！
入队时不要写成q[--tail] = q[tail + 1];,写成这样:tail--; q[tail] = q[tail + 1];
后缀数组初始化要记得把sa,t1,t2都清空！还有记得c数组的大小要开到字符串长度！
后缀数组在build—height的时候要注意i的循环要从1开始循环，然后判断rnk[i] == 1时跳过，i循环不能直接从2开始！

正确写法见后缀数组那篇文章

$a^b$对m取余的结果等于$a^{b \% \varphi(m)}$对m取余的结果，注意加粗处是m，不是$\varphi(m)$!!

树状数组query时要记得return ans！！！

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

char s[105];

int main() {
	int i = 100;
	for (i=5; i<6; ++i)
		i = i;
	
	int j = 100;
	for (j=5; j>5; ++j)
		j = j;
	
	printf("i = %d\n",i);
	printf("j = %d\n",j);
	return 0;
}

请说出输出的结果

C++ 右移是算术右移，空出来的位用符号位补