...

背包九讲 01背包问题 完全背包问题 多重背包问题 混合背包问题 二维费用的背包问题 分组背包问题 背包问题求方案数 求背包问题的方案 有依赖的背包问题 01背包问题1234567891011f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少。result = max{f[n][0~V]}f[i][j]:1. 不选第i个物品，f[i][j] = f[i - 1][j];2. 选第i个物品，f[i][j] = f[i - 1] [j - v[i]] + w[i];f[i][j] = max{1. 2.}f[0][0] = 0; 未优化版 1234567891011121314151617181920212223#include <iostream>using namespace std;const int N = 1010;int n, m;int f[N]; // f[i][j], j体积下前i个物品的最大价值 int v[N]; // 体积int w[N]; // 价值int main() { c ...

给定一个长度为 n 的数组 a1,a2,…,an。 现在，要将该数组从中间截断，得到三个非空子数组。 要求，三个子数组内各元素之和都相等。 请问，共有多少种不同的截断方法？ 输入格式第一行包含整数 n。 第二行包含 n 个整数 a1,a2,…,an。 输出格式输出一个整数，表示截断方法数量。 数据范围前六个测试点满足 1≤n≤10。所有测试点满足 1≤n≤10^5，−10000≤ai≤10000。 输入样例1：1241 2 3 3 输出样例1：11 输入样例2：1251 2 3 4 5 输出样例2：10 输入样例3：1220 0 输出样例3：10 1234567891011121314151617181920212223242526272829#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 100010;int n;int s[N];int main() { scanf("%d", &n); for (int i ...

机器人正在玩一个古老的基于 DOS 的游戏。 游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。 编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑高度为 H(i) 个单位。 起初，机器人在编号为 0 的建筑处。 每一步，它跳到下一个（右边）建筑。 假设机器人在第 k 个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。 如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1) 的能量值。 游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。 现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？ 输入格式第一行输入整数 N。 第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。 输出格式输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。 数据范围1≤N,H(i)≤10^5, 输入样例1：1253 4 3 2 4 输出样例1：14 输入样例2：1234 4 4 输出样例2：14 输入样例3：1231 6 4 输出样例3：13 ...

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102#include <bits/stdc++.h>using namespace std;// 判断质数bool ispr(int n) { if (n < 2) return 0; for (int i = 2; i <= n/i; i++) if (n % i == 0) return 0; return 1;}// 筛质数(埃筛)bool v[N]; // v存合数标记void pr(int n) { memset(v, 0, sizeof v); for (int i = 2; i <= ...

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。 对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。 如果数组中不存在该元素，则返回 -1 -1。 输入格式第一行包含整数 n 和 q，表示数组长度和询问个数。 第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。 接下来 q 行，每行包含一个整数 k，表示一个询问元素。 输出格式共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。 如果数组中不存在该元素，则返回 -1 -1。 数据范围1≤n≤1000001≤q≤100001≤k≤10000 输入样例：123456 31 2 2 3 3 4345 输出样例：1233 45 5-1 -1 123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>using namespace std;const int N = 5 + 1e5;int q[N];int n, m;int ma ...

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