摘要: 归并排序模板。 #include <bits/stdc++.h> using namespace std; long long cnt = 0; int a[1000007], b[1000007]; void merge_sort(int l, int r) { if (l == r) retur 阅读全文
posted @ 2022-05-13 01:51 空白菌 阅读(33) 评论(0) 推荐(0) 编辑
摘要: 高精度模板,现在有__int128,能不用高精度就不用吧。 /** 整数高精度 */ ///继承vector解决位数限制(当前最大位数是9倍整型最大值),操作方便(注意size()返回无符号长整型,尽量不要直接把size放入表达式) struct Huge_Int :vector<long long 阅读全文
posted @ 2022-02-18 03:33 空白菌 阅读(78) 评论(0) 推荐(0) 编辑
摘要: 快读快写模板,加速输入输出。 #include <iostream> using namespace std; template<class T> inline void read(T &val) { T x = 0, f = 1;char c = getchar(); while (c < '0' 阅读全文
posted @ 2022-02-17 19:32 空白菌 阅读(23) 评论(0) 推荐(0) 编辑
摘要: 快速排序模板。 #include <iostream> using namespace std; int a[100000+7]; void quick_sort(int l,int r){ int i = l,j = r; int mid = a[(l+r)/2]; while(i<=j) { w 阅读全文
posted @ 2022-02-17 19:31 空白菌 阅读(33) 评论(0) 推荐(0) 编辑
摘要: 数论算法模板,最近不更新。 /** 模意义下运算 */ ///龟速乘取余,O(logb) const int mod = 1e9 + 7; ll qmul(ll a, ll b) { ll ans = 0; while (b) { if (b & 1) ans = (ans + a) % mod; 阅读全文
posted @ 2022-02-17 19:26 空白菌 阅读(46) 评论(0) 推荐(0) 编辑
摘要: 算法简述 KMP是单模匹配算法,在一个长度为n的文本串中查找一个长度为m的模式串。它的时间复杂度是O(m+n),是这类算法的理论最优复杂度。 模式匹配:在长为n的字符串S中,找到某个长为m的模式串P,复杂度至少是O(m+n)。 朴素的模式匹配算法 普通的暴力方法是从S中逐个字符开始匹配P中每个字符。 阅读全文
posted @ 2022-01-21 23:32 空白菌 阅读(71) 评论(0) 推荐(0) 编辑
摘要: 比赛链接 A 题意 判断输入字符串与 $\pi$ 的最长前缀匹配,不超过 $30$ 位。 题解 知识点:模拟。 抄样例最后一个 $30$ 都正确的,直接匹配。 时间复杂度 $O(1)$ 空间复杂度 $O(1)$ 代码 #include <bits/stdc++.h> using namespace 阅读全文
posted @ 2023-01-29 16:27 空白菌 阅读(15) 评论(1) 推荐(1) 编辑
摘要: 比赛链接 A 题意 给两个数字 $a,b$ ,每次操作可以使 $a$ 加上 $+1,+2,+5,-1,-2,-5$ 中的一个数,求最少多少次操作可以将 $a$ 变成 $b$ 。 题解 知识点:贪心。 可以贪心取,先 $5$ 后 $2$ 再 $1$ 。 一点小结论(可能是假的qwq): 考虑三个硬币 阅读全文
posted @ 2023-01-27 18:42 空白菌 阅读(14) 评论(0) 推荐(0) 编辑
摘要: 比赛链接 A 题意 给 $n$ 个正整数,找到三个数,使得他们的和为奇数,输出他们的下标。 题解 知识点:贪心。 找到三个奇数或者一个奇数两个偶数即可,其他情况无解。 时间复杂度 $O(n)$ 空间复杂度 $O(n)$ 代码 #include <bits/stdc++.h> using namesp 阅读全文
posted @ 2023-01-26 22:17 空白菌 阅读(99) 评论(0) 推荐(2) 编辑
摘要: 比赛链接 A 题意 给定 $n$ 个怪物的血量 $h_i$ ,每次可以选择两种操作之一: 选择一个怪物直接杀死。 选择两个怪物血量减一(怪物血量为 $0$ 视作死亡)。 问最少多少次操作可以消灭所有怪物。 题解 知识点:贪心。 存在一对血量为 $1$ 的怪物选择操作2最好,否则选择操作1。 时间复杂 阅读全文
posted @ 2023-01-25 21:03 空白菌 阅读(50) 评论(0) 推荐(1) 编辑
摘要: A 题解 知识点:贪心。 把所有正偶数除成奇数,即可。 (人傻了没加 $x>0$ WA2 时间复杂度 $O(n)$ 空间复杂度 $O(1)$ 代码 #include <bits/stdc++.h> using ll = long long; using namespace std; int main 阅读全文
posted @ 2023-01-24 22:24 空白菌 阅读(108) 评论(0) 推荐(0) 编辑
摘要: 比赛链接 A 题解 知识点:数学。 用 $n$ 减去区间1的端点得到匹配的一个区间,求一下与区间2的交集。 一个小公式,两区间 $[L_1,R_1]$ 和 $[L_2,R_2]$ 的交集长度为 $\max(0, \min(R_1, R_2) - \max(L_1, L_2) + 1)$ 。 时间复杂 阅读全文
posted @ 2023-01-19 01:35 空白菌 阅读(83) 评论(0) 推荐(2) 编辑
摘要: 比赛链接 A 题解 知识点:模拟。 显然。 (用char输入到一半直接给答案跳出,WA了两小时,无话可说。 时间复杂度 $O(1)$ 空间复杂度 $O(1)$ 代码 #include <bits/stdc++.h> #define ll long long using namespace std; 阅读全文
posted @ 2023-01-17 22:08 空白菌 阅读(41) 评论(0) 推荐(1) 编辑
摘要: 比赛链接 A 题意 设计一条线路要贴着6个墙面走,从 $(a,b)$ 到 $(f,g)$ ,线路长度最短。 题解 知识点:模拟。 分类取最短即可。 时间复杂度 $O(1)$ 空间复杂度 $O(1)$ 代码 #include <bits/stdc++.h> #define ll long long u 阅读全文
posted @ 2023-01-17 01:13 空白菌 阅读(158) 评论(4) 推荐(1) 编辑
摘要: 同余 带余数除法 带余数除法的定义与基本性质 定义 对于整数 $a,b$ ,一定存在整数 $q,r$ 满足 $a = bq + r$ ,其中 $r$ 与 $a$ 同号且 $|r| \in [0,b)$ ,称 $q$ 为 $a$ 除以 $b$ 的商, $r$ 为 $a$ 除以 $b$ 的余数。 通常我 阅读全文
posted @ 2023-01-14 01:22 空白菌 阅读(39) 评论(0) 推荐(0) 编辑
摘要: 整除 本数论笔记中,不加说明的数,默认以其涉及的各运算的最大可行范围的交集为准。 整除的定义与基本性质 定义 设 $a,b \in \Z$ ,若 $b$ 除以 $a$ 余数为 $0$ ,则称 $a$ 整除 $b$ ,记为 $a \mid b$ 。 设 $a,b,c \in \Z$ 。 性质1 $a 阅读全文
posted @ 2023-01-14 01:21 空白菌 阅读(51) 评论(0) 推荐(0) 编辑
http://www.vxiaotou.com