【算法2-1】前缀和与差分 https://www.luogu.com.cn/training/200#problems P2671 [NOIP2015 普及组] 求和https://www.luogu.com.cn/problem/P2671枚举x，z复杂度为n²，会超时。用一下分组思想，把每个颜色分为一组，再在每个颜色中按奇偶分组，所以一共有2m组设一个分组里有k个数， 这个代码比较清楚。https://www.luogu.com.cn/blog/BlueHedgehog/p2671-qiu-hu-ti-xie P1115 最大子段和直接用前缀和会超时。 for(int i = ...

【数学1】基础数学问题 https://www.luogu.com.cn/training/117#problems P1469 找筷子我用map每次弹出有一个的长度也MLE P1017 [NOIP2000 提高组] 进制转换负数进制！！！商++相当于借位，类似a--，因为这里m为负数，所以借位是++。 P2822 [NOIP2016 提高组] 组合数问题要写出这道题，你需要掌握：组合数与杨辉三角的关系、前缀和 P2789 直线交点数有点绕，多想想 P3913 车的攻击数据量很大，要学会转换问题。这里应该题目给错了？数组开到1e6就能AC。 P2926 [USACO08DEC]Pattin...

https://www.luogu.com.cn/training/113#problems 【数据结构1-1】线性表 P3613 【深基15.例2】寄包柜 向量 https://www.luogu.com.cn/problem/P3613直接开a[N][N]数组， a[100005][100005]就肯定MLE 了，怎样设置数组才能节省内存呢？我们想到动态数组 vector 数组实现链表 P1160 队列安排要用链表第一次提交有部分未通过是因为可能有重复删除的数。所以要先判断是不是删过，加了判断之后AC了。 #include <bits/stdc++.h> using name...

【算法1-1】模拟与高精度 https://www.luogu.com.cn/training/106#problemsP1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Twohttps://www.luogu.com.cn/problem/P1518原本我是单纯的模拟，没有判断死循环即无解的情况。看了下面的分析，给t设置一个最大值，超过就无解。“看到题后，我们的第一反应是寻找环判重叠来算次数，但这样也太麻烦了，所以考虑更简洁的直接模拟： 由于只有10x10行的地图，因此牛和农夫最多只有400种情况（每个位置有4次，4方向各一次）由乘法原理可知，无论怎么走，最多都只能出...

【入门1】顺序结构 P1008 [NOIP1998 普及组] 三连击https://www.luogu.com.cn/problem/P1008模拟，枚举所有可能的a，输出满足条件的a，b，c。 #include <bits/stdc++.h> using namespace std; int main(){ int v; bool a[10];//ai表示第i个数已经用过了 for(int i = 123; i < 329; i++){ memset(a, 0, sizeof(a)); v = 0; ...

由数据范围反推算法复杂度以及算法内容https://www.acwing.com/blog/content/32/ 第七讲 时空复杂度分析https://www.acwing.com/blog/content/3398/ C++ 手动开O2优化https://blog.csdn.net/liyizhixl/article/details/77803291https://blog.csdn.net/Tony_Wang_JT/article/details/104444969#pragma GCC optimize(2)

https://www.acwing.com/video/39/ 区间问题 区间选点最大不相交区间数量和上一题等价区间分组区间覆盖 Huffman树 合并果子经典哈夫曼树的模型，每次合并重量最小的两堆果子即可。(贪心,哈夫曼树,堆,优先队列) O(nlogn)小根堆 priority_queue<int, vector<int>, greater<int>> heap;</int></int> 排序不等式 排队打水按从小到大排序，等待时间最少。 绝对值不等式 货仓选址最中间的位置为货仓选址。 推公式 耍杂技的牛

背包问题 01背包问题 每件物品最多只能用一次。 int n, m; int v[N], w[N]; int f[N]; int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i++){ for(int j = m; j >= v[i]; j--){ f[j] = max(f[j], f[j - v[i]] + w[i...

https://www.acwing.com/video/27/ 数论 https://zhuanlan.zhihu.com/p/35060143 质数 定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数。 （1）质数的判定————试除法 O(sqrt(n)) for循环的判定推荐用 i <= n / i；不用 i * i <= n 或者 i <= sqrt(n)。所以它的时间一定是sqrt(n) bool isPrime(int x){ if(x < 2) return false; for(int i = 2; i &lt...

DFS DFS算法是一一个递归算法，需要借助一个递归工作栈，故它的空间复杂度为O(N)。遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。 邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O(N),此时，总的时间复杂度为 O(N+E)。 邻接矩阵表示时，查找每个顶点的邻接点所需时间为 O(N)，要查找整个矩阵，故总的时间度为O(N^2) 。 void dfs(int k){ if(k == n){ for(int i = 0; i < n; i++){ printf(&quot...

https://www.acwing.com/activity/content/punch_the_clock/11/ 单链表 数组实现链表 #include <iostream> using namespace std; const int N = 1e5 + 10; // head 表示头结点的下标 // e[i] 表示节点i的值 // ne[i] 表示节点i的next指针是多少 // idx 存储当前已经用到了哪个点 int head, e[N], ne[N], idx; // 初始化 void init(){ head = -1; idx = 1; ...

https://codeforces.com/contest/1530AB题AC了 A - Binary Decimal #include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int N = 2e5 + 10; int t, n; int a[N]; int main(){ cin >> t; while(t--){ cin >> n...

https://codeforces.com/contest/1550 A. Find The Array 第十五分钟完成 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <math.h> #include <set> using namespace std; typedef ...

快速排序 时间复杂度O(nlogn)这里涉及到很多边界处理的问题，所以直接记住下面这个模板。使用quick_sort(q, 0, n-1)；实现从小到大排序。 void quick_sort(int q[], int l, int r){ if(l >= r) return; int k = q[l + r >> 1]; int i = l - 1, j = r + 1; while(i < j){ do i++; while(q[i] < k); do j--; while(q[j] > k)...