$$《算法竞赛进阶指南》0x10 基本算法$$
0x01 位运算
- 简介
位运算是个很神奇的东西,但是我讨厌它,利用它能够解决很多看起来很难的问题,还能提高算法的效率(%%%)
bit是度量信息的单位,只有$0$和$1$两种状态。 - 基本运算符:
& 与 两个都为真
| 或 有一个为真就为真
! 非 真变假假变真
^ 异或 相同为0不相同为1
功能 示例 位运算
去掉最后一位 (101101->10110) x >> 1
在最后加一个0 (101101->1011010) x << 1
在最后加一个1 (101101->1011011) (x >> 1)+1
把最后一位变成1 (101100->101101) x | 1
把最后一位变成0 (101101->101100) (x | 1)-1
最后一位取反 (101101->101100) x ^ 1
把右数第k位变成1 (101001->101101,k=3) x | (1 << k-1)
把右数第k位变成0 (101101->101001,k=3) x & ~ (1 << k-1)
右数第k位取反 (101001->101101,k=3) x ^ (1 << k-1)
取末三位 (1101101->101) x & 7
取末k位 (1101101->1101,k=5) x & (1 << k)-1
取右数第k位 (1101101->1,k=4) (x >> k-1) & 1
把末k位变成1 (101001->101111,k=4) x | (1 << k)-1
末k位取反 (101001->100110,k=4) x ^ (1 << k)-1
把右边连续的1变成0 (100101111->100100000) x & (x+1)
把右起第一个0变成1 (100101111->100111111) x | x+1
把右边连续的0变成1 (11011000->11011111) x | x-1
取右边连续的1 (100101111->1111) (x ^ x+1) >> 1
去掉右起第一个1的左边 (100101000->1000) x & (x ^ x-1)
呃这里排版有点问题大佬们别生气……
接下来这一小部分的转自这里
- 补码
int 32位 首位符号位,如果是0为正数,为1为负数。
1: 0000000000...01
2: 0000000000...10
3: 0000000000...11
1 + x = 000000000...00
x = 1111111111...11
1 + 1111111111...11 = 0000000000...00
2 + 1111111111...10 = 0000000000...00
x + ??????????...?? = 0000000000...00
? = ~x + 1
~x + 1 是 x 的补码
-n = ~n + 1
小技巧
数组初始化memset(f,0x3f,sizeof(f))
左移运算符 <<
二进制 : 1 -> 10 -> 100 -> 1000
十进制 : 1 -> 2 -> 4 -> 8
综上所述:1 << n == 2^n
右移运算符 >>
二进制 : 1000 -> 100 -> 10 -> 1
十进制 : 8 -> 4 -> 2 -> 1
综上所述: n >> x == n / (2^x)
-
枚举子集
- 显然,对于 $x$ 的二进制表示,我们可以用 $O(x)$ 的时间暴力求出它的所有子集。
- 但是这样的复杂度显然是不优的,所以考虑优化。
for (int i = x; i; i = (i - 1) & x)
这样可以直接枚举下一个子集。- 为什么呢?因为观察到上一个算法中我们每次都暴力减一,产生了许多不必要的 1。
- 那么我们取与操作,就可以把这些多余的 1 去掉。
- 所以与操作之后,就是下一个子集。
-
快速幂
求 m^k mod p,时间复杂度 O(logk)。
int qmi(int m, int k, int p) {
int res = 1 % p, t = m;
while (k) {
if (k & 1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
0x02 递推与递归
递推是已知的问题边界向原问题推导
递归是把原问题转化成相似子问题进行求解,到边界以后回溯
接下来是递归的基本操作:
- 缩小问题状态空间的规模。
- 尝试求解规模缩小后的问题,可能成功,也可能失败。
- 如果成功,就将答案拓展到当前问题。如果失败,就回到当前问题,查找别的路线,知道确定当前问题无解。
分支法把一个问题划分为若干个更小规模的同类子问题,对子问题进行递归求解,然后在回溯的时候通过这些答案来推导出原问题的解。
0x03 前缀和与差分
- 前缀和
一维前缀和
给定一个数列$A$,它的前缀和数列$S$是能够通过递推得到的基本信息之一。
hh这里公式Σ不知道怎么打就用比较土的方式描述吧……
$S[i] = A[1] + A[2] + A[3] + ...... + A[i]$
如果要求数列$A$从下标$l$到下标$r$的和,可以转化为这样:
$A[l] + A[l + 1] + A[l + 2] + ...... + A[r]$就相当于$S[r] - S[l - 1]$
注意!是$l - 1$!不然A[l]就没有算进去!
二维前缀和
这里公式更不会打了………………就直接用代码吧…………(大佬勿喷)
for (int i = 1;i <= x; i++)
for (int j = 1;j <= y; j++)
s[x][y] += a[i][j];
但是如果每一个$s_{x,y}$都这么算的话……效率太低了!!!
于是我们就要推导公式。
我不想写了我很懒,直接截图吧…………
这个公式的推导用到了容斥原理~以后会整理到
//定义数组
int s[5010][5010], a[5010][5010];
//读入数组a
blablabla......
//利用公式算出数组s
for (int i = 1;i <= n; i++)
for (int j = 1;j <= m; j++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
- 差分
给定数列A,它的差分数列B定义为:
$B[1] = A[1], B[i] = A[i] - A[i - 1], 2 <= i <= n$
0x04 二分
二分,非常好用!(但是不如STL的map好用,你想知道的话……)
有看过我帖子的人应该知道了……小小声:我二分元素第一次出现的位置……这道题用了map(啊啊啊不是AcWing上的啊……)
知道为什么我用map代替二分吗?
因为据说只有 $10$% 的程序员能够写对二分!
二分的实现方法有很多,但是细节的地方确实应该仔细进行考虑。
例如我二分写成了死循环……
……
……
……
悲剧悲剧……
二分的基础用法是在单调序列或者单调函数中进行查找。
二分的模板嘛……看蓝皮书去……(我真是太懒了)
0x05 排序
说到这个我不知道为什么自己异常激动……
这个是最短的一个小节因为……
自己点这里吧!
或者这里也是阔以滴~
好啦这个小节拜拜啦
………………………………
0x06 倍增
倍增…………
听说可能也许应该大概似乎大约约莫小概率……
不就是吗!废话这么多……(但这确实是我说出来的啊……)
vector利用了倍增的思想……
废话……当然是!
划重点!倍增就是成倍增长的意思(继续废话……)
指在我们进行递推时,如果状态空间特别非常超级(一堆废话)很大,通常的线性递推无法满足时间与空间复杂度的需求,我们就可以通过成倍增长的方式,只递推状态空间中在2的整数次幂位置上的值作为代表。
还有就是ST算法也是倍增思想啦(这里……我太难了先不写了……)
0x07 贪心
还记得这个片段吗?
刷题是一种出路
枚举是一种思想
打表是一种勇气
搜索是一种信仰
剪枝是一种精神
骗分是一种日常
爆零是一种宿命
WA是一种绝望
TLE是一种痛苦
RE是一种放弃
我想补充一句……
贪心是一种算法(这又是一句废话)
………………
贪心是一种在每次决策时采取当前意义下最优策略的算法。
这不用解释了吧……
0x08总结与练习
现在我宣布!
十六进制:nm我惹你了?
你™一来就骂脏话
啊不是,你听我
狡辩啊呸,解释这不是脏话,这是粗话