板子合集1.0

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/JK01WYX/

文章目录

  • 1.快速幂板子
  • 2.gcd得最大公约数
  • 3.堆优化的dijkstra板子
  • 4.线段树1板子 区间加
    • 线段树的结构关系：
    • int作为下标的：
    • long long作为下标的：
  • 5.线段树2板子 区间加与乘
  • 6.树状数组1板子 可修改单个点的前缀和
  • 7.树状数组2板子 差分数组快速区间加 求某个数
  • 8.manacher板子 快速求最长回文串的长度
    • 原理
    • 使用示范，本板子是加#(奇偶长度一起算)的：
    • 单独lamda:
    • OI Wiki摘录的只算单数和双数的：
  • 9.ST表板子 类似归并的有条理暴力 sparse-table
    • ST表部分的代码：
    • 使用示范：
  • 10.LCA倍增板子
    • 预处理：
    • LCA:
    • 主函数外版：
  • 11.KMP板子 前缀跳后缀
    • 原理：
    • 板子：
  • 12.扫描线板子 小思路
    • 前言：
    • 背景：
    • 扫描线原理：
    • 代码：
  • 13.龟速乘板子 a*二进制拆分的正数b（mod p）
  • 14.拓展欧几里得法求逆元
    • 板子：
    • 使用:
    • 原理：
    • 拓展欧几里得算法：
  • 15.二分图板子 匈牙利算法 KM算法
    • 原理：
    • 板子：
    • 使用：
  • 16.卢卡斯定理/Lucas定理板子 组合数板子
  • 17.高精度加法，乘法板子
    • High precision addition
    • High precision multiplication
  • 18.排列组合板子 A C
  • 19.快读快写板子
  • 20.分解质因数板子
  • 21.快速选择 数组中的第K个最大元素
  • 22. 26个质数
  • 23.多重背包问题
  • 24.归并
  • 25.判断是素数质数
  • 26.素数筛法
    • Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法）筛至平方根
    • 分块筛选
    • 线性筛法

1.快速幂板子

快速幂是快速算 a 的 c 次幂

原理：
我们用分治思想是比一个一个乘快的

即比如我们求a的8次方 ：a1a1 = a2 ,那么我们直接a2a2 = a4，a4*a4 = a8

参数就是几次幂。返回值是对应参数的幂 （这里对p取余了）(一般也把a当参数)

long long a, p;//a^c mod p=s
long long fp(int c)
{
    if(c==0)return 1;
    if (c == 1)return a % p;
 
 
    long long tmp = fp(c / 2); 
    if (c % 2 == 0)
        return tmp * tmp % p;
    else
        return tmp * tmp % p * a % p;
}
long long fp(long long a,int c)
{
    if(c==0)return 1;
    if (c == 1)return a % MOD;
    long long tmp = fp(a,c / 2); 
    if (c % 2 == 0)
        return tmp * tmp % MOD;
    else
        return tmp * tmp % MOD * a % MOD;
}

细节解释：
c == 1就是1次幂。

tmp就是a的c/2次幂。我们要返回c次幂，整数除法是向下取整的。

（比如5次幂，5/2==2，那么需要额外乘一个使得为c次幂）

——————————
非递归写法：(二进制拆分）

#define ll long long
ll mod = 1e9+7;
ll q(ll a,ll b)
{
    ll s = 1;
    while(b)
    {
        if(b&1) s = s * a %mod;
        a = a * a % mod;
        b >> 1;
    }
    return s;
}

2.gcd得最大公约数

证法一
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r不为0）
假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。
而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边可知m=r/d为整数，因此d|r
因此d也是b,a mod b的公约数。
因(a,b)和(b,a mod b)的公约数相等，则其最大公约数也相等，得证。
——————

百度百科证法一的一些便于理解的细节：

我们求 a 和 b 的最大公约数。

（如果a是b的倍数，那么b就是最大公约数。）

a>b，a可以表示为 a = kb + r

设d为a和b的最大公约数

对上式等号左右两端同时除以d，得 a/d = kb/d + r/d

a/d 和 kb/d都是整数，那么r/d也是整数。那么r也是d的倍数。同时r<b，r与b的最大公约数也是d

( r<d是因为r = a%b （由a的表示可知))

那么问题就转化成求 b 与 r 的最大公约数。

即 gcd(a,b) = gcd(b,a mod b)

r会一直变小，为0时，b就是最大公约数了 （b最小为1，当b为1时，余数必然为0）

——————

（当然再进一次循环就是 a 与 0 。返回a即可）：

long long gcd(long long a,long long b)
{
    if (a<b)
        swap(a,b); 
    if (b==0)      
        return a;
    else
        return gcd(b, a % b);
}

3.堆优化的dijkstra板子

1.第一个结构体dis_node把下标和该下标距起点的当前最短路放入一个结构体了，这样做堆排的时候方便找下标。

2.cmp仿函数是用于堆排比较器的，（试过greater<自己的类型>()是不行的。。）

建的小根堆快速选择当前最短路（dijkstra的原理）

①tmpdis代表节点之间的距离，有的时候就是1，自己设置吧，dijkstr主函数中算距离用。

②dij代表此点到所有点的最短路，所以我放参数列表当输出型参数了，许多题可能要用到。

③vector<set>arr代表通路，用set可以去重（有的题可能是多重图，即含平行边）。

④加强：自己到自己不用，所以if一下。因为next = cur，会吧dij[cur]给覆盖掉造成错误

    int tmpdis = 1;
    struct dis_node//放堆里面比长度，但是想知道端点
    {
        int dis;
        int next;
        bool operator < (const dis_node& a)
        {
            return dis < a.dis;
        }
        dis_node(int d, int n)
        {
            dis = d; next = n;
        }
    };
    class cmp
    {
    public:
        bool operator()(dis_node a, dis_node b)
        {
            return a.dis > b.dis;//
        }
    };
    void dijkstr(vector<int>&dij,vector<set<int>>& arr, int ori, int n)
    {
        priority_queue<dis_node, vector<dis_node>, cmp>heap;
        
        vector<int>barr(n + 1);
        int cur = ori;
        while (1)
        {
            //该次点所有可走的
            for (auto next : arr[cur])
            {
                if(next == cur)continue;
 
                //next就是下一个点（邻接表
                if (dij[next] == 0)
                    dij[next] = dij[cur] + tmpdis;
                else
                    dij[next] = min(dij[next], dij[cur] + tmpdis);
                heap.push(dis_node(dij[next], next));
            }
            //该点已使用，已最短，无需再抵达
            barr[cur] = 1;
            //最短路中找最短，同时可抵达的
            while (heap.size())
            {
                if (barr[heap.top().next] == 0)
                    break;
                heap.pop();
            }
            if (heap.size() == 0)break;
            cur = heap.top().next;
            heap.pop();
        }
    }

4.线段树1板子 区间加

类的构造函数写在类最后了，本板子没有将左右下标封装到节点中，而是实时计算的。

建议阅读：线段树 - OI Wiki (oi-wiki.org)

线段树的结构关系：

//		  1
//	  2      3			2^1
//	4   5  6   7		2^2
// 8 9					2^3
//1		log1==0
//2		log2==1		log3==1
//4		log4==2		log5==log6==log7==2
//8
//log5 == 2, +1在第三层，0~3 共四层 4
// 
//完全二叉树的总结点数就是：
//等比数列求和
//1*（2^  - 1）/(2-1)
//logn + 1层
//pow(2,(int)log2(n)+1)-1
//

int作为下标的：

template<class T>
class ST//segment tree
{
	struct node
	{
		T val;
		T t;//懒标记//服务后代
		node(T v = 0) :val(v), t(0)
		{}
	};
	int n = a.size();
	vector<T>a;
	vector<node>d;
public:
	void build_tree(int i, int l, int r)
	{
		if (l == r)
		{
			d[i].val = a[l];
			return;
		}
		int mid = l + (r - l) / 2;
		build_tree(i * 2, l, mid);
		build_tree(i * 2 + 1, mid + 1, r);
		d[i].val = d[i * 2].val + d[i * 2 + 1].val;
	}
	void spread(int i, int l, int r, int aiml, int aimr)
	{
		int mid = l + (r - l) / 2;
		if (d[i].t != 0 && l != r)
		{
			d[i * 2].val += d[i].t * (mid - l + 1);
			d[i * 2 + 1].val += d[i].t * (r - mid);
			d[i * 2].t += d[i].t;//可能上上次也没改
			d[i * 2 + 1].t += d[i].t;
			d[i].t = 0;
		}
	}
	T getsum(int l, int r)
	{
		return _getsum(1, 1, n, l, r);
	}
	T _getsum(int i, int l, int r, int aiml, int aimr)
	{
		if (aiml <= l && r <= aimr)//查询区间的子集全部加起来
			return d[i].val;
 
		//访问
		int mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);
 
		T ret = 0;
		if (aiml <= mid)
			ret += _getsum(i * 2, l, mid, aiml, aimr);
		if (aimr >= mid + 1)
			ret += _getsum(i * 2 + 1, mid + 1, r, aiml, aimr);
		return ret;
 
	}
	void update(int l, int r, ll val)
	{
		_update(1, 1, n, l, r, val);//加并挂标记
	}
	void _update(int i, int l, int r, int aiml, int aimr, ll val)
	{
		if (aiml <= l && r <= aimr)
		{
			d[i].val += val * (r - l + 1);
			d[i].t += val;
			return;
		}
 
 
		int mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);
 
		if (aiml <= mid)
			_update(i * 2, l, mid, aiml, aimr, val);
		if (aimr >= mid + 1)
			_update(i * 2 + 1, mid + 1, r, aiml, aimr, val);
		//我们只对叶子更新了，（别多想懒标记）
		d[i].val = d[i * 2].val + d[i * 2 + 1].val;
	}
	ST(vector<T>arr)
	{
		a = arr;
		n = a.size() - 1;
		d = vector<node>(pow(2, (int)log2(n) + 1 + 1) - 1 + 1);
		build_tree(1, 1, n);
	}
};

long long作为下标的：

#define ll long long
template<class T>
class ST//segment tree
{
	struct node
	{
		T val;
		T t;//懒标记//服务后代
		node(T v = 0) :val(v), t(0)
		{}
	};
	ll n = a.size();
	vector<T>a;
	vector<node>d;
public:
	void build_tree(ll i, ll l, ll r)
	{
		if (l == r)
		{
			d[i].val = a[l];
			return;
		}
		ll mid = l + (r - l) / 2;
		build_tree(i * 2, l, mid);
		build_tree(i * 2 + 1, mid + 1, r);
		d[i].val = d[i * 2].val + d[i * 2 + 1].val;
	}
	void spread(ll i, ll l, ll r, ll aiml, ll aimr)
	{
		ll mid = l + (r - l) / 2;
		if (d[i].t != 0 && l != r)
		{
			d[i * 2].val += d[i].t * (mid - l + 1);
			d[i * 2 + 1].val += d[i].t * (r - mid);
			d[i * 2].t += d[i].t;//可能上上次也没改
			d[i * 2 + 1].t += d[i].t;
			d[i].t = 0;
		}
	}
	T getsum(ll l, ll r)
	{
		return _getsum(1, 1, n, l, r);
	}
	T _getsum(ll i, ll l, ll r, ll aiml, ll aimr)
	{
		if (aiml <= l && r <= aimr)//查询区间的子集全部加起来
			return d[i].val;
 
		//访问
		ll mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);
 
		T ret = 0;
		if (aiml <= mid)
			ret += _getsum(i * 2, l, mid, aiml, aimr);
		if (aimr >= mid + 1)
			ret += _getsum(i * 2 + 1, mid + 1, r, aiml, aimr);
		return ret;
 
	}
	void update(ll l, ll r, ll val)
	{
		_update(1, 1, n, l, r, val);//加并挂标记
	}
	void _update(ll i, ll l, ll r, ll aiml, ll aimr, ll val)
	{
		if (aiml <= l && r <= aimr)
		{
			d[i].val += val * (r - l + 1);
			d[i].t += val;
			return;
		}
 
 
		ll mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);
 
		if (aiml <= mid)
			_update(i * 2, l, mid, aiml, aimr, val);
		if (aimr >= mid + 1)
			_update(i * 2 + 1, mid + 1, r, aiml, aimr, val);
		//我们只对叶子更新了，（别多想懒标记）
		d[i].val = d[i * 2].val + d[i * 2 + 1].val;
	}
	ST(vector<T>arr)
	{
		a = arr;
		n = a.size() - 1;
		d = vector<node>(pow(2, (ll)log2(n) + 1 + 1) - 1 + 1);
		build_tree(1, 1, n);
	}
};

5.线段树2板子 区间加与乘

当对区间即有加操作，又有乘操作时：

//乘法满足分配率！！，所以乘懒标记可以“攻击”加懒标记
//策略：两个标记都安排
//当乘标记来临时，对自己和懒标记都乘//假设都没有向后延伸
//
//（特别好的分析：）
//当加标记来临时，正常加就好啦，因为乘已经对加处理啦
//
//两个一起来临呢，先乘！！！！！！！！！！！！！！！！！
//(乘已经对这部分加处理过了)

template<class T>
class ST//segment tree
{
	struct node
	{
		T val;
		T t1;
		T t2;//乘
		node(T v = 0) :val(v), t1(0), t2(1)//x2x3 == x6
		{}
	};
	ll n = a.size();
	vector<T>a;
	vector<node>d;
public:
	void build_tree(ll i, ll l, ll r)
	{
		if (l == r)
		{
			d[i].val = a[l] % MOD;
			return;
		}
		ll mid = l + (r - l) / 2;
		build_tree(i * 2, l, mid);
		build_tree(i * 2 + 1, mid + 1, r);
		d[i].val = d[i * 2].val + d[i * 2 + 1].val;
	}
	void spread(ll i, ll l, ll r, ll aiml, ll aimr)
	{
		//懒惰
		ll mid = l + (r - l) / 2;
		//if ((d[i].t1 != 0 || d[i].t2 != 1) && l != r)
		//{
		T t1 = d[i].t1, t2 = d[i].t2;
		//先乘
		d[i * 2].val = (d[i * 2].val * t2) % MOD;
		d[i * 2].t1 = (d[i * 2].t1 * t2) % MOD;
		d[i * 2].t2 = (d[i * 2].t2 * t2) % MOD;
		d[i * 2 + 1].val = (d[i * 2 + 1].val * t2) % MOD;
		d[i * 2 + 1].t1 = (d[i * 2 + 1].t1 * t2) % MOD;
		d[i * 2 + 1].t2 = (d[i * 2 + 1].t2 * t2) % MOD;
 
		//后加
		d[i * 2].val = (d[i * 2].val + t1 * (mid - l + 1)) % MOD;
		d[i * 2 + 1].val = (d[i * 2 + 1].val + t1 * (r - mid)) % MOD;
		d[i * 2].t1 = (d[i * 2].t1 + t1) % MOD;
		d[i * 2 + 1].t1 = (d[i * 2 + 1].t1 + t1) % MOD;
 
		//复原
		d[i].t1 = 0;
		d[i].t2 = 1;
		//}
		/// 
	}
	ll getsum(ll l, ll r)
	{
		return _getsum(1, 1, n, l, r);
	}
	ll _getsum(ll i, ll l, ll r, ll aiml, ll aimr)
	{
		if (aiml <= l && r <= aimr)
			return d[i].val;
 
		ll mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);
 
		ll ret = 0;
		if (aiml <= mid)
			ret = (ret + _getsum(i * 2, l, mid, aiml, aimr)) % MOD;
 
		if (aimr >= mid + 1)
			ret = (ret + _getsum(i * 2 + 1, mid + 1, r, aiml, aimr)) % MOD;
		return ret;
 
	}
	void update1(ll l, ll r, ll val)
	{
		_update1(1, 1, n, l, r, val);//加并挂标记
	}
	void _update1(ll i, ll l, ll r, ll aiml, ll aimr, T val)
	{
		if (aiml <= l && r <= aimr)
		{
			d[i].t1 = (d[i].t1 + val) % MOD;
			d[i].val = (d[i].val + val * (r - l + 1)) % MOD;
			return;
		}
 
		ll mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);
 
		if (aiml <= mid)
			_update1(i * 2, l, mid, aiml, aimr, val);
		if (aimr >= mid + 1)
			_update1(i * 2 + 1, mid + 1, r, aiml, aimr, val);
		d[i].val = (d[i * 2].val + d[i * 2 + 1].val) % MOD;
	}
	void update2(ll l, ll r, T val)
	{
		_update2(1, 1, n, l, r, val);//加并挂标记
	}
	void _update2(ll i, ll l, ll r, ll aiml, ll aimr,T val)
	{
		if (aiml <= l && r <= aimr)
		{
			d[i].val = (d[i].val * val) % MOD;
			d[i].t1 = (d[i].t1 * val) % MOD;
			d[i].t2 = (d[i].t2 * val) % MOD;
			return;
		}
 
		ll mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);
 
		if (aiml <= mid)
			_update2(i * 2, l, mid, aiml, aimr, val);
		if (aimr >= mid + 1)
			_update2(i * 2 + 1, mid + 1, r, aiml, aimr, val);
		d[i].val = (d[i * 2].val + d[i * 2 + 1].val) % MOD;
	}
	ST(vector<T>arr)
	{
		a = arr;
		n = a.size() - 1;
		d = vector<node>(pow(2, (ll)log2(n) + 1 + 1) - 1 + 1);
		build_tree(1, 1, n);
	}
};

6.树状数组1板子 可修改单个点的前缀和

请添加图片描述

树状数组中，规定 c[x] 管辖的区间长度为 2 k 2^{k} 2k，其中：

设二进制最低位为第 0 位，则 k 恰好为 x 二进制表示中，最低位的 1 所在的二进制位数；
2^k（c[x] 的管辖区间长度）恰好为 x 二进制表示中，最低位的 1 以及后面所有 0 组成的数。

对于lowbit的证明，注意正数的原码反码和补码是相同的。

add函数给该节点增加值后，while循环一直找父节点加值。

template<class T>
class BIT//Binary Indexed Tree
{
public:
	ll n;//a的大小
	vector<T>a;//原数组
	vector<T>c;//树状数组
	ll lowbit(ll a)
	{
		return a & -a;
	}
	T getsum(ll i)
	{
		T sum = 0;
		while (i > 0)
		{
			sum += c[i];
			i -= lowbit(i);
		}
		return sum;
	}
	void add(ll i, T v)
	{
		while (i <= n)
		{
			c[i] += v;
			i = i + lowbit(i);
		}
	}
	BIT(vector<T>_a)
	{
		a = _a;
		n = a.size() - 1;
		c = vector<T>(n + 1);
		//直接把树建好
		for (ll i = 1; i <= n; i++)
		{
			add(i, a[i]);
		}
	}
};

7.树状数组2板子 差分数组快速区间加 求某个数

add可以给一个数加值

如果想给一段区间加值，有没有更快的操作：add1

实际上，这个是差分数组，差分的前缀和就是这个位置的数值，所以是用来求单个数的

template<class T>
class BIT//Binary Indexed Tree
{
public:
	ll n;//a的大小
	vector<T>a;//原数组
	vector<T>c;//树状数组//还是求和，只不过传过来的是差分了
	ll lowbit(ll a)
	{
		return a & -a;
	}
	T getsum(ll i)
	{
		T sum = 0;
		while (i > 0)
		{
			sum += c[i];
			i -= lowbit(i);
		}
		return sum;
	}
	void add(ll i, ll v)
	{
		while (i <= n)
		{
			c[i] += v;
			i += lowbit(i);
		}
	}
	void add1(ll l, ll r, ll v)
	{
		add(l, v);
		add(r + 1, -v);
	}
	BIT(vector<T>_a)
	{
		a = _a;
		n = a.size() - 1;
		c = vector<T>(n + 1);
		//直接把树建好
		for (ll i = 1; i <= n; i++)
		{
			add(i, a[i]);
		}
	}
};

使用示范：

//差分构造：
void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int>arr(n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}
	vector<int>d(n + 1);
	d[1] = arr[1];
	for (int i = 2; i <= n; i++)
	{
		d[i] = arr[i] - arr[i - 1];
	}
	BIT<int> demo(d);
 
	/// <summary>
 
	for (int i = 1; i <= m; i++)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x, y, k;
			cin >> x >> y >> k;
			demo.add1(x, y, k);
		}
		else if (op == 2)
		{
			int x;
			cin >> x;
			cout << demo.getsum(x) << endl;
		}
	}
}

8.manacher板子 快速求最长回文串的长度

原理

r记录当前最右的回文（l（左）与之对应），这样我们后来在r中偏右进行判断时，因为l r之间是回文，所以可以参照中偏左对应的位置，少判断许多次。

使用示范，本板子是加#(奇偶长度一起算)的：

d[i]表示以位置i为中心的最长回文串的半径长度

d数组的值-1即是本位置最长回文长度，原因看最下面注释。

void solve()
{
	string str, aim;
	cin >> str;
	aim += "#";
	for (int i = 0; i < str.size(); i++)
	{
		aim += str[i];
		aim += "#";
	}
 
	vector<int>d(aim.size());
 
	//  abcba
	auto manacher = [&](string s) {
		int l = 0, r = -1;
		for (int i = 0; i < s.size(); i++)
		{
			int k = i > r ? 1 : min(d[l + r - i], r - i + 1);//左边对称相同，但不越界
			//k是半径，加了等于下一位
			//朴素算法
			while (i - k >= 0 && i + k <= s.size() && s[i - k] == s[i + k])
				k++;
			d[i] = k;
			if (i + d[i] - 1 > r)
			{
				r = i + d[i] - 1;
				l = i - d[i] + 1;
			}
		}
	};
	manacher(aim);
	int ans = 0;
	for (auto x : d)
	{
		ans = max(ans, x);
	}
    //d[i]表示i（不包括i）左右的对称的长度
	// # a # b # a #
	//		 - - - -
	// # a # b # b # a #
	//		   - - - - -
	cout << ans - 1;
}

单独lamda:


   //  abcba
   auto manacher = [&](string s) {
   	int l = 0, r = -1;
   	for (int i = 0; i < s.size(); i++)
   	{
   		int k = i > r ? 1 : min(d[l + r - i], r - i + 1);//左边对称相同，但不越界
   		//k是半径，加了等于下一位
   		//朴素算法
   		while (i - k >= 0 && i + k <= s.size() && s[i - k] == s[i + k])
   			k++;
   		d[i] = k;
   		if (i + d[i] - 1 > r)
   		{
   			r = i + d[i] - 1;
   			l = i - d[i] + 1;
   		}
   	}
   };

————

OI Wiki摘录的只算单数和双数的：

vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
  int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
  while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
    k++;
  }
  d1[i] = k--;
  if (i + k > r) {
    l = i - k;
    r = i + k;
  }
}

vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
  int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
  while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
    k++;
  }
  d2[i] = k--;
  if (i + k > r) {
    l = i - k - 1;
    r = i + k;
  }
}

9.ST表板子 类似归并的有条理暴力 sparse-table

1.原理是“倍增”，直到两个长度为1的就可以合成一个长度为2的，两个2合成4，两个4合成8。

2.最后使用时没必要追求“正好匹配”，可以在范围内取多点：

比如看48长度为5（45678），我们取长度为4，看47与5~8的最大值哪个更大即可。

ST表部分的代码：

//ST表
	vector<vector<int>>st(30,vector<int>(n+1));//len = 2的i次方
	int len = 1;
	for (int pow = 0; len <= n; pow++, len *=2)
	{
		for (int left = 1; left <= n- len+1; left++)
		{
			if (pow == 0)
				st[0][left] = arr[left];
			else
			{
				st[pow][left] = max(st[pow - 1][left], st[pow - 1][min(left + len / 2,n)]);
			}
		}
	}

使用示范：

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int>arr(n+1);
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}
	//ST表
	vector<vector<int>>st(30,vector<int>(n+1));//len = 2的i次方
	int len = 1;
	for (int pow = 0; len <= n; pow++, len *=2)
	{
		for (int left = 1; left <= n- len+1; left++)
		{
			if (pow == 0)
				st[0][left] = arr[left];
			else
			{
				st[pow][left] = max(st[pow - 1][left], st[pow - 1][min(left + len / 2,n)]);
			}
		}
	}
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		//l+len-1<=r	len = 2的k次方
		//len <= r-l+1
		//k <= log(r-l+1);
		int k = log2(r - l + 1);
		cout << max(st[k][l], st[k][r-pow(2,k)+1]) << endl;
	}
}

10.LCA倍增板子

预处理：

void solve()
{
	int n, k;
	cin >> n >> k;
	vector<vector<int>>alist(n + 1);
	for (int i = 1; i <= n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		alist[x].push_back(y);
		alist[y].push_back(x);
	}
	vector<vector<int>>fa(n + 1, vector<int>(22));
	vector<int>dep(n + 1);
 
	vector<int>leaf;
	auto dfs = [&](int cur, int pa, auto dfs)->void {
		dep[cur] = dep[pa] + 1;
		if (alist[cur].size() == 1)
		{
			leaf.push_back(cur);
		}
		for (auto x : alist[cur])
		{
			if (x != pa)
			{
				fa[x][0] = cur;
				dfs(x, cur, dfs);
			}
		}
	};
	dfs(1, 0, dfs);
	//倍增求父亲
	for (int p = 1; p < 22; p++)
	{
		for (int i = 1; i <= n; i++)
		{
			fa[i][p] = fa[fa[i][p - 1]][p - 1];
		}
	}

LCA:

auto LCA = [&](int a, int b)->pair<int, int>
{
	ll ans = 0;
	if (dep[a] < dep[b])swap(a, b);
 
	while (dep[a] > dep[b])
	{
		int dis = (int)log2(dep[a] - dep[b]);
		a = fa[a][dis];
		ans += pow(2, dis);
	}
 
	for (int i = log2(dep[a]); i >= 0; i--)
	{
		if (fa[a][i] != fa[b][i])	//向上结果不同才跳
		{
			a = fa[a][i];
			b = fa[b][i];
			ans += pow(2, i) * 2;
		}
	}
	if (a != b)
	{
		a = b = fa[a][0];
		ans += 2;
	}
	return { a ,ans };
};

第一个让a，b深度相同的操作是while进行的，二进制拆分。

主函数外版：

inline int LCA(int a,int b)
{
	if (dep[a] < dep[b])swap(a, b);
	while (dep[a] > dep[b])
	{
		int dis = (int)log2(dep[a] - dep[b]);
		a = fa[a][dis];
	}
	if (a == b)return a;
	for (int i = log2(dep[a]); i >= 0; i--)
	{
		if (fa[a][i] != fa[b][i])
		{
			a = fa[a][i];
			b = fa[b][i];
		}
	}
	if (a != b)
	{
		a = b = fa[a][0];
	}
	return a;
}

使用示范：（链式前向星等，POJ 3417 Network 树上差分 LCA 链式前向星 仍超时，加上快读过-CSDN博客）

struct node
{
	int b, next;
}edges[maxn*2];
int head[maxn];
int k = 0;
inline void add(int a, int b)
{
	k++;
	edges[k].b = b;
	edges[k].next = head[a];
	head[a] = k;
}
int fa[maxn][23];
int dep[maxn];
void dfs1(int cur ,int pa)
{
	dep[cur] = dep[pa] + 1;
	fa[cur][0] = pa;
	for (int p = 1; p < 22; p++)
		fa[cur][p] = fa[fa[cur][p - 1]][p - 1];
 
	for (int i = head[cur]; i > 0; i = edges[i].next)
	{
		if(edges[i].b != pa)
			dfs1(edges[i].b, cur);
	}
}
inline int LCA(int a,int b)
{
	if (dep[a] < dep[b])swap(a, b);
	while (dep[a] > dep[b])
	{
		int dis = (int)log2(dep[a] - dep[b]);
		a = fa[a][dis];
	}
	if (a == b)return a;
	for (int i = log2(dep[a]); i >= 0; i--)
	{
		if (fa[a][i] != fa[b][i])
		{
			a = fa[a][i];
			b = fa[b][i];
		}
	}
	if (a != b)
	{
		a = b = fa[a][0];
	}
	return a;
}
int diff[maxn];
int pass[maxn];
int cnt0, cnt1;
void dfs2(int cur,int pa)
{
	pass[cur] += diff[cur];
	for (int i = head[cur]; i > 0; i = edges[i].next)
	{
		if (edges[i].b != pa)
		{
			dfs2(edges[i].b, cur);
			pass[cur] += pass[edges[i].b];
		}
	}
}

11.KMP板子 前缀跳后缀

原理：

出现重复【 存在部分前缀等于后缀 （自己的前面一部分跟后面一部分一样的） 】的时候，可以跳！
请添加图片描述

来源：KMP算法中next数组的理解 - 知乎 (zhihu.com)

（其实原理好懂，实现起来是有些难度的。）

板子：

kmp的返回值可以自己选择，比如第一次匹配成功返回位置，或者返回能匹配的数量。

//kmp
int kmp(vector<int> next, string str1, int len1, string str2, int len2)
{
	int i = 0, j = 0;
	int count = 0;
	while (i < len1)
	{
		if (j == -1 || str1[i] == str2[j])
		{
			i++; j++;
		}
		else
			j = next[j];
 
		if (j == len2)
		{
			count++;
			// 
			//最后一个比完后进来这个位置
			//return i - len2 + 1;//"第几个位置"
			//cout << i - len2 + 1 << endl;
 
			i--;
			j--;
			j = next[j];
		}
	}
	return count;
}
 
 
//next
void get_next(vector<int>& next, string str2, int len2)
{
	int i = 0, j = -1;
	next[0] = -1;
	while (i < len2)
	{
		if (j == -1 || str2[i] == str2[j])
		{
			i++, j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

12.扫描线板子 小思路

前言：

本板子是结合我的线段树1板子和OIWIKI的扫描线写成的类。

线段树1板子 区间加-CSDN博客

扫描线 - OI Wiki (oi-wiki.org)

背景：

照着OI WIKI打了一遍，结果洛谷交上去RE，查了半天查不出来，最后看讨论区，给线段树大小再乘个2，就过了。。

我还数组以为太大了呢

本题数组并不大：
请添加图片描述

本题的xy是坐标，看的是坐标间的长度，应该是线段树进行二分的时候都要有mid，所以会多分几次。

扫描线原理：

我们从下往上扫吧。

离散化就是把出现的x坐标放到数组里，排好序，数组里只有我们要的x。

离散化x后对这个数组进行建树。

然后我们从下往上是根据y坐标进行的，所以每个y捆绑对应的x1,x2,以及加或减。

//这就是整个策略了。

代码：

#define ll long long
#define endl "\n"
#define int long long
const ll inf = 1e9;
 
template<class T>
class ST//segment tree
{
	struct node
	{
		T l, r, sum;
		T t;//懒标记//服务后代
		node() :l(0), r(0), sum(0), t(0)
		{}
	};
	ll n;
	vector<T>a;
	vector<node>d;
	//扫描线中，上面的node中的l,r代表矩形左右
	//下面的l,r是线段树的下标，每个a表示的是一个横坐标
public:
	void push_up(ll i)
	{
		if (d[i].t > 0)//扫描到了
			d[i].sum = d[i].r - d[i].l;
		else
			d[i].sum = d[i * 2].sum + d[i * 2 + 1].sum;
	}
	//直到最左和最右范围，但是不知道其中的和
	void build_tree(ll i, ll l, ll r)
	{
		ll mid = l + (r - l) / 2;
		if (l + 1 < r)
		{
			d[i].l = a[l];
			d[i].r = a[r];
			build_tree(i * 2, l, mid);
			build_tree(i * 2 + 1, mid, r);
			push_up(i);
		}
		else
		{
			d[i].l = a[l];
			d[i].r = a[r];
			d[i].sum = 0;
		}
	}
	void update(ll l, ll r, ll val)
	{
		_update(1, l, r, val);//加并挂标记
	}
	void _update(ll i, ll l, ll r, ll val)
	{
		if (d[i].l == l && d[i].r == r)
		{
			d[i].t += val;
			push_up(i);
			return;
		}
		else
		{
			//中分
			if (d[i * 2].r > l)
				_update(i * 2, l, min(d[i * 2].r, r), val);//r在下一个内就不多传了
			if (d[i * 2 + 1].l < r)
				_update(i * 2 + 1, max(l, d[i * 2 + 1].l), r, val);
			push_up(i);
		}
	}
	T get_sum()
	{
		return d[1].sum;
	}
	ST(vector<T>arr)
	{
		a = arr;
		n = a.size() - 1;
		d = vector<node>(2*pow(2, (ll)log2(n) + 1 + 1) + 1);
		build_tree(1, 1, n);
	}
};
struct scanline
{
	int l, r, h;
	int mark;
	bool operator <(const scanline b)const
	{
		return h < b.h;
	}
};
//总的sum统计了此刻矩形的长度，update一直在更新这个长度
void solve()
{
	int n; cin >> n;
	vector<int>xaxis;
	vector<scanline>yaxis;
	//x离散化用来服务线段树
	//y该多少个就多少个，遇到就改，离散化了求得高度差，同层是0
 
	//该加加，该减减，区间求和改成求长度吧
	xaxis.push_back(0);
	yaxis.push_back({});
	for (int i = 1; i <= n; i++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		xaxis.push_back(x1);
		xaxis.push_back(x2);
		yaxis.push_back({ x1,x2,y1,1 });
		yaxis.push_back({ x1,x2,y2,-1 });
	}
	sort(xaxis.begin() + 1, xaxis.end());
	sort(yaxis.begin() + 1, yaxis.end());
	unique(xaxis.begin() + 1, xaxis.end());
	ST<int> demo(xaxis);
	int ans = 0;
	for (int i = 1; i < yaxis.size() - 1; i++)//最后一次不用算了
	{
		demo.update(yaxis[i].l, yaxis[i].r, yaxis[i].mark);
		ans += demo.get_sum() * (yaxis[i + 1].h - yaxis[i].h);
	}
	cout << ans;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

13.龟速乘板子 a*二进制拆分的正数b（mod p）

如果要乘负数b，先乘正的，最后结果加负号即可。

ll mul(ll a, ll b, ll p) {
	// 将乘法变为加法，二进制优化，边加边模
	ll ans = 0;
	while (b) {
		if (b & 1)
			ans = (ans + a) % p;
		a = (a + a) % p;
		b >>= 1;
	}
	return ans;
}

14.拓展欧几里得法求逆元

板子：

x即为最终答案，x可能为负数，加模数即可

乘法逆元 - OI Wiki (oi-wiki.org)

void exgcd(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1, y = 0;
		return;
	}
	exgcd(b, a % b, y, x);
	y -= a / b * x;
}

使用:

	exgcd(a, n + 1, x, y);//x就是逆元
	while (x <= 0)x += n + 1;

原理：

最大公约数 - OI Wiki (oi-wiki.org)
请添加图片描述

拓展欧几里得算法：

int Exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int d = Exgcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}

15.二分图板子 匈牙利算法 KM算法

KM算法

原理：

匈牙利算法：二分图最大权匹配 - OI Wiki

简单说就是挨个找，找到就退出。后面的来了就让前面的挪位置。

板子：

book指给u找位置时，有人考虑过的位置就不考虑了。

match[ i ]就是i位置对应的人。

e是关系

int book[10001];
int match[10001];
bool e[101][101];
int ans=0,n=0,m=0;
bool dfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(book[i]==0 && e[u][i]==true)
        {
            book[i]=1;
            if(match[i]==0 || dfs(match[i])==true)
            {
                match[u]=i;
                match[i]=u;
                return true;
            }
        }
    }
    return false;
}

使用：

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x=0,y=0;
        scanf("%d %d",&x,&y);
        e[x][y]=true;
        e[y][x]=true;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            book[j]=0;
        }
        if(dfs(i)==true)
        {
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}

16.卢卡斯定理/Lucas定理板子 组合数板子

a是阶乘数组，提前处理好，处理到模数应该够的。

ksm快速幂

C是组合数函数，ksm是用来费马小定理求逆元（即倒数）。就是组合数公式，n的阶乘除以（m的阶乘和n-m的阶乘）。

Lucas 卢卡斯定理 - OI Wiki (oi-wiki.org)

ll a[100005];
ll ksm(int x, int y,int mod) {//因为数据范围很大容易爆掉，所以就要Fast_Pow
	if (x == 1) return 1;
	ll res = 1, base = x;
	while (y) {
		if (y & 1) res = (res * base) % mod;
		base = (base * base) % mod;
		y >>= 1;
	}
	return res;
}
 
ll C(ll n, ll m,ll p) 
{
	if (m > n)return 0;
	return ((a[n] * ksm(a[m], p - 2, p)) % p * ksm(a[n - m], p - 2, p) % p);
}
 
long long Lucas(long long n, long long m, long long p) 
{
    if (m == 0) return 1;
    return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}

17.高精度加法，乘法板子

High precision addition

string hpa(string str1,string str2)
{
    int a[10000] = { 0 }, b[10000] = { 0 }, c[10000] = { 0 };
    int len1 = str1.size(), len2 = str2.size();
    //`len1>=len2
    if (len2 > len1)swap(str1, str2), swap(len1, len2);
    for (int i = 0; i < len1; i++)
        a[i] = str1[len1-1-i] - '0';
    for (int i = 0; i < len2; i++)
        b[i] = str2[len2-1-i] - '0';
    for (int i = 0; i < len1; i++)
    {
        c[i + 1] = (a[i] + b[i] + c[i])/10;
        c[i] = (c[i] + a[i] + b[i]) % 10;
    }
    if (c[len1] != 0)len1++;
    string ret;
    for (int i = len1 - 1; i >= 0; i--)
    {
        ret += '0' + c[i];
    }
    return ret;
}

High precision multiplication

//     999
//     999
//----------
//    8991
//   8991
//  8991
//  123456
string hpm(string str1,string str2)
{
    int a[10000] = { 0 }, b[10000] = { 0 }, c[10000] = { 0 };
    int len1 = str1.size(), len2 = str2.size();
    for (int i = 0; i < len1; i++)
        a[i] = str1[len1 - 1 - i] - '0';
    for (int i = 0; i < len2; i++)
        b[i] = str2[len2 - 1 - i] - '0';
    for (int i = 0; i < len1; i++)
    {
        for (int j = 0; j < len2; j++)
        {
            c[i + j] += a[i] * b[j];//也可以顺便在最后处理
        }
    }
    int len = len1 + len2;
    for (int i = 0; i < len; i++)
    {
        c[i + 1] += c[i] / 10;
        c[i] = c[i] % 10;
    }
    while (c[len - 1] == 0&&len>1/**/)
    {
        len--;
    }
    string ret;
    for (int i = len - 1; i >= 0; i--)
    {
        ret += '0' + c[i];
    }
    return ret;
}

18.排列组合板子 A C

a是阶乘数组，预处理一下

ksm快速幂求的是逆元。用的是费马小定理，适用于模数为素数的时候。

ll ksm(int x, int y, int mod) 
{
	if (x == 1) return 1;
	ll res = 1, base = x;
	while (y) {
		if (y & 1) res = (res * base) % mod;
		base = (base * base) % mod;
		y >>= 1;
	}
	return res;
}
ll C(ll n, ll m, ll p)
{
	if (m > n)return 0;
	return ((a[n] * ksm(a[m], p - 2, p)) % p * ksm(a[n - m], p - 2, p) % p);
}
ll A(ll n, ll m, ll p)
{
	if (m > n)return 0;
	return (a[n] * ksm(a[n - m], p - 2, p)) % p;
}

19.快读快写板子

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
inline void write(int x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

20.分解质因数板子

vector<int>divide(int x)
{
	vector<int>ret;
	for (int i = 2; i <= x / i; i++)//i*i <= x 
	{
		if (x % i == 0)
		{
			ret.push_back(i);
			while (x % i == 0)
				x /= i;
		}
	}
	if (x > 1)ret.push_back(x);
	return ret;
}

21.快速选择 数组中的第K个最大元素

class Solution {
    int _k;
public:
    // [0,l][l+1,r-1][r,nums.size()-1]
    int _sort(int left,int right,vector<int>& nums)
    {
        if(left==right)return nums[left];
        int aim = getRandom(left,right,nums);
        int i = left,l = left-1,r = right+1;
        while(i<r)
        {
            if(nums[i]<aim)swap(nums[++l],nums[i++]);
            else if(nums[i] == aim)i++;
            else swap(nums[--r],nums[i]);
        }
        if(nums.size()-1-r+1>=_k)
            return _sort(r,right,nums);
        else if(nums.size()-1-(l+1)+1>=_k)
            return nums[i-1];
        else
            return _sort(left,l,nums);
    }
    int getRandom(int left,int right,vector<int>& nums)
    {
        int r = rand();
        return nums[r%(right-left+1) + left];
                    /*    偏移量   */
    }
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(NULL));
        _k = k;
        return _sort(0,nums.size()-1,nums);
    }
};

22. 26个质数

int arr[26] = {2,3,5,7,11
    ,13,17,19,23,29
    ,31,37,41,43,47
    ,53,59,61,67,71
    ,73,79,83,89,97,101};

23.多重背包问题

const int MAX = 1e3 + 5;
int v[MAX], w[MAX], s[MAX];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, V;
	cin >> N >> V;
	for (int i = 1; i <= N; i++)
	{
		cin >> w[i] >> v[i] >> s[i];
	}
	int dp[MAX] = { 0 };
	for (int i = 1; i <= N; i++)
	{
		if (s[i] == -1)
		{
			for (int j = V; j >= w[i]; j--)
			{
				dp[j] = max(dp[j], dp[j - w[i]]+v[i]);
			}
		}
		else if (s[i] == 0)
		{
			for (int j = w[i]; j <= V; j++)
			{
				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
		else if (s[i] > 0)
		{
			int num = min(s[i], V/w[i]);
			for (int k = 1;num>0; k <<= 1)
			{
				if (num < k)k = num;
				num -= k;
				for (int j = V; j >= w[i] * k; j--)
				{
					dp[j] = max(dp[j], dp[j-w[i]*k]+v[i]*k);
				}
			}
		}
	}
	cout << dp[V];
	return 0;
}

24.归并

class Solution {
    int marr[50005];
public:
    void merge(int left,int right,vector<int>&arr)
    {
        if (left >= right)return;
        int mid = (left + right)>>1;//3 /2  + 5/2
        merge(left, mid,arr);
        merge(mid+1, right,arr);
        int aim = left;
        int part1 = left, part2 = mid + 1;
        while (part1<=mid && part2<=right)
        {
            if (arr[part1] <= arr[part2])
                marr[aim++] = arr[part1++];
            else
                marr[aim++] = arr[part2++];
        }
        while (part1 <= mid)
            marr[aim++] = arr[part1++];
        while (part2 <= right)
            marr[aim++] = arr[part2++];
        //最后再赋回去。。
        for (int i = left; i <= right; i++)
            arr[i] = marr[i];
    }
    vector<int> sortArray(vector<int>& nums) 
    {
        merge(0,nums.size()-1,nums);
        return nums;
    }
};

25.判断是素数质数

bool is_prime(int x)
{
	for(int i = 2; i * i <= x; i++)
	{
		if (x % i == 0)return false;
	}
	return true;
}

26.素数筛法

Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法）筛至平方根

考虑这样一件事情：对于任意一个大于 1 的正整数 n，那么它的 x 倍就是合数（x > 1）。利用这个结论，我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

vector<int> prime;
bool is_prime[N];

void Eratosthenes(int n) {
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; ++i) is_prime[i] = true;
  // i * i <= n 说明 i <= sqrt(n)
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i])
      for (int j = i * i; j <= n; j += i) is_prime[j] = false;
  }
  for (int i = 2; i <= n; ++i)
    if (is_prime[i]) prime.push_back(i);
}

分块筛选

int count_primes(int n) {
  const int S = 10000;
  vector<int> primes;
  int nsqrt = sqrt(n);
  vector<char> is_prime(nsqrt + 1, true);
  for (int i = 2; i <= nsqrt; i++) {
    if (is_prime[i]) {
      primes.push_back(i);
      for (int j = i * i; j <= nsqrt; j += i) is_prime[j] = false;
    }
  }
  int result = 0;
  vector<char> block(S);
  for (int k = 0; k * S <= n; k++) {
    fill(block.begin(), block.end(), true);
    int start = k * S;
    for (int p : primes) {
      int start_idx = (start + p - 1) / p;
      int j = max(start_idx, p) * p - start;
      for (; j < S; j += p) block[j] = false;
    }
    if (k == 0) block[0] = block[1] = false;
    for (int i = 0; i < S && start + i <= n; i++) {
      if (block[i]) result++;
    }
  }
  return result;
}

线性筛法

也称为 Euler 筛法（欧拉筛法）

vector<int> pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.push_back(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之，i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

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

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

相关文章

Vue--》打造简易直播应用平台项目实战

Vue--》打造简易直播应用平台项目实战

今天开始使用 vue3 + ts 搭建一个简易直播应用平台项目，因为文章会将项目的每一个地方代码的书写都会讲解到，所以本项目会分成好几篇文章进行讲解，我会在最后一篇文章中会将项目代码开源到我的github上，大家可以自行去进行下载运行，希望本文章对有帮助的朋友们能多多关注本…
阅读更多...
奇怪的需求之与图片做交互

奇怪的需求之与图片做交互

1.起因 客户想要展示自己的地图,该地图上有各种工作数据,和工作点位,已有的地图不能满足需求.于是提出将这张图片当成大背景 2.经过 鉴于文件格式和尺寸的原因,协商后客户提出将图片做成缩放效果,同时具有点击效果,原先直接进入的主页,现在为点击图片中的某条线路进入主页面…
阅读更多...
【论文阅读】多传感器SLAM数据集

【论文阅读】多传感器SLAM数据集

一、M2DGR 该数据集主要针对的是地面机器人&#xff0c;文章正文提到&#xff0c;现在许多机器人在进行定位时&#xff0c;其视角以及移动速度与车或者无人机有着较大的差异&#xff0c;这一差异导致在地面机器人完成SLAM任务时并不能直接套用类似的数据集。针对这一问题该团队…
阅读更多...
Sentinel 规则持久化，基于Redis持久化【附带源码】

Sentinel 规则持久化，基于Redis持久化【附带源码】

B站视频讲解 学习链接&#x1f517; 文章目录 一、理论二、实践2-1、dashboard 请求Redis2-1-1、依赖、配置文件引入2-1-2、常量定义2-1-3、改写唯一id2-1-4、新Provider和Publisher2-1-5、改写V2 2-2、应用服务改造2-2-1、依赖、配置文件引入2-2-2、注册监听器 三、源码获取3…
阅读更多...
从0到1实现自助棋牌室系统：技术调研

从0到1实现自助棋牌室系统：技术调研

前言 春节返乡之际&#xff0c;发现老家县城竟然开了近十家棋牌室。巧的是朋友也有意涉足&#xff0c;便咨询我自助棋牌室的软件投入成本。作为程序员的我&#xff0c;在思考了自助棋牌室背后的技术需求后&#xff0c;嗅到了一丝丝商机&#xff1a;何不自己开发一个自助棋牌室…
阅读更多...
操作系统的运行机制

操作系统的运行机制

目录 一. 特权指令与非特权指令二. 中断和异常2.1. 内中断2.2 外中断 三. 系统调用 注:很多人习惯把Linux、Windows、MacOS的“小黑框”中使用的命令也称为“指令”&#xff0c;其实这是“交互式命令接口”&#xff0c;注意与本节的“指令”区别开。本节中的“指令”指二进制机…
阅读更多...
jenkins实战（1）

jenkins实战（1）

一, Jenkins官网介绍: Jenkins 持续集成、持续部署 下载地址:Jenkins download and deployment 提供两种类型: LTS(长期版)和Weekly(最近一周的版本) 注: 必须是Java8及以上版本(官网针对这一点有做说明) 二, 安装 下载war包,java -jar XXX --httpPort8081 或 下载war包…
阅读更多...
Linux：kubernetes（k8s）搭建mater节点（kubeadm，kubectl，kubelet）（2）

Linux：kubernetes（k8s）搭建mater节点（kubeadm，kubectl，kubelet）（2）

安装k8有多种方式如&#xff1a; minikube kubeadm 二进制安装 命令行工具 我这里就使用kubeadm进行安装 环境 3台centos7 master ip &#xff1a;192.168.113.120 2G运存 2内核 node1 ip &#xff1a;192.168.113.121 2G运存 2内核 node2 ip &#xff1a;192.168.1…
阅读更多...
Tiktok算法还原-x-gorgon还原验证

Tiktok算法还原-x-gorgon还原验证

数据正确 数据错误
阅读更多...
Myqsort：基于冒泡排序算法的C语言实现

Myqsort：基于冒泡排序算法的C语言实现

我们将详细介绍一个基于冒泡排序算法的自定义排序函数——Mysqrt。该函数通过使用用户提供的比较函数进行元素间的比较&#xff0c;并结合swap交换函数对任意类型的数据进行排序。下面是对代码的逐行解析。 逻辑导图 代码实现 // 头文件 #include<stdio.h>// 定义比较函…
阅读更多...
关于uniapp小程序的分包问题

关于uniapp小程序的分包问题

开发uniapp小程序时&#xff0c;在打包上传代码时会出现超出2M的打包限制不能上传&#xff0c;那么我们该怎么做呢&#xff1f; 1.对于图片&#xff0c;将图片从后端服务取&#xff0c;尽量不要放在静态资源&#xff0c;图片体积会影响打包大小。 2.使用分包&#xff0c;tabb…
阅读更多...
SSH教程

SSH教程

ssh 是远程连接的利器, 可以说凡是涉及到 linux 服务器, ssh 就是一个绕不开的话题. 本文作为一个教程, 尽可能详细的帮助读者设置 ssh, 并给出一些常用的 ssh 配置方法 (主要用于 linux 系统的远程登录和文件传输). 1. 简介 ssh 分为两个部分, sshd 服务端和 ssh 客户端. ssh…
阅读更多...
2024-02学习笔记

2024-02学习笔记

1.当我们向Set集合中添加一个已经存在的元素时 当我们向Set集合中添加一个已经存在的元素时&#xff0c;Set集合会如何处理呢&#xff1f;实际上&#xff0c;Set集合不会将重复的元素添加到集合中。当我们向Set集合中添加一个元素时&#xff0c;Set集合会首先判断该元素是否已…
阅读更多...
[C++]C++使用yolov9结合bytetrack实现目标追踪演示

[C++]C++使用yolov9结合bytetrack实现目标追踪演示

【简介】 在C中实现YOLOv9的目标检测与ByteTrack的多目标追踪是一个相对复杂的过程&#xff0c;涉及到深度学习、计算机视觉和实时数据处理等多个领域。下面我将简单介绍这两个技术&#xff0c;并概述如何在C中实现它们。 YOLOv9&#xff08;You Only Look Once&#xff0c;版…
阅读更多...
STL常见容器（map/multimap容器）---C++

STL常见容器（map/multimap容器）---C++

STL常见容器目录&#xff1a; 8.map/ multimap容器8.1 map基本概念8.2 map构造和赋值8.3 map大小和交换8.4 map插入和删除8.5 map查找和统计8.6 map容器排序8.6.1 内置类型排序8.6.2 自定义类型排序8.6.3 自定义和内置类型混合排序 8.7 实例8.7.1 案例描述8.7.2 实现步骤 8.map…
阅读更多...
Vue.js+SpringBoot开发高校实验室管理系统

Vue.js+SpringBoot开发高校实验室管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、研究内容2.1 实验室类型模块2.2 实验室模块2.3 实验管理模块2.4 实验设备模块2.5 实验订单模块 三、系统设计3.1 用例设计3.2 数据库设计 四、系统展示五、样例代码5.1 查询实验室设备5.2 实验放号5.3 实验预定 六、免责说明 一、摘…
阅读更多...
基于springboot+vue的人格障碍诊断系统

基于springboot+vue的人格障碍诊断系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…
阅读更多...
云服务器租用哪家好？不要忽视第3点

云服务器租用哪家好？不要忽视第3点

注册资本&#xff1a;5亿元 权威认证&#xff1a;中央网信办云服务安全审查DJCP网络安全等级保护ITSS工信部云计算服务能力评估CSA STAR认证管理体系认证信息安全安全管理体系认证可信云服务认证可信云云主机等级评估5星 PCI-DSS支付卡行业数据安全认证 租哪家云服务器比较好&…
阅读更多...
关于拖拽功能

关于拖拽功能

文章目录 写在前面自己手动实现拖拽的demo技术细节&#xff1a;Js中拖拽(拉)事件&#xff08;drag 和 drop&#xff09;浏览器兼容性拖拽Api的介绍拖拽流程1.dragstart事件2.dragenter事件3.dragover事件4.drop事件(必须要dragover事件触发)5.dragend事件MDN关于拖拽的解析 相关…
阅读更多...
latex中\documentclass[preprint,review,12pt]{elsarticle}的详细解释

latex中\documentclass[preprint,review,12pt]{elsarticle}的详细解释

在LaTeX中&#xff0c;\documentclass 是一个命令&#xff0c;用于指定文档所使用的文档类。文档类定义了文档的总体结构、格式和样式。elsarticle 是一个常用的文档类&#xff0c;它主要用于在Elsevier出版的期刊上提交论文。 详细解释 \documentclass[preprint,review,12pt…
阅读更多...
最新文章

Copyright @ 2022~2023