Iterfun's Blog

作者：yxc链接：https://www.acwing.com/blog/content/277/来源：AcWing y总的算法基础课 https://www.acwing.com/activity/content/11/ 搜索与图论树与图的存储树是一种特殊的图，与图的存储方式相同。对于无向图中的边ab，存储两条有向边a->b, b->a。因此我们可以只考虑有向图的存储。(1) 邻接矩阵：g[a][b] 存储边a->b(2) 邻接表： 123456789101112// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点int h[N], e[N], ne[N], idx;// 添加一条边a->bvoid add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}// 初始化idx = 0;memset(h, -1, sizeof h); 树与图的遍历时间复杂度 O(n+m), n表示点数，m表示边数(1) 深度优先遍历 —— 模板题 A ...

作者：yxc链接：https://www.acwing.com/blog/content/277/来源：AcWing y总的算法基础课 https://www.acwing.com/activity/content/11/ 数据结构单链表 —— 模板题 AcWing 826. 单链表 https://www.acwing.com/problem/content/828/ 123456789101112131415161718192021// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点int head, e[N], ne[N], idx;// 初始化void init(){ head = -1; idx = 0;}// 在链表头插入一个数avoid insert(int a){ e[idx] = a, ne[idx] = head, head = idx ++ ;}// 将头结点删除，需要保证头结点存在void remove(){ head = ne[hea ...

作者：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) { ...

你玩过“拉灯”游戏吗？ 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'; ...