ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

需要经常练习的一些算法

2022年9月23日 104点热度 0人点赞 0条评论

为了熟悉各类算法原理,在这里整理一下一些需要经常练习的算法。

扩展欧几里得ex_gcd(求解ax + by = gcd(a, b) (mod p))

P1082 [NOIP2012 提高组] 同余方程 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1516 青蛙的约会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Problem - 2669 (hdu.edu.cn)

用于计算\(ax + by = c(mod p)\)的最小正整数解,如果\(c\)不是\(gcd(a, b)\)的倍数则无解。

void ex_gcd(int a,int b,int &d,int &x,int &y)
{
	if(!b)d = a, x = 1, y = 0;
	else ex_gcd(b, a % b, d, y, x), y -= x * (a / b);
}

记住ax = 1就可以记住d = a, x = 1, y = 0,记住b和a辗转相除,x, y换位置。

经常用于\(p = b\)的情况下求解,记得将x扩大c/d倍(x = x * c / d),因为用ex_gcd算出的x是在右侧等于gcd(a, b)的结果。

在算出x之后要使得x在modp意义下,所以需要对x取模加p再取模。

int d = 0, x = 0, y = 0;
ex_gcd(a, b, d, x, y);
if(p % d == 0)p /= d;
x = x * c / d;
x = (x % p + p) % p;

五行经典代码绝不出错。

主席树(类似树状数组,带前缀和的树)

P1972 [SDOI2009] HH的项链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P3834 【模板】可持久化线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

注意区间是[0, N]还是[1, N],root[i]表示第i个版本的根,插入函数要牢记,插入、查询函数记得判断x大小切掉一半的递归,确保每次只往一个方向递归。

主席树可以维护一个区间内的第k大的值,也可以维护区间数字的种类数。

树状数组(区间修改,区间查询)

P3368 【模板】树状数组 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间修改的树状数组用到了差分的思想,设差分数组为d,我们知道\(a[i] = \sum_{1}^{i}d[i]\),利用这个特性,可以知道\(\sum_{i = 1}^{N}a[i] = \sum_{i = 1}^{N}\sum_{j = 1}^{i}d[i]\),这个式子展开后容易发现\(\sum_{1}^{k}a[i] = \sum_{i = 1}^{k}k * d[i] - (i - 1)d[i]\),所以我们只需要维护一个\(d[i]\)和\((i - 1)d[i]\)即可,或者是\(d[i]\)和\(id[i]\)也可以。这里的k是随着查询而变化的,而i在修改的时候是不变的。

void add(int k,int x){for(int i = k;i <= N; i += lowbit(i))d[i] += x, di[i] += k * x;}
int getsum(int k)
{
	int res = 0;
	for(int i = k;i > 0; i -= lowbit(i))res += (k + 1) * d[i] - di[i];
	return res;
}

狠狠记住。

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 主席树 扩展欧几里得 树状数组 算法竞赛
最后更新:2022年9月23日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 扩展欧几里得ex_gcd(求解ax + by = gcd(a, b) (mod p))
  • 主席树(类似树状数组,带前缀和的树)
  • 树状数组(区间修改,区间查询)

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号