目录
- ——2020年11月1日（周日）——————————————————
- 以下是并查集 的三道题
- ——2020年11月2日（周一）——————————————————
- ——2020年11月3日（周二）——————————————————
- 最短路思维导图
- 单源最短路：
- ——2020年11月4日（周三）——————————————————
- ——2020年11月5日（周四）——————————————————
- ——2020年11月6日（周五）——————————————————
- ——2020年11月7日（周六）——————————————————
- 多源最短路：
- 最小生成树
- ~~ ——To be continue…… ~~（完）————————————————
——2020年11月1日（周日）——————————————————
一、KMP
第四次了，发现还是记不住……因为之前没好好做笔记……
答案&注释
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
//首先是处理好ne数组，作用是当匹配不成功时，尝试从上一个出现当前字符的地方开始找，不至于从头再来。
for (int i = 2, j = 0; i <= n; i ++ )
{
//这里就是一点一点地往回退，从头开始太傻了。
while (j && p[i] != p[j + 1]) j = ne[j];
//找到可以往后一步的地方就j加1
if (p[i] == p[j + 1]) j ++ ;
//然后将对应i位置的ne设为j
ne[i] = j;
}
//开始寻找,其实两者代码是差不多的，因为找的时候也是一步一步往回退着找的。
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == n)
{
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}
二、Trie
转
理解之后觉得挺简单的，就这样吧。
连注释都不注的答案
#include<bits/stdc++.h>
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
", query(str));
}
return 0;
}
三、最大异或对
传送
一周前刚刷完……
（然而过了一周后再看，发现又忘记怎么做了……我的记忆果然是假的。
不过这次刷完Trie之后再看，发现其实做法和Trie真的很像，就是Trie的一种运用。
(注：-1的二进制码全是 1，所以 ~-1 == 0 ！
注释版 & 思路
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 3000000;
int n;
int a[N], son[M][2], idx;
void insert(int x)
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int &s = son[p][x >> i & 1];
if (!s) s = ++ idx;
p = s;
}
}//这个函数就是说，将这个数分解为一个二进制数，然后按照这个二进制不断地往下开辟一条道路
//每到一个新节点就给它取一个新的名字，这样往下找儿子的时候就不会产生混乱……
int search(int x)
{
int p = 0, res = 0;
for (int i = 30; i >= 0; i -- )
{
int s = x >> i & 1;
if (son[p][!s])
{
res += 1 << i;
p = son[p][!s];
}
else p = son[p][s];
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
insert(a[i]);
}
int res = 0;
for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));
printf("%d
", res);
return 0;
}
以下是并查集 的三道题
附上过去以下三道题的笔记
因为已经写过我就不想多赘述了，直接复制粘贴过来凑合吧。
四、合并集合（并查集）
AcWing 836. 合并集合
**答案**
#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int find(int x)
{
return p[x] == x ? p[x] : p[x] = find(p[x]);
//这句活浓缩了很多东西哦
//首先会把祖先返回；
//其次还会将每一个点的父节点都变为祖先。
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if (*op == 'M') p[find(a)] = find(b);
else
{
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
五、连通块中点的数量（并查集）
AcWing 837. 连通块中点的数量
思路
只是多了一个算和的情况，
每次只需要将一个 祖宗所在并查集的点数加上 另一个 祖宗 所在并查集的点数就好了；
答案
#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int sum[N];
int a, b;
string op;
int find(int x){
return p[x] == x ? p[x] : p[x] = find(p[x]);
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i, sum[i] = 1;
while (m -- )
{
cin >> op;
if(op == "C"){
scanf("%d%d", &a, &b);
if(a != b){
int pa = find(a), pb = find(b);
if(pa != pb)
sum[pb] += sum[pa], p[pa] = pb;
}
}
else{
if(op == "Q1"){
scanf("%d%d", &a, &b);
if(find(a) == find(b)) printf("Yes
");
else printf("No
");
}
else scanf("%d", &a), printf("%d
", sum[find(a)]);
}
}
return 0;
}
六、食物链（并查集）
AcWing 240. 食物链
思路
这个有点麻烦，题目描述得太烂了。
……
题意大概就是，并查集里面的元素每三层分一组，每一组的同一位置 的元素为一类，然后要你判断句子对错；
我们可以用一个d数组来记录这个点到祖宗节点的距离，然后%3 来判断它在某一组的哪一层，以此判断它是哪一类动物；
于是我们只需要额外地记录当前点到祖宗节点的距离就可以了；
如果描述的时候两个点不在同一个并查集之中，那么就合并，
距离的处理就是用两个点合并前到各自祖宗的距离相减，得到的就是一个点的祖宗到合并后的新祖宗的距离；
答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int sum;
int n, m, P;
int p[N];
int d[N];
//这里每执行一次都会直接将祖宗节点作为所有在内节点的父节点，
//其距离不会重复计算第二次，因为下一次就遍历不到之前的父节点了.
int find(int x){
if(x != p[x]){
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main(){
// freopen("ttt.in", "r", stdin);
// freopen("ttt.out", "w", stdout);
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (k -- ){
int z, a, b;
scanf("%d%d%d", &z, &a, &b);
int pa = find(a), pb = find(b);
if(a > n || b > n) sum ++;//假话
else{//其他情况
if (z == 1){
if(pa == pb && (d[a] - d[b]) % 3 ) sum ++;//假话,自己不吃自己
else if(pa != pb){
p[pa] = pb;
d[pa] = d[b] - d[a];
}
}
else
{
if(pa == pb && (d[a] - d[b] - 1) % 3) sum ++;//假话，说反了
else if(pa != pb){
p[pa] = pb;
d[pa] = d[b] + 1 - d[a];
}
}
}
}
cout << sum;
return 0;
}
——2020年11月2日（周一）——————————————————
一、堆排序
传送
堆结构就是可以维护一个最大值或者最小值在堆顶的结构，
通常在仅需要得到最大或最小值的时候用到。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], cnt;
int down(int u){
//找到较小的节点的位置t
int t = u;
if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
//找到了的话就把t下放
if(u != t){
swap(h[u], h[t]);
down(t);
}
//这样操作完之后，就会把最小的数维护在顶上；
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
//初始化
for(int i = n / 2; i; i --) down(i);
//从n / 2开始是因为最后一半是叶节点
//cnt 是当前最后一个元素的位置
cnt = n;
while(m --){
printf("%d ", h[1]);
h[1] = h[cnt --];
down(1);
}
puts("");
return 0;
}
——2020年11月3日（周二）——————————————————
最短路思维导图
单源最短路：
一、Dijkstra求最短路 I （朴素）
转到题目
大概思路
就是说，从目标点开始，利用被处理过的当前距离最小的点，不断地对为处理过的点进行处理，直到所有点都处理完毕。
也就是说，这是针对点的操作
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, g[N][N], djs[N];
bool s[N];
int djst(){
memset(djs, 0x3f, sizeof djs);
djs[1] = 0;
//下面这个循环，循环的是次数，有n个点，所以要进行n次处理
for(int i = 1; i <= n; i ++){
int t = -1;
//这里循环是为了找到未被处理的点中，距离最小的点
for(int j = 1; j <= n; j ++)
if(!s[j] && (t == -1 || djs[t] > djs[j]))
t = j;
//对将要进行操作的点进行标记
s[t] = 1;
//利用它来不断更新其他点的距离（即使是已经操作过的点也没有关系，因为肯定不会更新那些已经操作过的点）
for(int j = 1; j <= n; j ++)
djs[j] = min(djs[j], djs[t] + g[t][j]);
}
//如果我们要求的点没有办法到达源点，那就返回-1
if(djs[n] == 0x3f3f3f3f) return -1;
//否则如实输出就可以了
return djs[n];
}
int main(){
cin >> n >> m;
memset(g, 0x3f, sizeof g);//初始化
while(m-- ){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
cout << djst();
return 0;
}
二、Dijkstra求最短路 II（堆优化）
#include<bits/stdc++.h>
using namespace std;
const int N = 150010;
int n, m;
int dist[N];
bool st[N];
int ne[N], h[N], e[N], w[N], idx = 0;
typedef pair <int , int > P;
//邻接矩阵
void add(int a, int b, int c){
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
//堆优化版……
int djs(){
memset(dist , 0x3f, sizeof dist);
dist[1] = 0;
//下面这句话就按这种格式来写，具体为什么我不知道……
priority_queue < P, vector<P>, greater<P> > he;
//优先队列的插入方式
//记得我们这里用的是pair类型的，其中第一个代表距离，因为优先队列会自动按照第一个元素first进行排序
//第二个很明显就是点的编号了
he.push({0, 1});
while(he.size()){
//取出头结点
P t = he.top();
//头结点出队！
he.pop();
//ver是节点编号，dis是距离
int ver = t.second, dis = t.first;
//确定是没有操作过的点
//因为一个点有可能会进队很多很多次，因为每一次被更新都会进队，不过我们只要取距离最短的那次。
if(st[ver]) continue;
//对将要处理的点进行标记
st[ver] = 1;
//将所有与当前节点有关联的都遍历一遍，依次更新那些点的距离
for(int i = h[ver]; i != -1; i = ne[i]){
//j是遍历到得点的编号
int j = e[i];
//如果有必要我们才进行更新
if(dist[j] > dis + w[i]){
dist[j] = dis + w[i];
//之所以一更新完就直接放进优先队列，
//一是因为它会自动排序，
//二是因为当前点已经是离远点最最近的还未被处理完的点，那么下一个离源点最近的还未被处理过的点一定会与当前正在处理的点有关
//当然，如果与源点不连通的话也就无法遍历到，没办法的事……
//更新后的距离，以及节点编号
he.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i ++){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << djs() << endl;
return 0;
}
三、bellman-ford
bellman-ford 可以求出当经过的边不超过k条时的单源最短路。
并且可以处理负权边，因为没有那种按照最小值来的循环，每一次遍历都是固定的遍历所有的边……
#include<bits/stdc++.h>
using namespace std;
const int N = 510, M = 100010;
int n, m, k;
int dist[N], backup[N];
struct Edge{
int a, b, w;
}e[M];
int brm(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//所以这里一共k次， 代表当前最多经过k条边
for(int i = 0; i < k; i ++){
//备份上一轮的图；
memcpy(backup, dist, sizeof dist);
//j将所有的边都遍历一遍；
for(int j = 0; j < m ; j ++){
//取出a, b, w;
int a = e[j].a, b = e[j].b, w = e[j].w;
//尝试用当前边的 起点到源点的距离 来更新 终点到源点的距离。
//这样可以保证不会有遗漏，因为所有的边都会遍历到
//为了不 串联(这一轮走了两条边， 但理论上一轮只应该走一条边)，就要用上一轮的图；
//新的数据会保留在新的图里,并且舍弃掉旧的副本
dist[b] = min(dist[b], backup[a] + w);
}
}
// 假设 1没有边可以经过5、8,dist[5]、dist[8]都是10^9(正无穷),
// 但是5到8的距离是-2，那么dist[8]会被更新为 10^9-2, 就不再是正无穷。
// 题目所限制的距离一般不会超过0x3f3f3f3f的一半。
// 这就是为什么bell-ford可以处理负权！
//这个条件满足就说明目标点没有办法到源点。
if(dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
int main(){
cin >> n >> m >> k;
for(int i = 0; i < m; i ++){
int a, b, w;
cin >> a >> b >> w;
e[i] = {a, b, w};
}
int t = brm();
if(t == -1) cout << "impossible" << endl;
else cout << t;
return 0;
}
四、SPFA(spfa)
思路
优化Bellman-Ford
对Bellman-Ford算法 中的dist[b] = min(dist[b], dist[a] + w )做优化。
因为dist[a]不一定会更新dist[b]。具体而言就是，当dist[a]变小了， 与其相连的dist[b]才会变小。
用宽搜做优化。
大致模板
*1 定义一个queue q， 用来储存dist变小了的点；
*2 while q 不空
*3 取出队头 t，pop(t);
*4 更新 t 的所有出边。
*5 如果更新成功 且 队列中没有b， 将 b 入队；
写法和Dijkstra算法很像,不过是把针对“点”的操作 改为 针对“边”的操作。
注：很多正权图可以用SPFA。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int dist[N];
int ne[N], h[N], e[N], w[N], idx = 0;
bool st[N];
//邻接矩阵
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int spfa(){
//先初始化为最大值
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
st[1] = 1;
//优化开始的地方。
//这里不像Dijkstra那样用优先队列，是因为对边的要求不高，只要能全部走完要进行更新的边就可以了。
//Dijkstra还要按照点的距离大小进行遍历，于是要用优先队列。
queue<int> q;
//从第一条边开始
q.push(1);
//当队列不空，说明还可以更新
while(q.size()){
//获取队头
int t = q.front();
q.pop();
st[t] = 0;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
//虽然更新了距离，但是已经入队的边不能再进队
if(!st[j]){
st[j] = 1;
q.push(j);
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
cin >> n >> m;
//记住，头结点这个函数一定要全部初始化成-1
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
if(t == -1) cout << "impossible";
else cout << t;
return 0;
}
——2020年11月4日（周三）——————————————————
文化科期中考……
——2020年11月5日（周四）——————————————————
文化科期中考……
——2020年11月6日（周五）——————————————————
文化科期中考……
——2020年11月7日（周六）——————————————————
多源最短路：
一、Floyd算法
d[k, i, j]代表中间只经过从1到k这几个点 的 从i到j 的最短距离。
与动态规划有关，k表示状态，但没什么用,就优化掉变成d[i, j]。
也可以看做是不断地枚举一个中间点k，然后枚举起点i和终点j，如果满足条件我们就更新；
放心地写吧，不会有什么遗漏之类的，毕竟 n3的枚举可不是开玩笑的。
for(k = 1; k <= n;k ++);
for(i = 1; i <= n; i ++)
for(j = 1; j <= n; j ++)
d[i, j] = min(d[i, j], d[i, k] + d[k, j] )
图中不能有负权回路！
#include<bits/stdc++.h>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, k;
int d[N][N];
void floyd(){
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main(){
cin >> n >> m >> k;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF;
while(m --){
int a, b, w;
cin >> a >> b >> w;
d[a][b] = min(d[a][b], w);
}
floyd();
while(k --){
int a, b;
cin >> a >> b;
if(d[a][b] > INF / 2) printf("impossible
");
else printf("%d
", d[a][b]);
}
return 0;
}
最短路似乎都复习了一遍……
最小生成树
首先复习一下什么是最小生成树：
就是说给你N个点，M条边，请你从中挑选N-1条边来连接这M个节点，使得所有边的权值最小。
很简单，对不对？
一、Prim
prim
首先是一个很类似Dijkstra的算法。
从点1开始建立连通块，
不断地用当前距离最小的点更新其它 连通块之外的 点的距离，
然后将这个点加入连通块。
Dijkstra算法：
s[]数组 表示当前已在连通块中的所有点
先把所有距离初始化成正无穷dist[i] = 1e9
然后是不断枚举当前离源点最近的点，将其更新其它所有的点；
最后就得到答案啦
#include<bits/stdc++.h>
using namespace std;
const int N = 510, INF = 1e9;
int n, m;
int dist[N];
int g[N][N];
bool st[N];
int prim(){
memset(dist, 0x3f, sizeof dist);
int res = 0;
for(int i = 0; i < n; i ++){
int t = -1;
for(int j = 1; j <= n; j ++)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if(i && dist[t] >= INF / 2) return INF;
if(i) res += dist[t];
for(int j = 1; j <= n; j ++)
dist[j] = min(dist[j], g[t][j]);
st[t] = 1;
}
return res ;
}
int main(){
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while(m --){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if(t > INF / 2) cout << "impossible";
else cout << t ;
return 0;
}
二、堆优化版Prim
这个很容易想到吧？毕竟是类似dijkstra的算法，相应的优化当然是会凑效的啦！
不过我还没有写，没想到吧！哈哈哈……
原因是不会写&…………
来啦……
这个鬼程序耗了我三天时间……写完之后发现时间上还不如朴素版……
#include<bits/stdc++.h>
using namespace std;
//用邻接矩阵来储存数据。
const int N = 2e5 + 10,MAXX = 6e8 + 10;
int n, m;
int dist[N];
bool st[N];
int ne[N], h[N], e[N], w[N], idx = 0;
int res;
typedef pair <int , int > P;
void add(int a, int b, int c){
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
priority_queue < P, vector<P>, greater<P> > he;
int prim(){
//数点数
int cnt = 0;
memset(dist , 0x3f3f3f3f, sizeof dist);
dist[1] = 0;
he.push({0, 1});
while(he.size()){
//得到一个新的没有进的点
P t = he.top();
he.pop();
//当前的点的标号
int ver = t.second;
if(st[ver]) continue;
st[ver] = true;
//这是第一个无法连通的情况
if(dist[ver] > MAXX / 2){
printf("impossible");
return 1;
}
cnt ++;
res += dist[ver];
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i], k = w[i];
if(dist[j] > k && !st[j]){
dist[j] = k;
he.push({k, j});
}
}
}
//这是的二个法连通的情况，即把能走的边都走完了，发现点数不足n个，说明无法做到一个完整的连通块。
if(cnt < n) printf("impossible");
else printf("%d", res);
return 0;
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m;
while(m --){
int a, b, c;
cin >> a >> b >> c;
//这个图是双向的，一定要两次加入！
add(a, b, c);
add(b, a, c);
}
int l = prim();
return 0;
}
为什么这东西可以搞我三天时间？
其实堆优化函数我早就写好了，
却在建图的时候没建好，单向图和双向图这个细节忽略了……
没有很快地反应过来时建图出了问题，堆优化那部分改了又改还是没过……
果然每一个细节都很重要啊！