广安哪里做网站,织梦安装教程,用服务器ip做网站页面,用html5做的静态网站网站版权声明#xff1a;本文为博主原创文章#xff0c;遵循 CC 4.0 BY-SA 版权协议#xff0c;转载请附上原文出处链接和本声明。
原文链接#xff1a;https://blog.csdn.net/JK01WYX/ 文章目录 1.快速幂板子2.gcd得最大公约数3.堆优化的dijkstra板子4.线段树1板子 区间加线段…版权声明本文为博主原创文章遵循 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-tableST表部分的代码使用示范 10.LCA倍增板子预处理LCA:主函数外版 11.KMP板子 前缀跳后缀原理板子 12.扫描线板子 小思路前言背景扫描线原理代码 13.龟速乘板子 a*二进制拆分的正数bmod p14.拓展欧几里得法求逆元板子使用:原理拓展欧几里得算法 15.二分图板子 匈牙利算法 KM算法原理板子使用 16.卢卡斯定理/Lucas定理板子 组合数板子17.高精度加法乘法板子High precision additionHigh precision multiplication 18.排列组合板子 A C19.快读快写板子20.分解质因数板子21.快速选择 数组中的第K个最大元素22. 26个质数23.多重背包问题24.归并25.判断是素数质数26.素数筛法Eratosthenes 筛法埃拉托斯特尼筛法简称埃氏筛法筛至平方根分块筛选线性筛法 1.快速幂板子 快速幂是快速算 a 的 c 次幂 原理 我们用分治思想是比一个一个乘快的
即比如我们求a的8次方 a1a1 a2 ,那么我们直接a2a2 a4a4*a4 a8
参数就是几次幂。返回值是对应参数的幂 这里对p取余了(一般也把a当参数)
long long a, p;//a^c mod ps
long long fp(int c)
{if(c0)return 1;if (c 1)return a % p;long long tmp fp(c / 2); if (c % 2 0)return tmp * tmp % p;elsereturn tmp * tmp % p * a % p;
}
long long fp(long long a,int c)
{if(c0)return 1;if (c 1)return a % MOD;long long tmp fp(a,c / 2); if (c % 2 0)return tmp * tmp % MOD;elsereturn tmp * tmp % MOD * a % MOD;
}细节解释 c 1就是1次幂。
tmp就是a的c/2次幂。我们要返回c次幂整数除法是向下取整的。
比如5次幂5/22那么需要额外乘一个使得为c次幂
—————————— 非递归写法(二进制拆分
#define ll long long
ll mod 1e97;
ll q(ll a,ll b)
{ll s 1;while(b){if(b1) s s * a %mod;a a * a % mod;b 1;}return s;
}2.gcd得最大公约数
证法一 a可以表示成a kb rabkr皆为正整数且r不为0 假设d是a,b的一个公约数记作d|a,d|b即a和b都可以被d整除。 而r a - kb两边同时除以dr/da/d-kb/d由等式右边可知mr/d为整数因此d|r 因此d也是b,a mod b的公约数。 因(a,b)和(b,a mod b)的公约数相等则其最大公约数也相等得证。 ——————
百度百科证法一的一些便于理解的细节 我们求 a 和 b 的最大公约数。 如果a是b的倍数那么b就是最大公约数。
aba可以表示为 a kb r
设d为a和b的最大公约数
对上式等号左右两端同时除以d得 a/d kb/d r/d
a/d 和 kb/d都是整数那么r/d也是整数。那么r也是d的倍数。同时rbr与b的最大公约数也是d
( rd是因为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 (ab)swap(a,b); if (b0) return a;elsereturn gcd(b, a % b);
}3.堆优化的dijkstra板子
1.第一个结构体dis_node把下标和该下标距起点的当前最短路放入一个结构体了这样做堆排的时候方便找下标。
2.cmp仿函数是用于堆排比较器的试过greater自己的类型()是不行的。。
建的小根堆快速选择当前最短路dijkstra的原理 ①tmpdis代表节点之间的距离有的时候就是1自己设置吧dijkstr主函数中算距离用。
②dij代表此点到所有点的最短路所以我放参数列表当输出型参数了许多题可能要用到。
③vectorsetarr代表通路用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(vectorintdij,vectorsetint arr, int ori, int n){priority_queuedis_node, vectordis_node, cmpheap;vectorintbarr(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;elsedij[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 log10
//2 log21 log31
//4 log42 log5log6log72
//8
//log5 2, 1在第三层0~3 共四层 4
//
//完全二叉树的总结点数就是
//等比数列求和
//1*2^ - 1/(2-1)
//logn 1层
//pow(2,(int)log2(n)1)-1
//int作为下标的
templateclass T
class ST//segment tree
{struct node{T val;T t;//懒标记//服务后代node(T v 0) :val(v), t(0){}};int n a.size();vectorTa;vectornoded;
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(vectorTarr){a arr;n a.size() - 1;d vectornode(pow(2, (int)log2(n) 1 1) - 1 1);build_tree(1, 1, n);}
};long long作为下标的
#define ll long long
templateclass T
class ST//segment tree
{struct node{T val;T t;//懒标记//服务后代node(T v 0) :val(v), t(0){}};ll n a.size();vectorTa;vectornoded;
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(vectorTarr){a arr;n a.size() - 1;d vectornode(pow(2, (ll)log2(n) 1 1) - 1 1);build_tree(1, 1, n);}
};5.线段树2板子 区间加与乘
当对区间即有加操作又有乘操作时
//乘法满足分配率所以乘懒标记可以“攻击”加懒标记
//策略两个标记都安排
//当乘标记来临时对自己和懒标记都乘//假设都没有向后延伸
//
//特别好的分析
//当加标记来临时正常加就好啦因为乘已经对加处理啦
//
//两个一起来临呢先乘
//(乘已经对这部分加处理过了)templateclass 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();vectorTa;vectornoded;
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(vectorTarr){a arr;n a.size() - 1;d vectornode(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^kc[x] 的管辖区间长度恰好为 x 二进制表示中最低位的 1 以及后面所有 0 组成的数。
对于lowbit的证明注意正数的原码反码和补码是相同的。
add函数给该节点增加值后while循环一直找父节点加值。
templateclass T
class BIT//Binary Indexed Tree
{
public:ll n;//a的大小vectorTa;//原数组vectorTc;//树状数组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(vectorT_a){a _a;n a.size() - 1;c vectorT(n 1);//直接把树建好for (ll i 1; i n; i){add(i, a[i]);}}
};7.树状数组2板子 差分数组快速区间加 求某个数
add可以给一个数加值
如果想给一段区间加值有没有更快的操作add1
实际上这个是差分数组差分的前缀和就是这个位置的数值所以是用来求单个数的
templateclass T
class BIT//Binary Indexed Tree
{
public:ll n;//a的大小vectorTa;//原数组vectorTc;//树状数组//还是求和只不过传过来的是差分了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(vectorT_a){a _a;n a.size() - 1;c vectorT(n 1);//直接把树建好for (ll i 1; i n; i){add(i, a[i]);}}
};使用示范
//差分构造
void solve()
{int n, m;cin n m;vectorintarr(n 1);for (int i 1; i n; i){cin arr[i];}vectorintd(n 1);d[1] arr[1];for (int i 2; i n; i){d[i] arr[i] - arr[i - 1];}BITint demo(d);/// summaryfor (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 #;}vectorintd(aim.size());// abcbaauto 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:
// abcbaauto 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摘录的只算单数和双数的
vectorint 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;}
}vectorint 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长度为545678我们取长度为4看47与5~8的最大值哪个更大即可。
ST表部分的代码
//ST表vectorvectorintst(30,vectorint(n1));//len 2的i次方int len 1;for (int pow 0; len n; pow, len *2){for (int left 1; left n- len1; 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;vectorintarr(n1);for (int i 1; i n; i){cin arr[i];}//ST表vectorvectorintst(30,vectorint(n1));//len 2的i次方int len 1;for (int pow 0; len n; pow, len *2){for (int left 1; left n- len1; 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;//llen-1r len 2的k次方//len r-l1//k log(r-l1);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;vectorvectorintalist(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);}vectorvectorintfa(n 1, vectorint(22));vectorintdep(n 1);vectorintleaf;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)-pairint, 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 };
};第一个让ab深度相同的操作是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(vectorint 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;}elsej 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(vectorint 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;}elsej 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;templateclass T
class ST//segment tree
{struct node{T l, r, sum;T t;//懒标记//服务后代node() :l(0), r(0), sum(0), t(0){}};ll n;vectorTa;vectornoded;//扫描线中上面的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;elsed[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(vectorTarr){a arr;n a.size() - 1;d vectornode(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;vectorintxaxis;vectorscanlineyaxis;//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());STint 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*二进制拆分的正数bmod 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 ans0,n0,m0;
bool dfs(int u)
{for(int i1;in;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 i1;im;i){int x0,y0;scanf(%d %d,x,y);e[x][y]true;e[y][x]true;}for(int i1;in;i){for(int j1;jn;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_Powif (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();//len1len2if (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] 0len1/**/){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 || ch9){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.分解质因数板子
vectorintdivide(int x)
{vectorintret;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][l1,r-1][r,nums.size()-1]int _sort(int left,int right,vectorint nums){if(leftright)return nums[left];int aim getRandom(left,right,nums);int i left,l left-1,r right1;while(ir){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-r1_k)return _sort(r,right,nums);else if(nums.size()-1-(l1)1_k)return nums[i-1];elsereturn _sort(left,l,nums);}int getRandom(int left,int right,vectorint nums){int r rand();return nums[r%(right-left1) left];/* 偏移量 */}int findKthLargest(vectorint 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;num0; 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,vectorintarr){if (left right)return;int mid (left right)1;//3 /2 5/2merge(left, mid,arr);merge(mid1, right,arr);int aim left;int part1 left, part2 mid 1;while (part1mid part2right){if (arr[part1] arr[part2])marr[aim] arr[part1];elsemarr[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];}vectorint sortArray(vectorint 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。利用这个结论我们可以避免很多次不必要的检测。
如果我们从小到大考虑每个数然后同时把当前这个数的所有比自己大的倍数记为合数那么运行结束的时候没有被标记的数就是素数了。
vectorint 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;vectorint primes;int nsqrt sqrt(n);vectorchar 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;vectorchar 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 筛法欧拉筛法
vectorint 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;}}}
}
