知识点:
前缀和
前缀和矩阵
二分
双指针
递推
并查集
哈希
kmp(算了)
bfs
dfs
dijkstra
floyd
最小生成树:prim/kruskal
筛质数
最大公约数
组合计数
快速幂
背包dp(01背包 完全背包 分组背包 多重背包)
线性dp
代码:
前缀和
for(int i = 1; i <= n; i ++)
{
s[i] += s[i - 1];
}
int ans = s[r] - s[l - 1];
前缀和矩阵
//预处理
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];
}
}
for(int i = 1; i <= n; i ++)
{
for(int j == 1; j <= m; j ++)
{
int x1, y1, x2, y2;
int sum = s[x2][y2] - s[x1 - 1][y2] - s2[x2][y1 - 1] + s[x1 - 1][x2 - 1];
}
}
二分
//左半区,或者找最大值
int l = 0, r= n - 1;//不一定这个数
while(l < r)
{
int mid = l + r >> 1;
//if(check(mid))
if(x <= a[mid]) r = mid;
else l = mid + 1;
}
//右半区,求最小值
int l = 0, r= n - 1;//不一定这个数
while(l < r)
{
int mid = l + r + 1>> 1;
//if(check(mid))
if(a[mid] >= x) l = mid;
else r = mid - 1;
}
双指针
刷 日志统计 一些基础课的题
for(int i = 0, j = 0; i <= n; i ++)
{
while(j < i)//看两个区间是不是单调性以及挖掘一些性质,刷一些题体会一下。
{
j ++;
}
//代码处理
}
递推
斐波那契数列吧,找递推公式
并查集
//p[x] 表示位 x的祖宗节点,即集合编号
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);//找不到继续找
return p[x];
}
哈希
kmp
bfs
dfs
dijkstra
floyd
最小生成树:prim/kruskal
筛质数(朴素 埃氏筛法)
### 最普通的
bool check(int x
{
for(int i = 2; i <= x; i ++)
{
if(x % i == 0) return false;
}
return true;
}
### 朴素
int get_prime(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i])//没被筛过
{
primes[cnt ++] = i;
}
for(int j = i; j <= n; j += i) st[j] = true;//2到p-1全部筛选完
}
return cnt;
}
### 埃氏筛法
int get_primes(int n)
int get_prime(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i])//没筛过的就是质数
{
primes[cnt ++] = i;
//把质数的倍数给筛掉
for(int j = i; j <= n; j += i) st[j] = true;
}
}
return cnt;
}
### 欧拉筛(还是有点懵)
int get_prime(int n)
{
for(int i = 2; i <= n; i ++)
{
if(st[i] == 0)//没被筛过
{
primes[cnt ++] = i;
}
for(int j = 0; primes[j] <= n / i; j++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0)
break;
}
}
return cnt;
}
最大公约数
int gcd(int a, int b)
{
return b ? gcd(b , a % b) : a;
}
### 最小公倍数
就是n / gcd
### 多个数的最小公倍数
int d = 0;
//循环
for(int i = 1; i <= n; i ++)
{
d = gcd(d, a[i]);
}
//三个
gcd(gcd(a, b), c);
组合计数
快速幂
int qmi(int a, int k, int p)
{
LL res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL) a * a % p;
}
return res;
}
背包dp(01背包 完全背包 分组背包 多重背包)
01背包
完全背包
分组背包
多重背包
线性dp