搜索模板
搜索模板
基本包括了DFS和BFS的所有类型
BFS
常用于求最小值
基于迭代,相较于 DFSDFSDFS 不容易爆栈。
Flood Fill 模型
顾名思义洪水覆盖问题。
可以在 线性 时间复杂度内找到矩阵内某个点所在的连通块。
可以维护所有矩阵内连通块的个数
123456789101112131415161718192021222324252627282930313233343536373839typedef pair<int, int> pii;int n, m; //矩阵的长和宽int vis[MAXN][MAXN]; //标记每个点属于哪一个连通块,0表示还问访问过int mp[MAXN][MAXN]; //每个点的权值int dx[4] = {0, 0, -1, 1};int dy[4] = {-1, 1, 0, 0};int cnt = 0; //连通块个数int size[MAXN]; //连通块内部元素个数void bfs(int x, int y) { que ...
数学提高模板
数学提高
此部分由我前队友完成。浏览体验可能会有所不同因为水平比我强
有些地方无法正常浏览,可能是因为我队友有些用的LateX语法,markdown渲染不出来
常用数学技巧和公式
1. 常用公式
完全立方公式
(a+b)3=a3+3a2b+3ab2+b3=a3+b3+3ab(a+b)(a+b)^3=a^3+3a^2b+3ab^2+b^3=a^3+b^3+3ab(a+b)(a+b)3=a3+3a2b+3ab2+b3=a3+b3+3ab(a+b)
a3+b3=(a+b)3−3ab(a+b)=(a+b)(a2+b2−ab)a^3+b^3=(a+b)^3-3ab(a+b)=(a+b)(a^2+b^2-ab)a3+b3=(a+b)3−3ab(a+b)=(a+b)(a2+b2−ab)
(a−b)3=a3−3a2b+3ab2−b3=a3−b3+3ab(b−a)(a-b)^3=a^3-3a^2b+3ab^2-b^3=a^3-b^3+3ab(b-a)(a−b)3=a3−3a2b+3ab2−b3=a3−b3+3ab(b−a)
a3−b3=(a−b)3+3ab(a−b)=(a−b)(a2+b2+a ...
数学基础模板
数学基础
此部分由我前队友完成。浏览体验可能会有所不同因为水平比我强
有些地方无法正常浏览,可能是因为我队友有些用的LateX语法,markdown渲染不出来
组合数
1. 求组合数
根据不同的数据范围,求组合数也可以运用不同的方法。总的式子:
Cab=a!b!(a−b)!C_a^b=\frac{a!}{b!(a-b)!}Cab=b!(a−b)!a!
表示从aaa个物品中选出bbb个的方案数。
(1) 递推法
使用递推式Cab=Ca−1b+Ca−1b−1C_a^b=C_{a-1}^b+C_{a-1}^{b-1}Cab=Ca−1b+Ca−1b−1
证明:考虑已经得知了Ca−1k,k∈[0,b]C_{a-1}^k,k\in[0,b]Ca−1k,k∈[0,b]的结果,那么当前有aaa个物品时,第aaa个物品要么被选,要么不被选中。若被选中,则方案一共有Ca−1b−1C_{a-1}^{b-1}Ca−1b−1个,若不被选中,则方案有Ca−1bC_{a-1}^bCa−1b个,方案累加,得证。
时间复杂度O(n2)O(n^2)O(n2)
12345678910void in ...
数据结构模板-上
数据结构模板
包含了ACM里面常用的基本数据结构
链表
单链表
1234567891011121314151617181920212223242526272829303132333435// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点// MAXN表示最大点数int head = 0, e[MAXN], ne[MAXN], idx;void init() { //初始化链表 idx = 0, head = 0;}void insert(int val) { // 在链表头部插入一个数val e[++ idx] = val, ne[idx] = head, head = idx;}void insert_after(int k, int val) { // 在下标为k的节点后插入一个数val e[++idx] = val; ne[idx] = ne[k]; ne[k] = idx;}void remove_head() ...
计算几何模板
计算几何模板
此部分由我前队友完成。浏览体验可能会有所不同因为水平比我强
有些地方无法正常浏览,可能是因为我队友有些用的LateX语法,markdown渲染不出来
基础模板及常用小函数
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#define Vector Point#define PI acos(-1)/*判断double x 的正负 1:正 0:0 -1:负*/int sgn(double x){ if (fabs(x) < ZERO) return 0; else if (x > 0) return 1; else return -1;}/** 封装点 重载 + - * / < == 运算符*/struct Point{ double x, y; Point(d ...
动态规划模板-上
动态规划模板
包含了ACM一些常用的动态规划模型
思维导图:
数字三角形模型
每次只能向下走或者向右走。从起点走到终点。
题目给定一个 n×nn \times nn×n 的矩阵,矩阵中的每个格子上有一个价值为 www 的物品。给定起点 (1,1)(1,1)(1,1) 和终点 (n,n)(n, n)(n,n) ,规定只能向下或者向右走。从起点出发两次,但同一个格子在两次路径中都经过的话,他的物品价值只会被累加一次。问两次路线,途径格子的物品的总价值最大是多少。
注意到每次走一步,横纵坐标的和都会加1.且知道横坐标,纵坐标,和两个坐标的和的任意两个就能知道另外一个。这就启示我们可以状态压缩。
另外两次行动可以看成一起同步行动。通过这样的想法就定义出 dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示 aaa 路线当前横坐标为 iii ,bbb 路线当前横坐标为 jjj ,横纵坐标和为 kkk 时的最大总价值。
状态只能由 dp[i−1][j][k−1],dp[i][j−1][k−1],dp[i][j][k−1],dp[i−1][j−1][k−1]dp[i - ...
JS常用库
js常用库
计时器
setTimeout(func, delay)
delay毫秒后,执行函数func
clearTimeout()
关闭计时器,例如:
12345let timeout_id = setTimeout(() => { console.log("Hello World!")}, 2000); // 2秒后在控制台输出"Hello World"clearTimeout(timeout_id); // 清除定时器
setInterval(func, delay)
每隔delay毫秒,执行一次函数func
clearInterval()
12345let interval_id = setInterval(() => { console.log("Hello World!")}, 2000); // 每隔2秒,输出一次"Hello World"clearInterval(interval_id); // 清除周期执 ...
Jquery常用
jQuery常用
选择器
$(selector)$,例如:
1234$('div');$('.big-div');$('div > p');let $DIV = $(`div`);
用法和CSS选择器差不多
事件
$(selector).on(event, func)绑定事件
123$('div').on('click', function (e) { console.log("click div");})
$(selector).off(event, func)删除事件
12345$('div').on('click', function (e) { console.log("click div"); $('div').off('click');});
当存在多个相同类型的事件触发函数时,可以通过 ...
JS常用语法
JavaScript常用语法
JS的调用方式
直接在<script type="module"></script>标签内些JS代码
引入文件<script type="module" src="/static/js/index.js"></script>
将所需的代码通过import关键字引入到当前作用域
示例:
12345678910let name = "acwing";function print() { console.log("Hello World!");}export { name, print}
123456<script type="module"> import { name, print } from "/static/js/index.js"; console.log( ...
git常用命令
git命令分类整理
全局设置
git config --global user.name xxx 设置全局用户名,信息记录在 ~/.gitconfig文件中
git config --global user.email xxx@xxx.com 设置全局邮箱地址,信息记录在~/.gitconfig文件中
git init 将当前目录配置成git仓库,信息记录在隐藏的.git文件夹中
常用命令
git add XX 将XX文件添加到暂存区
git commit -m “备注” 将暂存区的内容提交到当前分支
git status 查看仓库状态
git push -u (第一次需要-u以后不需要) 将当前分支推送到远程仓库
git log 查看当前分支的所有版本
git clone git@git.acwing.com:xxx/XXX.git 将远程仓库XXX下载到当前目录下
git branch 查看所有分支和当前所有分支
git remote rm origin 删除原来的origin
查看命令
git diff XX 查看XX文件相对于暂存区修改了哪些内容 ...