蓝桥杯备赛

关闭同步流：

   ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

注意数据范围：数据范围较大时干脆所有变量类型都定义成longlong等。

stl：

sort函数

时间复杂度为nlog(n);
sort(数组指针，从指针开始多少个数，greater<int>()/cmp):
三个参数，第三个参数不加默认为从小到大排，加了greater<int>为从大到小排，也可以自定义函数cmp

bool cmp(int x,int y){
    return x>y
}

如果返回的是false，则会把传入的第一个参数放到第二个参数后面，如果两个数相等，必须返回false，不然会报错。

unique：

    该函数的作用是“去除”容器或者数组中相邻元素的重复出现的元素，注意
         (1) 这里的去除并非真正意义的erase，而是将重复的元素放到容器的末尾，返回值是去重之后的尾地址。
         (2) unique针对的是相邻元素，所以对于顺序顺序错乱的数组成员，或者容器成员，需要先进行排序，可以调用std::sort()函数

返回数组中最后一个不重复的数的位置索引

#include <iostream>
#include <algorithm>

int main(void)
{
    int a[8] = {2, 2, 2, 4, 4, 6, 7, 8};
    int c;

    //std::sort(a, a + 8);  //对于无序的数组需要先排序

    c = (std::unique(a, a + 8) - a );

    std::cout<< "c = " << c << std::endl;

    //打印去重后的数组成员
    for (int i = 0; i < c; i++)
        std::cout<< "a = [" << i << "] = " << a[i] << std::endl;

    return 0;
}

动态数组vector:

需要引入头文件<vector>

声明：

vector<type> vec;

vector<type> vec(n,1);   //第一个参数为数组长度(后续仍能继续添加)，第二个参数为初始化的值，不加则默认0。

方法：

push_back(); //末尾添加数据

pop_back();  //末尾删除数据，要是想删中间的需要手动移动整个数组

.size();    //获取vector的长度

.clear();  //清空vector，但是不会释放内存，要释放内存可以用 vector <int>().swap(v)

二维数组：

vector<vector<int> > vec;   //注意有个空格，不能省略

按上面的定义，刚开始vec里面都是空的，我们需要先往里面push空的一维vector数组

vec.push_back(vector<int>());

初始化方法：vector<vector<int> > vec(n,vector(m,0));

也可以建立vector类型的数组：

vector<int> x[100];

集合set：

由不重复的元素组成。

声明：

set<type> s;

方法：

.insert()    //往集合里插入数据，如果数据已经存在，就不会插入

.erase();  //删除元素，找不到元素则不进行任何操作

.count();   //查找元素是否存在，存在返回1，不存在返回0

.clear();  //会清空集合并释放内存

.size();   //获取元素个数

遍历：

要遍历集合需要用到迭代器

for(set<string>::iterator it = s.begin(); it != s.end(); it++){
    cout << *it << endl;
}
//自动会从小到大遍历


集合经常会搭配结构体使用，此时遍历会无法判断结构体的大小，需要重载<符号
struct node {
    int x,y;
    bool operator<(const Node &rhs) const{
        if (x == rhs.x){
            return y < rhs.y;
        }
        else return x < rhs.x;
        
    }

}

pair：

头文件utility，由一对元素组成，可以看作有两个属性first和second的结构体，重载了<运算符，先比较first大小，如果等于再比较second

声明：

pair<type1,type2> p;

方法：

make_pair(v1,v2);   //返回一个由v1，v2初始化的pair，类型可以从v1，v2反推出来

映射集合map:

存储key->value键值对，一个key只能对应一个value，一个value可以对应多个key

声明：

map<type1,type2> m;

方法：

.insert();   //插入的类型为pair类型，如果key存在不会执行

map['key'];    //获取key对应的value，如果没有对key做过映射，会自动为其创建映射，初始值为其类型的默认值

map['key']=value2；   //更改对应的值

.count('key');   //检测key值是否存在，存在返回1，否则返回0

.size();   //返回映射的个数

.claer();  //清空map

遍历：

与set类似，也需要使用迭代器

此外：

map也可以套set，套map

map<int , set<string> > s;   //注意空格！
 

cmath头文件：

fabs();    //取绝对值

round();   //四舍五入取整

sqart();   //开方函数

最大公约数计算：

代码练习：

二维单调队列：

在一维单调队列的基础上，先进行行的单调队列，再进行列的单调队列

我简化了列题，改为求长度为n的正方形区域中的最大值

代码：

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m, k, w;
int g[1005][1005];
int head, tail;     //窗口的头尾指针
int d[1005];  //单调队列
int maxx[1005][1005];
int ans[1005][1005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    //对每一行做单调队列
    memset(d, 0, sizeof(d));
    for (int i = 1; i <= n; i++) {
        head = tail = 0;
        for (int j = 1; j <= m; j++) {
            if (j != 1 && d[head] < j - k + 1) head++;
            while (tail != head && g[i][j] > g[i][d[tail - 1]]) tail--;
            d[tail++] = j;
            maxx[i][j] = g[i][d[head]];
            cout << g[i][d[head]]  << " ";
        }
        cout << endl;
    }
    //对每一列做单调队列
    memset(d, 0, sizeof(d));
    for (int i = k; i <= m; i++) {
        head = tail = 0;
        for (int j = 1; j <= n; j++) {
            if (j != 1 && d[head] < n - k + 1) head++;
            while (head != tail && maxx[j][i] > maxx[d[tail - 1]][i]) tail--;
            d[tail++] = j;
            ans[j][i] = maxx[d[head]][i];
            cout << maxx[d[head]][i] << " ";
        }
        cout << endl;
    }
    int ans2 = 0;
    for (int i = k; i <= n; i++) {
        for (int j = k; j <= m; j++) {
            ans2 = max(ans2, ans[i][j]);
        }
    }
    cout << ans2;
}

前缀异或和：

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long a[100005];
long long s[100005];
long long ans;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	s[0] = 0;
	for (int i = 1; i <= n; i++) {
		s[i] = s[i - 1] ^ a[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			ans += s[i - 1] ^ s[j];
		}
	}
	cout << ans;
}

蓝桥杯真题：

拆位+有效位思想

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long a[100005];
long long ans;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < 20; i++) {
		//s为前缀和，n1为奇数，n0为偶数
		long long s = 0; 
		long long n1 = 0;
		long long n0 = 1;
		for (int j = 1; j <= n; j++) {
			long long t = a[j] >> i & 1;
			s += t;
			if (s % 2) {
				//此处n0必须设为longlong，longlong和int相乘结果是int导致越界
				ans += (1 << i) * n0;
				n1++;
			}
			else {
				ans += (1 << i) * n1;
				n0++;
			}
		}
	}
	cout << ans;
}

并查集：

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int fa[1005];
int n;
//初始化
void intt() {
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
}
//找父亲节点
int find(int i) {
	if (i == fa[i]) return i;
	else {
//路径压缩
		fa[i] = find(fa[i]);
		return fa[i];
	}
}
//合并
void unionn(int i, int j) {
	int fai = find(i);
	int faj = find(j);
	fa[fai] = faj;
}
int main() {
	cin >> n;
}

DFS:

深搜剪枝：

找路：

剪枝思路，last数组用于记录一个方块附近可到达的方块数量，如果该方块附近可到达的方块的附近只有一个可到达的方块（且这个方块不为目标地点），那么我们就必须走这一个方块，因为需要一进一出，如果此时不走，将来走进去了就出不来了。同时这样的方块只能有一块，大于一块就可以直接return。

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
using namespace std;
bool vis[10][10];
int last[10][10];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int n,m,ans;
bool in(int x, int y) {
	return x <= n && y <= n && x >= 1 && y >= 1;
}
void dfs(int x, int y, int step) {
	if (x == n && y == 1 && step != m) {
		return;
	}
	if (!in(x, y) || vis[x][y]) {
		return;
	}
	if (x == n && y == 1 && step == m) {
		ans++;
		return;
	}
	int dir = -1;
	int cnt = 0;
	vis[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int ex = x + dx[i];
		int ey = y + dy[i];
		if (in(ex, ey) && !vis[ex][ey]) {
			last[ex][ey]--;
			if (last[ex][ey] < 2) {
				if (!(ex == n && ey == 1)) {
					dir = i;
					cnt++;
				}
			}
		}
	}
	if (cnt >= 2) {
		for (int i = 0; i < 4; i++) {
			int ex = x + dx[i];
			int ey = y + dy[i];
			if (in(ex, ey) && !vis[ex][ey]) {
				last[ex][ey]++;
			}
		}
		vis[x][y] = false;
		return;
	}
	if (dir != -1) {
		dfs(x + dx[dir], y + dy[dir], step + 1);
	}
	else {
		for (int i = 0; i < 4; i++) {
			int ex = x + dx[i];
			int ey = y + dy[i];
			if (in(ex, ey) && !vis[ex][ey]) {
				dfs(x + dx[i], y + dy[i], step + 1);
			}
		}
	}
	vis[x][y] = false;
	for (int i = 0; i < 4; i++) {
		int ex = x + dx[i];
		int ey = y + dy[i];
		if (in(ex, ey) && !vis[ex][ey]) {
			last[ex][ey]++;
		}
	}
}
int main() {
	cin >> n;
	m = n * n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int m = 0; m < 4; m++) {
				int ex = i + dx[m];
				int ey = j + dy[m];
				if (in(ex, ey)) {
					last[i][j]++;
				}
			}
		}
	}
	dfs(1, 1, 1);
	cout << ans;
}
蓝桥杯真题： 卖瓜
//方案1   无敌剪枝（全过）
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int ans = 100;
int n;
double m;
double s[35];
double pre[35];
void dfs(int num, double sum, int cnt) {
	//找到方案
	if (sum == m) {
		if (cnt < ans) { ans = cnt; }
		return;
	}
	//切的次数已经大于最优解
	if (cnt >= ans) { return; }
	//总重超过目标重量
	if (sum > m) return;
	//n个瓜都遍历完了
	if (num > n) return;
	//总重不可能到目标重量
	if (sum + pre[num] < m) return;
	dfs(num + 1, sum + s[num] / 2, cnt + 1);
	dfs(num + 1, sum + s[num], cnt);
	dfs(num + 1, sum, cnt);
	return;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	//贪心算法，让大的瓜放在前面
	sort(s + 1, s + n + 1,greater<double>());
	//记录后缀和，用于剪枝
	for (int i = n; i >= 1; i--) {
		pre[i] = s[i] + pre[i + 1];
	}
	dfs(1,0, 0);
	if (ans == 100) { cout << -1; }
	else cout << ans;
	return 0;
}
//方案2 折半枚举+hash表查找
//这里不会写hash表直接拿unordered_map只能拿78分，因此主要还是学一下折半枚举的思想
#include<bits/stdc++.h>
using namespace std;
unordered_map <double, int> PII;
int ans = 100;
int n;
double m;
double s[35];
double pre[35];

void dfs1(int num, double sum, int cnt) {
	if (sum > m) return;
	if (num == n / 2 + 1) {
		PII[sum] = cnt;
		return;
	}
	dfs1(num + 1, sum + s[num], cnt);
	dfs1(num + 1, sum, cnt);
	dfs1(num + 1, sum + s[num] / 2, cnt + 1);
	return;
}
void dfs2(int num, double sum, int cnt) {
	if (cnt > ans) return;
	if (sum > m) return;
	if (sum <= m && PII.count(m - sum)) {
		ans = min(ans, PII[m - sum] + cnt);
	}
	if (num > n) return;
	dfs2(num + 1, sum + s[num], cnt);
	dfs2(num + 1, sum, cnt);
	dfs2(num + 1, sum + s[num] / 2, cnt + 1);
	return;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	贪心算法，让大的瓜放在前面
	sort(s + 1, s + n + 1, greater<double>());
	dfs1(1, 0, 0);
	dfs2(n / 2 + 1, 0, 0);
	if (ans == 100) { cout << -1; }
	else cout << ans;
	return 0;
}

BFS:

1.平面三维魔方复原

思路就是用一个结构体记录魔方的状态，用一个队列记录魔方的状态和已进行的步数，将每次12种可能都入栈，采用BFS。在node中重载了==号。

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
using namespace std;
struct node {
	int a[5][5];
	bool operator < (const node& x) const {
		for (int i = 1; i <= 3; i++) {
			for (int j = 1; j <= 3; j++) {
				a[i][j] < x.a[i][j];
				return 1;
			}
		}
		return 0;
	}
	bool operator == (const node& x) const {
		for (int i = 1; i <= 3; i++) {
			for (int j = 1; j <= 3; j++) {
				if (a[i][j] != x.a[i][j])
					return 0;
			}
		}
		return 1;
	}
};
node first;
node des;
node line(node t,int i, int flag) {
	//左移
	if (flag == 1) {
		int x = t.a[i][1];
		t.a[i][1] = t.a[i][2];
		t.a[i][2] = t.a[i][3];
		t.a[i][3] = x;
	} //右移
	else if (flag == 0) {
		int x = t.a[i][3];
		t.a[i][3] = t.a[i][2];
		t.a[i][2] = t.a[i][1];
		t.a[i][1] = x;
	}
	return t;
}
node col(node t, int i, int flag) {
	//上移
	if (flag == 1) {
		int x = t.a[1][i];
		t.a[1][i] = t.a[2][i];
		t.a[2][i] = t.a[3][i];
		t.a[3][i] = x;
	} //下移
	else if (flag == 0) {
		int x = t.a[3][i];
		t.a[3][i] = t.a[2][i];
		t.a[2][i] = t.a[1][i];
		t.a[1][i] = x;
	}
	return t;
}
void bfs(node t) {
	queue<pair<node , int>> q;
	q.push({ t,0 });
	while (!q.empty()) {
		auto [tt , step] = q.front();
		q.pop();
		if (tt == des) {
			cout << step;
			exit(0);
		}
		for (int i = 1; i <= 3; i++) {
			q.push({ line(tt,i,1),step + 1 });
			q.push({ line(tt,i,0),step + 1 });
			q.push({ col(tt,i,1),step + 1 });
			q.push({ col(tt,i,0),step + 1 });
		}
	}

}
int main() {
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			des.a[i][j] = (i-1) * 3 + j;
		}
	}
	for (int i = 1; i <= 3; i++) {
		int n;
		cin >> n;
		for (int j = 3; j >= 1; j--) {
			first.a[i][j] = n % 10;
			n /= 10;
		}
	}
	bfs(first);
}

2.分糖果（数据结构）：

思路就是利用vector数组来建立邻接表，然后bfs搜索即可，直接用二维数组会过大导致编译失败

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
vector<int> a[100010];
int maxstep;
bool vis[100010];
void bfs(int c) {
	queue<pair<int, int>> q;
	q.push({ c , 0 });
	while (!q.empty()) {
		auto [num,step] = q.front();
		q.pop();
		if (step > maxstep) {
			maxstep = step;
		}
		for (int i = 0; i < a[num].size(); i++) {
			if (!vis[a[num][i]]) {
				q.push({ a[num][i], step + 1 });
				vis[a[num][i]] = 1;
			}
		}
	}
}
int main() {
	int n, p, c, m,x,y;
	cin >> n >> p >> c >> m;
	for (int i = 0; i < p; i++) {
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	vis[c] = true;
	bfs(c);
	cout << maxstep + m;
}

相似度（思路）：

思路：每个选手的字符与其本身的相似度最大，即为m(特征总数)，以这些字符为起点，全部放入堆栈，然后依次修改这些字符的每一位数字，每次修改得到的字符最大相似度会-1，如果得到的字符已经被访问过了就不管，没访问过就把最大相似度-1并入队列，这样越进行到后面最大相似度越小，直到最后获得最小的。

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
queue<int> q;   //存放每组数，用二进制的值来代表每组数据
int f[100000];  //存放每组数的最大相似度
int n, m;
int mincnt = 100000;
vector<int> mi(100000,-1);
void ext(int x, int cnt) {
	if (f[x] == -1) {
		f[x] = cnt;
		q.push(x);
		if (cnt < mincnt) {
			mincnt = cnt;
			for (int i = m-1; i >= 0; i--) {
				mi[i] = x % 2;
				x /= 2;
			}
		}
	}

}
int main() {
	cin >> n >> m;
	for (int i = 0; i < 1 << m; i++) {
		f[i] = -1;
	}
	for (int i = 0; i < n; i++) {
		int sum = 0;
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			sum = sum * 2 + s[j]-'0';
		}
		f[sum] = m;
		q.push(sum);
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < m; i++) {
			//更改每一位的数字
			ext(x ^ (1 << i), f[x] - 1);
		}
	}
	for (int i = 0; i < m; i++) {
		cout << mi[i];
	}
}

动态规划：

一维消消乐：

思路:从左往右进行选择，每个珠子有两种状态，与前面一个相消和不消，如果不消，分数就为前面一个两种状态的较大值，如果相消，则为前一个不消状态的分数加上这两个珠子相消的分数。

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int x[10005];
int stau[10005][2];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	stau[0][0] = stau[0][1] = 0;
	for (int i = 1; i < n; i++) {
		stau[i][0] = max(stau[i - 1][0], stau[i - 1][1]);
		stau[i][1] = stau[i - 1][0] + x[i] * x[i - 1];
	}
	cout << max(stau[n - 1][0], stau[n - 1][0]);
}

数组分组：

ans[i]代表对前i个数字分组的最大权值，对于i+1个数字的分组，则考虑ans[n]+n到i为一组的权值，n从1到i。

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int pre[1005][1005];
int a[1005];
int ans[1005];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	//预处理
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if (i == j) pre[i][j] = a[i];
			else {
				pre[i][j] = pre[i][j - 1] * a[j] % 1000;
			}
		}
	}
	ans[0] = 0;
	ans[1] = a[1];
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			ans[i] = max(ans[i], ans[j] + pre[j + 1][i]);
		}
	}
	cout << ans[n];
}

常见模型：

二维数组可以看作一维数组，比如3x3的二维数组，可以看成6种一维数组，第一、二、三行，1+2行，1+3行，2+3行，1+2+3行。

1.最大子段和

思路：考虑从1到i这i个数的最大子段和（子段和中必须包括第i个数），记为sum。在考虑1到i+1的最大子段和时只需要考虑sum加上i+1的值是否为正，为正则更新sum的值，为负则令sum=0。这样就舍掉了所有前缀和为负数的情况。用一个ans变量与sum比较来更新最大值即可。

上述的思想是建立在存在一个正数的情况，所以如果全为负数需要单独考虑，此时只需要取最大的

负数即可。

2.最长上升子序列

3.最长公共子序列

4.字符串转变

数组dp[i][j]代表字符串s1前i位与s2前j位对齐需要操作数。

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int a[1005];
int b[1005];
int dp[1005][1005];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++){
		cin >> b[i];
	}
	for (int i = 1; i <= n; i++) {
		dp[i][0] = i;
	}
	for (int i = 1; i <= m; i++) {
		dp[0][i] = i;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i] == b[j]) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
		}
	}
	cout << dp[n][m];
}
5.最长公共上升子序列
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int a[1005];
int b[1005];
int dp[1005][1005];    //dp[i][j]代表a组i个和b组j个的最大公共子序列，这个序列的结尾是b组的第j个数
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	for (int i = 1; i <= n; i++) {
		int maxx = 0;
		for (int j = 1; j <= m; j++) {
			//这里dp[i - 1][j]表示以b[j]为结尾的最大公共子序列，因此多加一个a[i]不会影响
			dp[i][j] = dp[i - 1][j];
			//maxx记录a组i个和b组所有的最大公共子序列，因此a[i] > b[j]才更新
			if (a[i] > b[j] && maxx < dp[i-1][j]) {
				maxx = dp[i - 1][j];
			}
			else if(a[i] == b[j]) {
				dp[i][j] = maxx + 1;
			}
		}
	}
	int maxx = 0;
	for (int i = 1; i <= m; i++) {
		maxx = max(maxx, dp[n][i]);
	}
	cout << maxx;
}

背包问题：

01背包：

空间优化：

多重背包：

优化：将n个相同物品的n用二进制拆封，例如7个相同物品可以拆成1+2+4这样三个物品.

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int w[1005];
int c[1005];
int n[1005];
int nc[1005];
int nw[1005];
int dp[1005][1005];
int main() {
	int m, v;
	cin >> m >> v;
	for (int i = 1; i <= m; i++) {
		cin >> w[i] >> c[i] >> n[i];
	}
	int k;
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		for (k = 1; n[i] - (1 << k) + 1 > 0; k++) {
			nc[cnt] = (1 << (k - 1)) * c[i];
			nw[cnt] = (1 << (k - 1)) * w[i];
			cnt++;
		}
		k--;
		nc[cnt] = (n[i] - (1 << k) + 1) * c[i];
		nw[cnt] = (n[i] - (1 << k) + 1) * w[i];
	}
	for (int i = 1; i <= cnt; i++) {
		for (int j = 1; j <= v; j++) {
			if (j > nc[i])
				dp[i][j] = max(dp[i][j - nc[i]] + nw[i], dp[i - 1][j]);
			else dp[i][j] = dp[i - 1][j];
		}
	}
}
完全背包:

物品无限，例题存钱罐：

钱的重量为e-f，满足这个情况的最小金额

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
const int inf = 0x3f3f3f3f;
//dp[i]代表重量为i时的最小金额
int dp[1000];
int main() {
	//memset将整数数组全部赋值为非0整数值会出错，推荐for循环设置，这里是看老师这么做的，原理不明
	memset(dp, inf, sizeof dp);
	dp[0] = 0;
	int a, b, n;
	cin >> a >> b;
	int v = b - a;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		for (int j = b; j <= v; j++) {
			dp[j] = min(dp[j], dp[j - b] + a);
		}
	}
	if (dp[v] == inf) {
		cout << "imposible";
	}
	else cout << dp[v];
}
双塔（好题） ：

思路写在注释里了。

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int h[10005];
int dp[1005][1005];//dp[i][j]表示考虑到第i号水晶，两座塔差距为j时较低的塔的最大高度
int main() {
	int n;
	int sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
	}
	memset(dp, -1, sizeof dp);
	dp[0][0] = 0;
	//每一种状态可以有四种产生方式，高塔的更高，低塔变高但还是小于高塔，低塔变高大于高塔，不选择这块水晶状态不变
	//因此可以用动态规划遍历四种情况选出最优解
	for (int i = 1; i <= n; i++) {
		sum += h[i];
		for (int j = 0; j <= sum; j++) {
			//不选择水晶
			if (dp[i - 1][j] > dp[i][j]) {
				dp[i][j] = dp[i - 1][j];
			}
			//高的更高
			if (j >= h[i] && dp[i - 1][j - h[i]] >= 0) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]]);
			}
			//低塔变高但还是小于高塔
			if (dp[i - 1][j + h[i]] >= 0) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j + h[i]] + h[i]);
			}
			//低塔变高大于高塔
			if (j <= h[i] && dp[i - 1][h[i] - j] >= 0) {
				dp[i][j] = max(dp[i][j], dp[i - 1][h[i] - j] + h[i] - j);
			}
		}
	}
	if (dp[n][0] > 0) {
		cout << dp[n][0];
	}
	else cout << "impossible";
}

图和树：

最短路径：

有权图：

Dijkstra:
 

注意这个算法需要在每一轮中找出到未标记的节点中路径最短的节点，而spfa算法不用

//借助临界表
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
struct edge {
	//v为边指向的节点，w为边权
	int v, w, next;     //next记录的是与该边共起点的一条边的序号，与head数组配合可以遍历从一个节点发出的所有边
	edge() {};
	edge(int vv, int ww ,int nextt) {
		v = vv;
		w = ww;
		next = nextt;
	}
}e[100000];
int head[100000];   //head[u]从u起点发出的边中最后一条，搭配next属性可以从这条边开始遍历从u发出的所有边
int num;   //边的序号
int n, m;
bool vis[100000];
int dis[100000];
void init() {
	memset(head, -1, sizeof(head));
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));   //设置很大的数
	num = 0;
}
void insert2(int u, int v, int w) {
	e[num] = edge(v, w, head[u]);
	head[u] = num++;
}
void insert(int u, int v, int  w) {
	insert2(u, v, w);     //无向图相当于每个节点之间两条边
	insert2(v, u, w);
}
void Dijkstra(int u) {
	dis[u] = 0;
	for (int i = 1; i <= n; i++) {
		int mind = 10000000, minj = -1;
		for (int j = 1; j <= n; j++) {
			
			//找到到某个点的距离最小且这个点还没被访问过的点
			if (!vis[j] && dis[j] < mind) {
				mind = dis[j];
				minj = j;
			}
		}
		if (minj == -1) {
			return;
		}
		vis[minj] = true;
		for (int j = head[minj]; j != -1; j = e[j].next) {
			int w = e[j].w;
			int v = e[j].v;
			if(!vis[v] && w + dis[minj] < dis[v]){
				dis[v] = w + dis[minj];
			}
		}
	}
}
int main() {
	init();
	cin >> n >> m;
	int u, v, w;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		insert(u, v, w);
	}
	Dijkstra(1);
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << endl;
	}
}
//借助临界矩阵
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int dis[10000];
int pre[10000];
int map[10000][10000];
bool vis[10000];
int n,m;
void Dis(int u) {
	dis[u] = 0;
	for (int i = 0; i < n; i++) {
		int mind = 1000000;
		int minj = -1;
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && dis[j] < mind) {
				mind = dis[j];
				minj = j;
			}
		}
		if (minj == -1) {
			return;
		}
		vis[minj] = true;
		for (int k = 1; k <= n; k++) {
			if (map[minj][k] != 0x3f3f3f3f) {
				if (dis[k] > dis[minj] + map[minj][k]) {
					dis[k] = dis[minj] + map[minj][k];
					pre[k] = minj;
				}
			}
		}
	}
}
int main() {
	cin >> n >> m;
	int u, v, w;
	memset(dis, 0x3f, sizeof(dis));
	memset(pre, -1, sizeof(pre));
	memset(vis, 0, sizeof(vis));
	memset(map, 0x3f, sizeof(map));
	for (int i = 1; i <= n; i++) {
		map[i][i] = 0;
	}
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		map[u][v] = map[v][u] = w;
	}
	Dis(1);
	cout << dis[n];
}
堆优化Dijkstra：

关于优先队列priority_queue函数的使用:

头文件#include<queue>
定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式。
greater<Type>是小根堆，less<Type>是大根堆

 //升序队列，小顶堆
2 priority_queue <int,vector<int>,greater<int> > q;
3 //降序队列，大顶堆
4 priority_queue <int,vector<int>,less<int> >q;
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> p;
priority_queue<p, vector<p>, greater<p>> heap;
int num = 0;
int n, m, u, v, w;
int head[100000];
int dis[10000];
bool vis[100000];
struct edge {
	int w, v, next;
	edge() {};
	edge(int vv, int ww, int nextt) {
		w = ww;
		v = vv;
		next = nextt;
	}
}e[100000];
void init() {
	memset(head, -1, sizeof(head));
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
}
void insert2(int u, int v, int w) {
	e[num] = edge(v, w, head[u]);
	head[u] = num++;
}
void insert(int u, int v, int w) {
	insert2(u, v, w);
	insert2(v, u, w);
}
void dist(int x) {
	dis[x] = 0;
	heap.push({ dis[x], x});
	while (!heap.empty()) {
		p temp = heap.top();
		int mind = temp.first;
		int minj = temp.second;
		heap.pop();
		if (vis[minj]) continue;
		vis[minj] = true;
		for (int j = head[minj]; j != -1; j = e[j].next) {
			int v = e[j].v;
			int w = e[j].w;
			if (!vis[v] && dis[v] > dis[minj] + w) {
				dis[v] = dis[minj] + w;
				heap.push({ dis[v],v });
			}
		}
	}
}
int main() {
	init();
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		insert(u, v, w);
	}
	dist(1);
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << endl;
	}
}
spfa:
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
struct edge {
	//v为边指向的节点，w为边权
	int v, w, next;     //next记录的是与该边共起点的一条边的序号，与head数组配合可以遍历从一个节点发出的所有边
	edge() {};
	edge(int vv, int ww ,int nextt) {
		v = vv;
		w = ww;
		next = nextt;
	}
}e[100000];
int head[100000];   //head[u]从u起点发出的边中的一条，搭配next属性可以从这条边开始遍历从u发出的所有边
int num;   //边的序号
int n, m;
bool vis[100000];
int dis[100000];
void init() {
	memset(head, -1, sizeof(head));
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));   //设置很大的数
	num = 0;
}
void insert2(int u, int v, int w) {
	e[num] = edge(v, w, head[u]);
	head[u] = num++;
}
void insert(int u, int v, int  w) {
	insert2(u, v, w);     //无向图相当于每个节点之间两条边
	insert2(v, u, w);
}
void spfa(int u) {
	dis[u] = 0;
	vis[u] = true;
	queue<int> ed;  //队列存放边的序号
	ed.push(u);
	while (!ed.empty()) {
		int minj = ed.front();
		ed.pop();
		vis[minj] = false;
		for (int j = head[minj]; j != -1; j = e[j].next) {
			int w = e[j].w;
			int v = e[j].v;
			if (w + dis[minj] < dis[v]) {
				dis[v] = w + dis[minj];
				//有更新才会入栈
				if (!vis[v]) {
					ed.push(v);
					vis[v] = true;
				}
			}
			
		}
	}

}
int main() {
	init();
	cin >> n >> m;
	int u, v, w;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		insert(u, v, w);
	}
	spfa(1);
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << endl;
	}
}
//判断是否存在负环
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
struct edge {
	//v为边指向的节点，w为边权
	int v, w, next;     //next记录的是与该边共起点的一条边的序号，与head数组配合可以遍历从一个节点发出的所有边
	edge() {};
	edge(int vv, int ww, int nextt) {
		v = vv;
		w = ww;
		next = nextt;
	}
}e[100000];
int head[100000];   //head[u]从u起点发出的边中的一条，搭配next属性可以从这条边开始遍历从u发出的所有边
int num;   //边的序号
int n, m;
bool vis[100000];
int dis[100000];
int cnt[1000000];   //记录每个点入栈的次数，用于判断负环
void init() {
	memset(head, -1, sizeof(head));
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));   //设置很大的数
	memset(cnt, 0, sizeof(cnt));
	num = 0;
}
void insert2(int u, int v, int w) {
	e[num] = edge(v, w, head[u]);
	head[u] = num++;
}
void insert(int u, int v, int  w) {
	insert2(u, v, w);     //无向图相当于每个节点之间两条边
	insert2(v, u, w);
}
int spfa(int u) {
	dis[u] = 0;
	cnt[u] = 1;
	vis[u] = true;
	queue<int> ed;  //队列存放边的序号
	ed.push(u);
	while (!ed.empty()) {
		int minj = ed.front();
		ed.pop();
		vis[minj] = false;
		for (int j = head[minj]; j != -1; j = e[j].next) {
			int w = e[j].w;
			int v = e[j].v;
			if (w + dis[minj] < dis[v]) {
				dis[v] = w + dis[minj];
				//有更新才会入栈
				if (!vis[v]) {
					ed.push(v);
					cnt[v]++;
					vis[v] = true;
					if (cnt[v] > n) {
						return 0;
					}
				}
			}

		}
	}
	return 1;
}
int main() {
	init();
	cin >> n >> m;
	int u, v, w;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		insert(u, v, w);
	}
	if (spfa(1)) {
		cout << "不存在负环" << endl;
	}
	else cout << "存在负环" << endl;

}
 Floyd：

时间复杂度：O（V的三次方）

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int g[105][105];   //邻接矩阵
//g[k][i][j]表示一种状态，即只经过1到k中的点的从i点到j点的最短路径,可以由两种状态转变而成，一种是不经过k点，另一种就是经过k点
//g[k][i][j] = min (g[k-1][i][j], g[k-1][i][k] + g[k-1][k][j])
//因为g[k-1][i][k] + g[k-1][k][j] 完全等价于 g[k][i][k] + g[k][k][j]
//所以可以等价变换成g[k][i][j] = min (g[k-1][i][j], g[k][i][k] + g[k][k][j])
//因此我们可以从小到大枚举k，舍弃k的这一维空间，即g[i][j] = min(g[i][j], g[i][k] + g[k][j])
//后面的g[i][j]是在前一轮循环中产生的最小路径，即g[k-1][i][j]，随后新一轮循环k++，此时得到的g[i][j]即为g[k][i][j]
void floyd(int n) {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
}
int main() {
	int n, m, u, v, w;
	cin >> n >> m;
	memset(g, 0x3f, sizeof(g));
	for (int i = 1; i <= 100; i++) {
		g[i][i] = 0;
	}
	while (m--) {
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = w;
	}
	floyd(n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << i << " " << j << " " << g[i][j] << endl;
		}
	}
}
kruskal最大/小生成树：
 

   Kruskal算法也叫避圈法，基于贪心策略，它通过不断选择图中权重最小的边来构建最小生成树。算法的主要思想是从所有边中按照权重从小到大进行选择，如果选择的边不会构成环（即不会形成闭合回路），就将该边加入最小成树中。为了避免环的形成，算法使用了并查集（Disjoint Set）数据结构来判断顶点是否连接。
二、Kruskal算法步骤

    将所有边按照权重从小到大进行排序。
    初始化并查集。
    从排好序的边中选择权重最小的边。
    如果该边连接的两个顶点不在同一个连通分量中（即不会形成环），则将该边加入最小生成树，并合并这两个顶点的连通分量。
    重复步骤3和步骤4，直到最小生成树中包含了V-1条边，其中V为顶点数。

例题：蓝桥杯真题

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
int n, m, q, next;
int fa[1000005];
int head[1000005];
int ans = 0x3f3f3f3f;
int vis[100005];
int len = 0;
int flag = 0;
//edge用来存最开始题目给的边，edge2用来存kruskal筛选后的边
struct edge {
	int u, v, w, next;
	edge() {};
	edge(int uu, int vv, int ww) {
		u = uu;
		v = vv;
		w = ww;
	}
	bool operator <(const edge& rhs) const {
		return rhs.w > w;
	}
}e[300005];
struct edge2 {
	int v, w, next;
	edge2() {};
	edge2(int vv,int ww,int nextt) {
		v = vv;
		next = nextt;
		w = ww;
	}
}e2[1000000];
//insert和insert2就是迪利斯特拉算法的模板
void insert2(int u, int v, int w) {
	e2[len] = edge2(v, w, head[u]);
	head[u] = len++;
}
void insert(int u, int v, int w) {
	insert2(u,v,w);
	insert2( v,u, w);
}
int cmp(edge a, edge b) {
	return a.w > b.w;
}
//并查集模板
void init() {
	memset(head, -1, sizeof(head));
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
}
int find(int x) {
	while (fa[x] != x) {
		x = fa[x];
	}
	return x;
}
bool unionn(int a, int b) {
	int aa = find(a);
	int bb = find(b);
	if (aa == bb) {
		return false;
	}
	else fa[aa] = bb;
	return true;
}
//最后题目会询问几组点之间的最小距离，dfs用于遍历最大生成树
void dfs(int u, int v, int dis) {
	if (u == v) {
		cout << dis << endl;
		flag = 1;
		return;
	}
	vis[u] = true;
	for (int i = head[u]; i != -1; i = e2[i].next) {
		if (!vis[e2[i].v]) dfs(e2[i].v, v, min(dis, e2[i].w));
	}
	vis[u] = false;
}
int main() {
	cin >> n >> m >> q;
	int u, v, w;
	int size = 0;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		e[size++] = edge(u, v, w);
	}
	//排序，进行kruskal算法
	sort(e, e + m, cmp);
	init();
	for (int i = 0; i < m; i++) {


		if (unionn(e[i].u, e[i].v)) {
			insert(e[i].u, e[i].v, e[i].w);
		}
	}
	//遍历目录树得到答案
	for (int i = 0; i < q; i++) {
		cin >> u >> v;

		dfs(u, v, 0x3f3f3f3f);
		if(flag == 0) cout << -1 << endl;
		flag = 0;
	}
}

 次短路径：

求出最短路径经过的每个点，每次删除其中的一个点求最短路径，这样求出的所有最短路径中最短的就是次短路径

LCA:

 圣诞树：

分析：

所有边的价值等于每个点到根节点的所有边乘上这些边的边权和之和，因此我们只需要从根节点做一次单源最短路径，令所有点到根节点的权值同时最小即可。

 地图：

 因为每个点都可以经过任意次，需要考虑正环的情况，直接将正环中的点的权值设置为无穷大即可。

成仙之路：

分析：

先不考虑等级问题，先建立起模型，可以将每个物品作为节点(成仙也是一个物品)，物品到物品之间需要加的价格为边权，然后自己设置一个0点，0点到每个物品的边的权值就等于这个物品的价格，然后从0点到成仙做最短路。

然后考虑价格问题，如果成仙的价格是L，那么能够交易的范围就在L-M到L+M,但这个范围是2M，我们需要枚举最低的等级，从L-M到L，因为M<20，所以最多枚举20次即可。

网络稳定性:

第一反应是Floyd，但是看了数据的大小感觉只能过30%

//最后过了两组，错了一组，其他超时
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
vector<vector<int>> v;
int main() {
	int n,m, x;
	cin >> n >> m >> x;
	int u, vv, w;
	for (int i = 0; i <= n + 1; i++) {
		vector<int> v1(n + 2, 0);
		v.push_back(v1);
	}
	for (int i = 1; i <= m; i++) {
		cin >> u >> vv >> w;
		v[u][vv]=max(v[u][vv],w);   //选稳定性最大的一条路
        v[vv][u]=max(v[vv][u],w);
	}
	for (int i = 1; i <= n; i++) {
		v[i][i] = 0x3f3f3f3f;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				v[i][j] = max(min(v[i][k], v[k][j]), v[i][j]);
			}
		}
	}
	for (int i = 1; i <= x; i++) {

		cin >> u >> vv;
		if (v[u][vv] == 0) cout << -1 << endl;
		else cout << v[u][vv] << endl;
	}
}

 后来发现可能dfs更快点。

对每个点都做一次dfs，时间复杂度是O（V*E），边数E最大为V的平方，也就是说这个 算法最大时间复杂度为O（V的三次方），和Floyd的固定复杂度一样。

特别是这题不需要枚举所有的点。

小技巧：

1.将9x9分成3x3的九个格子并分别编号

2.奇偶性剪枝

用一个二维数组，前一个是二进制数，后一个是空格的位置来表示状态，

常用函数：

memset：

memset(dp，0，sizeof(dp)); //dp为数组指针，需要头文件cstring。

memset是逐字节赋值，并不是将数组每一个元素的值赋值，参数可以选择0，-1，0x3f

0x3f很大，且两倍的0x3f不会超出int范围。

strcmp() 

#include<iostream>
#include<string.h>  //or #include<cstring>
using namespace std;

int main()
{
    char *a = "11112";
    char *b = "11117";
    cout<<strcmp(a,b)<<endl;
    return 0;
    
    //a==b -> 返回 0；
    //a>b -> 返回大于0的数；
    //a<b -> 返回小于0的数；
}

reverse

头文件：algorithm
reverse(st, ed)：反转一个数组、向量、字符串

islower、isupper

头文件：cctype
islower©：返回值bool，判断一个字符是否是小写或大写字母


tolower、toupper

tolower©：返回一个字符，如果c是大写字母就转化成小写字母
acsii码

大写字母转换为小写字母：c + 32 或 c - ‘A’ + ‘a’
小写字母转换为大写字母：c - 32 或 c - ‘a’ + ‘A’
字符转化成数字：‘6’ - ‘0’ = 6

find函数

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int a[10]={2,6,8,1,3,7,5,1,0,11};
	cout<<find(a+0,a+5,8)<<endl;//打印类似0x地址 
	cout<<find(a+0,a+5,8)-a<<endl;//打印数组【】内的序号 
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/555499.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

如何辨别：DNS污染or DNS劫持？

如何辨别：DNS污染or DNS劫持？

DNS劫持和DNS污染的情况在互联网中并不少见&#xff0c;到底是出现了DNS污染还是DNS劫持。什么是DNS污染&#xff1f;什么是DNS劫持&#xff1f;我们该如何辨别DNS污染和DNS劫持&#xff1f; DNS劫持&#xff1a; DNS 劫持是指恶意攻击者通过非法手段篡改了网络中的 DNS 服务…
阅读更多...
HTML快速入门

HTML快速入门

HTML简介 HTML&#xff08;超文本标记语言&#xff09;是一种用于创建网页和Web应用程序的标记语言。它由一系列标签组成&#xff0c;每个标签通过尖括号来定义&#xff0c;并用于标记文本、图像、链接和其他内容。HTML标签描述了网页中的信息结构和布局&#xff0c;并定义了文…
阅读更多...
[MySQL数据库] 索引与事务

[MySQL数据库] 索引与事务

1. 索引 1.1 概念 索引是一种特殊的文件&#xff0c;包含着对数据表里所有记录的引用指针.可以对表中的一列或多列创建索引,并指定索引的类型&#xff0c;各类索引有各自的数据结构实现. 1.2 作用 数据库中的表、数据、索引之间的关系&#xff0c;类似于书架上的图书、书籍…
阅读更多...
【Redis】面试题汇总

【Redis】面试题汇总

Redis什么是Redis、使用场景有哪些Redis 为什么这么快&#xff1f;Redis 数据类型及使用场景五种常见的 Redis 数据类型是怎么实现&#xff1f;Redis是单线程吗Redis 采用单线程为什么还这么快&#xff1f;Redis 如何实现数据不丢失&#xff1f;Redis 如何实现服务高可用&#…
阅读更多...
【复习笔记】FreeRTOS(六) 队列操作

【复习笔记】FreeRTOS(六) 队列操作

本文是FreeRTOS复习笔记的第六节&#xff0c;队列操作。 上一篇文章&#xff1a; 【复习笔记】FreeRTOS(五)时间片调度 文章目录 1.队列操作1.1.队列操作过程1.2.队列操作常用的API函数 二、实验设计三、测试例程四、实验效果 1.队列操作 队列是为了任务与任务、任务与中断之间…
阅读更多...
极狐GitLab x LigaAI，AI 时代研发提效新范式

极狐GitLab x LigaAI，AI 时代研发提效新范式

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 近日&#xff0c;极狐GitLab 和 LigaAI 宣布合作&#xff0c;双…
阅读更多...
分布式锁设计

分布式锁设计

一、为什么需要分布式锁 1.1 单体项目同步实现 在单进程&#xff08;启动一个jvm&#xff09;的系统中&#xff0c;当存在多个线程可以同时改变某个变量&#xff08;可变共享变量&#xff09;时&#xff0c;就需要对变量或代码块做同步&#xff0c;使其在修改这种变量时能够线…
阅读更多...
vue2中props属性设置一个对象或数组的默认值

vue2中props属性设置一个对象或数组的默认值

在Vue.js中&#xff0c;如果您想要为一个props属性设置一个对象或数组的默认值&#xff0c;您应该使用一个函数来返回这个默认值。这是因为对象和数组是引用类型&#xff0c;直接将它们作为默认值可能会导致预设的默认值被所有实例共享&#xff0c;这不是我们想要的结果。 下面…
阅读更多...
zabbix 自定义模板，邮件报警，代理服务器，自动发现与自动添加及snmp

zabbix 自定义模板，邮件报警，代理服务器，自动发现与自动添加及snmp

目录 一. 自定义监控内容 1. 在客户端创建自定义 key 2. 在 web 页面创建自定义监控项模块 2.1 创建模板 2.2 创建应用集 2.3 创建监控项 2.4 创建触发器 2.5 创建图形 2.6 将主机与模板关联起来 登录测试 2.7 设置邮件报警 测试邮件报警 3. nginx 服务状况的检测…
阅读更多...
Vue中SourceMap的使用方法详解

Vue中SourceMap的使用方法详解

目录 一、概述 二、使用方法 三、生成SourceMap 四、优化 五、结语 一、概述 Vue.js是一套构建用户界面的渐进式框架&#xff0c;通过HTML模板或者直接写render函数可以快速开发单页应用。在开发过程中&#xff0c;很多时候我们需要调试代码&#xff0c;追踪错误。Vue官方…
阅读更多...
Linux：调试器 - gdb

Linux：调试器 - gdb

Linux&#xff1a;调试器 - gdb gbd基本概念gbd调试浏览断点运行变量 gbd基本概念 GDB (GNU Debugger) 是一个强大的命令行调试工具,用于调试各种编程语言(如C、C、Java、Python等)编写的程序。使用 gdb可以帮助开发人员更快地定位和修复程序中的缺陷,提高代码质量和开发效率。…
阅读更多...
Python介绍(未完)

Python介绍(未完)

文章目录 Python 背景知识Python 是谁创造的&#xff1f;Python 可以用来干什么&#xff1f;Python 的优缺点 搭建 Python 环境安装 Python搭建 PyCharm 环境新工具到手&#xff0c;赶紧试试中文设置第一个Python程序 Python基础语法基础语法&#xff08;1&#xff09;常量和表…
阅读更多...
Error : java 错误 : 不支持发行版本5 ( 完美解决）

Error : java 错误 : 不支持发行版本5 ( 完美解决）

解决方案 1. 原因 idea的默认配置JDK版本与当前项目所需版本不一样 方案一&#xff08;每一个项目可能都要配置一遍&#xff09; Ctrlshitalts 打开项目结构&#xff0c;设置项目所需的JDK版本&#xff0c;本项目需要JDK8 Modules的JDK版本为5&#xff0c;这时就会报Error …
阅读更多...
最大公约数和最小公倍数（C语言）

最大公约数和最小公倍数（C语言）

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>//实现最大公约数函数&#xff1b; int max(int x, int y) {//初始化变量值&#xff1b;int judge 1;//运算&#xff1b;judge x %…
阅读更多...
Ubuntu 23.10.1 nginx源码安装

Ubuntu 23.10.1 nginx源码安装

注&#xff1a;以下所有命令均在root管理员模式下&#xff0c;若不是&#xff0c;请在所有命令前加sudo 1、安装依赖库 1.1、安装gcc g的依赖库 apt-get install build-essential apt-get install libtool1.2、安装pcre依赖库 apt-get update apt-get install libpcre3 lib…
阅读更多...
剑指Offer题目笔记33（并查集）

剑指Offer题目笔记33（并查集）

面试题116&#xff1a; 解决方案&#xff1a; ​ 一个班级可以包含一个或多个朋友圈&#xff0c;对应的图中可能包含一个或多个子图&#xff0c;每个朋友圈对应一个子图。因此&#xff0c;这个问题可以转化为如何求图中子图的数目。图的搜索算法可以用来计算图中子图的数目。扫…
阅读更多...
企业Linux特殊权限位/为什么会存在SUID?/企业环境测试（原理剖析）-4989字解析

企业Linux特殊权限位/为什么会存在SUID?/企业环境测试（原理剖析）-4989字解析

企业高薪思维&#xff1a; 坚持很难&#xff0c;优秀的人才是少数&#xff0c;很重要 坚持不下去&#xff0c;问自己想要什么&#xff1f; 问问自己想要好的生活状态&#xff1f;问自己有背景吗&#xff1f;你学历是亮点吗&#xff1f;有钱没&#xff0c;你也就是一般家庭&…
阅读更多...
selenium 下载文件取消安全下载的方法

selenium 下载文件取消安全下载的方法

问题描述 我要从一个网站上下载文件&#xff0c;谷歌浏览器总是自动阻止下载&#xff0c;并询问我是否保留。 可是&#xff0c;我想要的是不要询问&#xff0c;默认下载即可。 运行环境 OS: macOSselenium: 4.19.0python: 3.10.11Chrome: 124.0.6367.62selenium chromedrive…
阅读更多...
工会排队模式：创新营销的双赢之道

工会排队模式：创新营销的双赢之道

工会排队模式全面解读 在当今数字化营销的大潮中&#xff0c;促销方式层出不穷&#xff0c;但能真正抓住消费者眼球并带来双方共赢的模式并不多见。而工会排队模式便是在这样的背景下崭露头角&#xff0c;它巧妙地融合了工会积分、奖金池与排队机制&#xff0c;为消费者与商家…
阅读更多...
linux进阶篇：重定向和管道操作

linux进阶篇：重定向和管道操作

Linux中的重定向和管道操作 llinux中的三种IO设备&#xff1a; 标准输入&#xff08;STDIN&#xff09;,文件描述符号为&#xff1a;0&#xff0c;默认从键盘获取输入 标准输出&#xff08;STDOUT&#xff09;,文件描述符号位&#xff1a;1&#xff0c;默认输出到显示终端 标准…
阅读更多...
最新文章

Copyright @ 2022~2023