常用的东西
const int INF = 1e9;
算法基础课
整数二分
加不加1 完全取决于 l = mid 还是r = mid
l等于mid时必须+1向上取整 不然会陷入l=l的死循环
可以这样记:
找右半边的左端点时,mid = l + r >> 1,可能更新l = mid + 1;
找左半边的右端点时,mid = l + r + 1 >> 1, 可能更新r = mid - 1;
(记住一加一减)
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid] <= x) l = mid;
else r = mid - 1;
}
双指针 判断子序列 写错了好多次
位运算相关知识还要看看
int lowbit(int x)
{
return x & -x;
}
补充内容
字符串
字串与子序列的区别:
- 字串:是原字符串的一个连续部分。例如,在字符串”abcde”中,”abc”、”de”和”abcde”都是它的子串,但”ace”不是,因为”ace”中的字符在原字符串中不是连续的。
- 子序列:是原字符串中字符的不连续选择,但保持其在原字符串中的相对顺序。例如,在字符串”abcde”中,”ace”、”abd”和”abcde”都是它的子序列,但”cba”不是,因为”cba”中的字符顺序与它们在原字符串中的顺序不同。
以下内容要求不看也要能自己想到
-
求上取整
x / y上取整 等价于 (x + y - 1) / y 的下取整
-
计算组合数
LL C(int a, int b)
{
LL res = 1;
for (int i = a, j = 1; j <= b; i --, j ++)
res = res * i / j;
return res;
}
推荐看b站五点七边的二分视频,这玩意根本不用记
感谢推荐