二分
整数二分
有单调性一定可以二分,二分不一定有单调性
数的范围
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
while(m --)
{
int x;
scanf("%d", &x);
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(q[mid] >= x) r = mid;//找绿色边界,验证是不是满足绿色的要求,也就是q[mid]是否 >= x,满足的话,更新右边界
else l = mid + 1;
}
if (q[l] != x) cout << "-1 -1" << endl;
else
{
cout << l << ' ';
int l = 0 , r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
数的三次方
#include <iostream>
using namespace std;
int main()
{
double x;
cin >> x;
double l = -10000, r = 10000;
while(r - l > 1e-8)
{
double mid = (l + r) / 2;
if(mid * mid * mid >= x) r = mid;
else l = mid;
}
printf("%lf\n", l);
return 0;
}
前缀和与差分
双指针
核心思想
for(i = 0, j = 0; i < n; i ++)
{
while(j < i && check(i, j)) j ++;
}
#include <iostream>
using namespace std;
const int N = 1e5 + 10;//数的范围,一共有n个整数,整数的范围是N
int n;
int q[N], s[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
// 存数组
int res = 0;
for(int i = 0, j = 0; i < n; i ++)
{
s[q[i]] ++;//
while(j < i && s[q[i]] > 1)
s[q[j ++]] -- ;
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
int i = 0, j = 0;
while (i < n && j < m)
{
if (a[i] == b[j]) i ++ ;
j ++ ;
}
if (i == n) puts("Yes");
else puts("No");
return 0;
}
位运算
lowbit(x)返回x的最后一位1
离散化
区间合并
单调栈
单调队列
kmp
Trie
#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
char op[2];
scanf("%s%s", op, str);
if (*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/45282/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
堆
哈希表
模拟散列表
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
int n, m;//字符串长度,询问次数
char str[N];//字符串
ULL h[N], p[N];
ULL get(int l, int r)//求l和r之间的哈希值,公式计算出结果
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
while (m -- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/45313/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
DFS深搜
#include <iostream>
using namespace std;
const int N = 10;//给n是什么范围就把这个N先定义了
int n;//存输入的值
int path[N];//保存的是路径
bool st[N];
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);//path[i]??
puts("");
return;
}
for (int i = 1; i <= n; i ++ )
if(!st[i])
{
path[u] = i;
st[i] = true;
dfs(u + 1);
path[u] = 0;//可去掉
st[i] = false;
}
}
int main()
{
scanf("%d", &n);
dfs(0);
return 0;
}
回溯?为什么要回溯,回溯完,下一次循环难道不会得出和上一次一样的结果吗???
- 不恢复现场的话,在最深的一层也就是即将要输出的时候,1 2 3 全部被用过了,递归到倒数第二层的时候因为3已经被用过了,所以不能出现1 3 _这种情况,所以算法也就失败了。所以最后一层的时候要恢复现场,同理可以推得,如果倒数第二层的时候不恢复现场,那么第一层的时候需要的2 _ _也被用过了,所以算法失败。所以每层都要恢复现场
n皇后
BFS宽搜
走迷宫
八数码
1、状态表示复杂
2、如何记录每个状态的距离
树与图的深度优先遍历
树和图的存储
树是特殊的图,所以只讲图
邻接表(拉链法)
const int N = 100010, M = N * 2;
int h[N], e[M], ne[M], idx;//头,边
void add(int a, int b)//插入a指向b的bian
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
st[u] = true;//标记是否已经搜过了
//遍历u的所有出边
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];//当前链表里的节点对应的图里边的编号是多少
if(!st[j]) dfs(j);//j如果没搜过,就继续搜
}
}
int main()
{
memset(h, -1 ,sizeof h);
}
邻接矩阵(稠密图)
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 2;
int n;
int h[N], e[M], ne[M], idx;//idx当前已经用到了的b
bool st[N];
int ans = N;//最小的最大值
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
//返回以u为根的子树中点的数量
int dfs(int u)
{
st[u] = true;//初始化的时候全是未被
int sum = 1, res = 0;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j])//如果没被搜索过
{
int s = dfs(j);
res = max(res, s);
sum += s;
}
}
res = max(res, n - sum);
ans = min(ans, res);
return sum;
}
int main()
{
cin >> n ;
memset(h, -1, sizeof h);//全部初始化为-1
for(int i = 0; i < n - 1; i ++)
{
int a, b;
cin >> a >> b;
add(a,b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}
树与图的广度优先遍历
AcWing 847. 图中点的层次
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int h[N], e[N], ne[N], idx;//头,边,下一节点,索引
int d[N], q[N];//距离,数值
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int bfs()
{
int hh = 0, tt = 0;
q[0] = 1;
memset(d, -1, sizeof d);
d[1] = 0;
while(hh <= tt)
{
int t = q[hh ++];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
d[j] = d[t] + 1;
q[++ tt] = j;
}
}
}
return d[n];
}
int main()
{
cin >> n ;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
拓扑排序
有向图才有拓扑序列(起点在终点前面
)
有向无环图:拓扑图
AcWing 848. 有向图的拓扑序列
Dijkstra
AcWing 849. Dijkstra求最短路 I
AcWing 850. Dijkstra求最短路 II
bellman-ford
存边方式非常随便
AcWing 853. 有边数限制的最短路
spfa
AcWing 851. spfa求最短路
AcWing 852. spfa判断负环
dist[]最短距离
cnt[]边数
Floyd
三重循环,把邻接矩阵转成最短路矩阵
AcWing 854. Floyd求最短路
Prim
AcWing 858. Prim算法求最小生成树
Kruskal
AcWing 859. Kruskal算法求最小生成树
染色法判定二分图
AcWing 860. 染色法判定二分图
匈牙利算法
AcWing 861. 二分图的最大匹配
质数
判定:试除法
AcWing 866. 试除法判定质数
快速幂
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int qmi(int a, int k, int p)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main()
{
int n;
scanf("%d", &n);
while(n --)
{
int a, k, p;
scanf("%d%d%d", &a, &k, &p);
printf("%d\n", qmi(a, k, p));
}
return 0;
}
区间问题
Huffman树
排序不等式
绝对值不等式
推公式
标签:idx,int,res,scanf,笔记,++,算法,基础课,AcWing From: https://www.cnblogs.com/wswtc/p/18171682