Iterfun's Blog

作者：yxc链接：https://www.acwing.com/blog/content/277/来源：AcWing y总的算法基础课 https://www.acwing.com/activity/content/11/ 基础算法快速排序算法模板 —— AcWing 785. 快速排序 https://www.acwing.com/problem/content/787/ 12345678910111213void quick_sort(int q[], int l, int r){ if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort( ...

由数据范围反推算法复杂度以及算法内容一般ACM或笔试题的时间限制是 1秒/2秒。在这种情况下，C++代码的操作次数控制在 10^7 ~ 10^8 最佳。 在不同的数据范围下，代码的时间复杂度与算法的选择： n ≤ 30 ⇒ 指数级别dfs + 剪枝状态压缩dp n ≤ 100 ⇒ O(n³)FloydDP高斯消元 n ≤ 1000 ⇒ O(n²) / O(n²logn)DP二分朴素版Dijkstra朴素版PrimBellman-Ford n ≤ 10000 ⇒ O(n * √n)块状链表分块莫队 n ≤ 100000 ⇒ O(nlogn)各种sort线段树树状数组set/mapheap拓扑排序Dijkstra + heapPrim + heapKruskalspfa求凸包求半平面交二分CDQ分治整体二分后缀数组树链剖分动态树 n ≤ 10⁶ ⇒ O(n) / 常数较小的O(nlogn)算法单调队列hash双指针扫描并查集KMPAC自动机常数较小的O(nlogn)算法有：sort，树状数组，heap，Dijkstra，spfa n ≤ 10⁷ ⇒ ...

100 可以表示为带分数的形式：100=3+69258714 还可以表示为：100=82+3546197 注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。 类似这样的带分数，100 有 11 种表示法。 输入格式一个正整数。 输出格式输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。 数据范围1≤N<106 输入样例1：1100 输出样例1：111 输入样例2：1105 输出样例2：16 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 20;int n;bool st[N ...

从 1∼n这 n 个整数中随机选出 m 个，输出所有可能的选择方案。 输入格式两个整数 n, m 在同一行用空格隔开。 输出格式按照从小到大的顺序输出所有方案，每行 1 个。 首先，同一行内的数升序排列，相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。 数据范围n>0 ,0≤m≤n ,n+(n−m)≤25 输入样例：15 3 输出样例：123456789101 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 12345678910111213141516171819202122232425// 递归#include <iostream>using namespace std;int n, m;void dfs(int u, int sum, int state) { if (sum + n - u < m) return; if (sum == m) { ...

我忽然意识到自己忽视了总结与回顾的重要性，这是对精力很大的浪费。具体地来说，我多年以来收集的碎片化知识一次又一次地被遗忘了。 我花了相当可观的时间使用B站（刷沙雕视频）和知乎（读故事）。不可否认的是，在刷的过程中我收获了很多知识。这涉及到如何合理使用b站和知乎这种”干货和奶头乐并存的平台“——这一点不是本篇文章想反思的。如果无法合理地使用B站和知乎提升自己，我只需要刻意卸载它们并花更多时间去阅读。现在我想要反思的是：学习过程中没有及时整合与加工信息的问题。 我通常不舍得花时间记录和总结。我刷的视频和文章涉及了健身、营养学、编程、人文社科。它们通常成为我消遣的素材。在”刷“这个过程中，大脑分泌了多巴胺。另外，我体验到了积累知识的错觉。我大呼过瘾，加入收藏夹，清楚记忆，一气呵成。 出于缓解强迫症的目的与一点点求知欲，我常常刷类似于“力量训练的组数安排”、“力竭/不力竭的意义”、“神经募集能力“、”健身补剂科普“、”轻断食“、”日均摄入卡路里推荐值“、“100克鸡胸肉含有的精确蛋白质含量与人体对其吸收比率”等感兴趣的碎片知识，而很少记录与总结。结果是：无数次的遗忘。 我曾经做得很好 ...

你玩过“拉灯”游戏吗？ 25 盏灯排成一个 5×5 的方形。 每一个灯都有一个开关，游戏者可以改变它的状态。 每一步，游戏者可以改变某一个灯的状态。 游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。 下面这种状态 123451011101101101111000011011 在改变了最左上角的灯的状态后将变成： 123450111111101101111000011011 再改变它正中间的灯后状态将变成： 123450111111001110011010011011 给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。 输入格式第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。 以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。 每组数据描述了一个游戏的初始状态。 各组数据间用一个空行分隔。 输出格式一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 对于 ...

以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。 这个数列从第 3 项开始，每一项都等于前两项之和。 输入一个整数 N，请你输出这个序列的前 N 项。 输入格式一个整数 N。 输出格式在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。 数据范围0<N<46 输入样例：15 输出样例：10 1 1 2 3 1234567891011121314151617#include <cstring>#include <iostream>#include <algorithm>using namespace std;int main() { int n; cin >> n; int f[46]; f[1] = 0, f[2] = 1; for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; for (int i = 1; i <= n; i++) cout << f[i] &l ...

递归实现指数型枚举从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。 输入格式输入一个整数 n。 输出格式每行输出一种方案。 同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。 对于没有选任何数的方案，输出空行。 本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。 数据范围1≤n≤15 输入样例：13 输出样例：1234567322 311 31 21 2 3 难度：简单 时/空限制：5s / 256MB 总通过数：45400 总尝试数：70261 来源：《算法竞赛进阶指南》 算法标签 1234567891011121314151617181920212223242526272829303132333435#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 16;int n;in ...

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。 输入格式一个整数 n。 输出格式按照从小到大的顺序输出所有方案，每行 1 个。 首先，同一行相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。 数据范围1≤n≤9 输入样例：13 输出样例：1234561 2 31 3 22 1 32 3 13 1 23 2 1 123456789101112131415161718192021222324252627#include <iostream>#include <vector>using namespace std;int n;vector<int> path;void dfs(int u, int state) { if (u == n) { for (auto x : path) cout << x << ' '; cout << '\n'; ...

高精度计算有几种常见的类型： 两个很大的整数相加A, B的位数均小于等于10⁶ 两个很大的整数相减A, B的位数均小于等于10⁶ 一个很大的整数乘以一个比较小的整数A的位数小于等于10⁶，B的数值小于等于10⁹ 一个很大的整数除以一个比较小的整数A的位数小于等于10⁶，B的数值小于等于10⁹ 还有 两个很大的整数相乘 和 两个很大的整数相除 这两种情况，不过不常用，暂时不学了。 我们写数字习惯从高位开始写，但是模拟加减乘除时由于要做进位的操作，所以从低位开始存比较方便。即：数组第 0 位存个位，第 1 位存十位，第 2 位存百位······ 高精度加法C = A + B用变量 t 表示进位，要么是 1 要么是 0 。 123456789101112131415161718192021vector<int> add(vector<int> &A, vector<int> &B) { vector<int> C; // 和 int t = 0; // 1表示进位，0表示不进位 for ...