X03 三班 笔记 超全 @AC君 求置
2024-07-30 17:15:10
发布于：浙江
159阅读
0回复
0点赞
借了同学20%的内容
一、认识STL（初赛知识）
C++标准库的一部分，用于实现数据类型算法。
STL容器属于一种数据类型，用于存储。
常见的容器有map、set、list、queue、vector、stack等。
二、map容器（T20416.计数员、T20417.幸运数对、T20421.密文搜索）
map是一种关联容器用于存储映射关系，可用多种数据类型表示其下标。
每个下标是唯一的，可用于用键查找值的场景。（键即下标）
如果键不存在，会自动扩展一个空间；若已存在，则会更换数值。
map可开辟无数个空间，不会造成空间浪费。
map会按照其下标字典序进行自动排序，与插入顺序无关。（从小到大）
头文件：#include<map>
定义：map<键类型,值类型> 容器名;
存值：容器名[下标（键）] = 值;
查值：容器名[下标（键）]
使用迭代器访问map时，.first是键，.second是值
获取首元素：(*it).first
获取尾元素：(*it).second
插入元素：容器名.insert(插入内容)
删除元素：容器名.erase(删除内容)
查找空间数量：容器名.size()
清空元素：容器名.clear()
判断是否为空：容器名.empty()
查找迭代器是否存在：容器名.find(查找内容)
三、迭代器（T20416.计数员、T20418.宝物管理）
提供一种统一的方式来访问容器中元素的方式，STL大多容器都支持迭代器。
it最初为一个地址，需使用*进行解析，迭代器可用auto来替换。
auto可将it直接变成容器里的实际数据。
定义：容器定义::iterator 迭代器名;
查找首元素：it.begin()
查找尾元素：it.end()-1
创建：for(it = 容器名.begin();it != 容器名.end();it++)
auto用法：for(auto it : 容器名)
四、set容器（T20418.宝物管理、T20419.明明的随机数、T20422.复制）
set是一种关联容器，是一个有序、不允许重复元素的容器。（可自动去重并排序）
set也会按照其下标字典序进行自动排序。（从小到大，结构体亦此）
set也可以使用迭代器（auto）进行遍历。
使用数值作为删除依据的时间复杂度为O(logn)，迭代器删除依据的时间复杂度为O(1)。
头文件：#include<set>
定义：set<数据类型> 容器名;
插入元素：容器名.insert(插入内容)
删除元素：容器名.erase(删除内容)
查找空间数量：容器名.size()
清空元素：容器名.clear()
判断是否为空：容器名.empty()
查找迭代器是否存在：容器名.find(查找内容)
五、vector容器（T20420.输出所有约数、T20423.出边的排序）
vector是一种可以自动扩容的STL容器，与数组相似。（最多可存放1e9个元素）
vector内所有值的初始值都为0。
当加入元素时，vector会自动将元素加入下标0的位置。
push_back()是从后往前压入vector容器的。
初始值会将vector中所有值变为该值。
头文件：#include<vector>
普通定义：vector<数据类型> 容器名;
初始化空间定义：vector<数据类型> 容器名(空间大小);
初始值定义：vector<数据类型> 容器名(空间大小,初始值);
查找下标值：容器名[下标]
插入元素：容器名.push_back(插入内容)
第一个元素：容器名.front()
最后一个元素：容器名.back()
找空间数量：容器名字.size()
调整大小：容器名.resize(调整后的大小)
预分配内存：容器名.reserve(预分配的内存)
获取首元素：容器名.first()
获取尾元素：容器名.end()
普通数组遍历：for(int i = 1;i <= 容器名.size();i++)
迭代器遍历：for(auto i : 容器名)
六、priority_queue容器（T20422.复制）
优先队列是一种容器适配器，每次访问的是具有最高优先级的元素。
与队列一样，队头出队，对位入队，但会维护优先级。
排序规则有greater（从小到大）和less（从大到小）。
普通定义：priority_queue<数据类型> 容器名;
自定义定义：priority_queue<数据类型,vector<int>,排序规则<int>>
删除最高级：容器名.pop()
添加元素：容器名.push()
查找队头元素：容器名.top()
判断是否为空：容器名.empty()
----------------------------------------Day2下午：高精度算法-----------------------------------------
一、高精度算法（T20451.高精度加法、T20452.高精度减法、T19485.高精度乘法...）
指当我们要计算的数字无法使用基础类型存储时的计算方法，一般数字很大。（模拟）
我们常将数位分离，并用字符串数组string来倒序存储数据。（除法除外）
高精度算法中，0下标为个位、1下标为十位、2下标为百位，以此类推。
【使用字符串输入数字（加、减、乘）】
string s1,s2; cin >> s1 >> s2;
int l1 = s1.size(),l2 = s2.size();
【逆序存入数组（加、减、乘）】
int a[N],b[N];
for(int i = 0;i < l1;i++) a[i] = s1[l1 - i - 1] - '0';
for(int i = 0;i < l2;i++) b[i] = s2[l2 - i - 1] - '0';
二、高精度加法（T20451.高精度加法）
指模拟数学计算时，竖式计算加法的过程。（从高位往低位计算）
过程：1.储存数字；2.同位相加（考虑进位）；3.输出结果（去前导0）。
【同位相加】
int c[N];
int l = max(l1,l2);
for(int i = 0;i < l;i++){
c[i] += a[i] + b[i];
【进位】
if(c[i] >= 10){
c[i] -= 10;
c[i + 1]++;
}
}
【去除前导0】
while(c[l] == 0) l--;
【逆序输出】
for(int i = l;i >= 0;i--) cout << c[i];
三、高精度减法（T20452.高精度减法）
指模拟数学计算时，竖式计算减法的过程。（从高位往低位计算）
过程：1.储存数字（判断符号）；2.同位相减（考虑借位）；3.输出结果（去前导0）。
【判断符号】
if(s1.size() == s2.size()){
if(s2 > s1){
cout << "-";
swap(s1,s2);
}
}else{
if(s1.size() < s2.size()){
cout << "-";
swap(s1,s2);
}
}
【同位相减】
int c[N];
int l = max(l1,l2);
for(int i = 0;i < l;i++){
c[i] += a[i] - b[i];
【借位】
if(c[i] < 0){
a[i + 1]--;
c[i] += 10;
}
}
【去除前导0】
while(c[l] == 0) l--;
【逆序输出】
for(int i = l;i >= 0;i--) cout << c[i];
四、高精度乘法（T20448.高精度乘低精度、T19485.高精度乘法）
指模拟数学计算时，竖式计算乘法的过程。（从高位往低位计算）
高精乘分为高精乘高精和低精乘低精。（常为高精乘高精）
过程：1.储存数字；2.同位相乘（考虑进位）；3.输出结果（去前导0）。
int c[N];
【枚举数字a】
for(int i = 0;i < l1;i++){
【枚举数字b】
for(int j = 0;j < l2;j++){
c[i + j] = a[i] * b[j];
【进位】
if(c[i + j] >= 10){
c[i + j + 1] += c[i + j] / 10;
c[i + j] %= 10;
}
}
}
【逆序输出】
int l = l1 + l2;
while(c[l] == 0) l--;
for(int i = l;i >= 0;i--) cout << c[i];
五、高精度除法（T20450.高精度除法）
指模拟数学计算时，竖式计算除法的过程。（从高位往低位计算）
当除数或被除数可以用基础类型储存时，可将其作为整体进行计算。
过程：1.储存数字；2.同位相除（考虑借位）；3.输出结果（去前导0）。
高精除不需要逆序存储。（不需要数位对齐）
int a[100005],b,c[100005];
【正序存储】
int l = s1.size();
for(int i = 0;i < l;i++) a[i] = s1[i] - '0';
【保存余数（当前可以除的数）】
long long t = 0;
【从高往低除】
for(int i = 0;i < l;i++){
t = t * 10 + a[i];
【合并余数与后一位】
if(t >= b){
c[i] = t / b;
t %= b;
}
}
【正序输出】
int le = 0;
while(c[le] == 0 && le <= l) le++;
for(int i = le;i < l;i++) cout << c[i];
----------------------------------------Day3下午：算法基础-----------------------------------------
一、双指针（T20459.双指针1、T20458.双指针2）
双指针是指利用两个游标的方式，在序列上进行维护。（贪心、二分均利用此方法）
双指针不属于一种算法，而是一种以两个变量进行框定区间的思路。
二、差分（T19465.区间修改模板题）
差分是前缀和的逆运算，从后往前进行序列的分割，并求两个相邻元素的差值。
对于某个数组a，存在差分数组d，使得d的前缀和，可以获得a。
当在差分位置i的d[i]增加c时，其对应的原数据在i位置的a[i]也增加c。
区间修改问题是指对序列[L,R]区间上的每个元素都增加一个c。
d[i] = a[i] - a[i - 1]
a[i] + c = d[i] + c
三、倍增（T20457.RMQ、T20460.积木大赛）
即成倍增加，一般用于处理数据很大不能使用枚举解决的问题。
ST稀疏表采用倍增的思想处理RMQ问题。（每查询一次，时间复杂度为O(1)；最终时间复杂度为O(nlogn)）
建表基础思想：设F[i][j]表示区间[i,i + 2^j - 1]区间的最值，区间长度为2^j。
根据倍增思想：长度为2j的区间可以被分为两个长度为2^j-1的子区间。递推公式：F[i][j] = max(F[i][j - 1],F[i + 2^j-1][j - 1])。
ST创建：若数组长度为n，则有2^k ≤ n < 2^k+1，那么ST表长度为k=floor(log2(n))。
ST查询：查询[L,R]区间的最值，区间长度k=floor(log2(R - L + 1))。查询以L为起点的长度2k，以R为终点的长度2^k，两个区间最值。
----------------------------------------Day4下午：排序进阶-----------------------------------------
一、分治（[NOIP2011 普及组] 瑞士轮）
对于一个规模为N的问题分解为M个规模较小的子问题。
该问题的规模缩小到一定的程度就可以容易的解决。
该问题可以分解为若干个规模较小的相同问题。
利用该问题分解出的子问题的解可以合并为总问题的解。
子问题的解相互独立，不会相同。
快速排序等使用了分治思想。
二、快速排序（T20472.【快速排序】升序）
利用分治思想，可以迅速将数列变得有序。
从序列中任选一个元素，设为x，x为基准值。（一般选择第一个元素）
调整位置，将x的左边全部小于x，x的右边全部大于x。
时间复杂度：最好情况O(nlogn)，最坏情况O(n)。（不具有稳定性）
【停止】
if(l >= r) return;
int i = l,j = r;
while(i != j){
【j向i】
while(j > i && a[j] >= a[l]) j--;
【i向j】
while(i < j && a[i] <= a[l]) i++;
【交换i,j】
swap(a[i],a[j]);
}
swap(a[i],a[l]);
【左半部分】
qs(l,i - 1);
【右半部分】
qs(i + 1,r);
三、归并排序（T20468.【归并排序】划分、T20467.【归并排序】合并…）
先划分，多次将一个数列分为两个部分。（根据中间值（(l+r)/2）分为两部分）
再合并，将划分后排序后的结果整合后输出。
时间复杂度：最好情况O(nlogn)，最坏情况O(n)。（不具有稳定性）
【划分】
【停止】
if(l >= r) return ;
【确定中间值】
int mid = l + r >> 1;
cout << "[";
【确定左半部分】
for(int i = l;i <= mid;i++) cout << a[i] << " ";
cout << "],[";
【确定右边部分】
for(int i = mid + 1;i <= r;i++) cout << a[i] << " ";
cout << "]" << endl;
【继续划分左边】
ms(l,mid);
【继续划分右边】
ms(mid + 1,r);
【合并】
【a,b序号】
int i = 1,j = 1;
【当前数字的排序】
int id = 1;
while(i <= n && j <= m){
【a[i]序号增加】
if(a[i] <= b[j]) c[id++] = a[i++];
【b[j]序号增加】
else c[id++] = b[j++];
}
【最后处理】
while(i <= n) c[id++] = a[i++];
while(j <= m) c[id++] = b[j++];
ST:
F[i][j] 表示区间 [i,i+2^(j-1)] 区间的差值 区间长度为2^j
F[i][j] = max(F[i][j-1],F[i+2^(j-1)][j-1])
区间最值 F[i][j] 区间长度 2^j
区间最值 F[i][j-1] 区间长度 2^(j-1)
a[i] ... a[i+2^(j-1)-1] a[i+2^(j-1)] ... a[i+2^(-1)] ...
区间最值 F[i+2^(j-1)][j-1] 区间长度 2^(j-1)
void St_create() {
for (int i = 1;i <= n;i ++) F[i][0] = a[i];
int k = log2(n);
for (int j = 1;i <= k;j ++) {
for (int i = 1;i <= n;i ++) {
F[i][j] = max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
F[i][j] = min(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
}
}
}
k = florr(log2(n));
#include <bits/stdc++.h>
using namespace std;
int mx_f[500005][30];
int mi_f[500005][30];
int n,q,a[1000005];
void createmax() {
for (int i = 1;i <= n;i ++) mx_f[i][0] = a[i];
int k = log2(n); // 取q的最大值
for (int j = 1;j <= k;j ++) {
for (int i = 1;i <= n - (1 << j) + 1;i ++) {
mx_f[i][j] = min(mx_f[i][j-1],mx_f[i + (1 << j - 1)][k]);
}
}
}
void createmin() {
for (int i = 1;i <= n;i ++) mi_f[i][0] = a[i];
int k = log2(n); // 取q的最大值
for (int j = 1;j <= k;j ++) {
for (int i = 1;i <= n - (1 << j) + 1;i ++) {
mi_f[i][j] = min(mi_f[i][j-1],mi_f[i + (1 << j - 1)][k]);
}
}
}
int Queue(int l,int r) {
// 最大值与最小值返回差值
int k = log2(r - l + 1);
int mx = max(mx_f[l][k],mx_f[r - (l << k) + 1][k]);
int mi = min(mi_f[l][k],mi_f[r - (l << k) + 1][k]);
return mx - mi;
}
int main() {
cin >> n >> q;
for (int i = 1;i <= n;i ++) cin >> a[i];
createmax();
createmin();
while (q --) {
int l,r;
cin >> l >> r;
cout << Queue(l,r) << "\n";
}
return 0;
}
完全二叉树 :
前序: 根左右
中序: 左根右
后序: 左右根
除第k层外其他的结点总数达最大值，且k层结点数小于等于2^(k-1)并靠左
侧连续 称为完全二叉树
n为奇数时 完全二叉树中没有度为1的结点 此时 n = n0 + n2;
n为偶数时 完全二叉树中只有一个度为1的结点 此时 n = n0 + 1 + n2;
具有n(n >= 0) floor(log2(n)) + 1;
n-3+1
log = 2
2
左孩子 编号2*i (2 * i <= n);
右孩子 标号2*i+1 (2*i+1 <= n);
1
/ \
2 3
/ \ /
4 5 6
DataType tree[N];
tree[i] , tree[2 * i] , tree[2 * i + 1];
//父结点 左孩子 右孩子
与根节点的通路叫做路径
第L层结点到根节点的路径长度为L-1;
层数 路径长度 L-1
1 0 9
2 1 / \
3 2 6 3
^ / \
| 2*1=2-> 1 5
二叉搜索树:
Binary Search Tree -> BST 二叉搜索树 -> 二分搜索树 log2(n); o(n)
左子树上所有结点的值都小于它的根节点(若左子树不为空)
右子树上所有的结点的值都大于它的根节点(右子树不为空)
他的左右结子都是二叉搜索树
拓扑排序:（英语:Topological sorting),拓扑排序要解释的问题给一个有向无环图(DAG:边是有向的 没有形成成闭环)的所有节点排序
AVO 网: 顶点表示活动 有向边表示活动之间的优先制关系 (u,v) 表示活动u必须先于v进行 称这种有向图为顶点表示后动的网 简称
AOV 网 AVO网同时也是有向无环图(DVA)
动态规划:
是一种表格处理法 或者记忆递归法 在对问题求解时 通过把原问题分解为相对简单的
子问题的方式 求解复杂问题的一种方法
归并排序 快速排序 (分治) 大问题拆解成小问题 good() n -> 小问题
1 2 3 4 5 6 7 8 9 子问题独立
分治思想 ————- ———— 让原本的问题差分成答案时
---------> l mid r (l + r) >> 1; 差分
1.确定状态(读题);
2.划分阶段(规划);
3.确定转移方程(动态);
a[i] = min(a[i-1],min(a[i-5],a[i-11]))+1;
区间DP属于线段DP的一种 以区间长度作为DP的阶段 以区间的左右作为端点作为
状态的维度 一个状态通常由被他包含且比它更小的区间状态转移而来
背包问题 :
1.状态定义(一般基于经验 基于一些灵感)
2.状态转方程 (基于给出的理由)
走楼梯 dp[i]: 走到第i层的时候做那些动作
跨一步? 或者 跨两步
dp[i+1] += dp[i];
dp[i+2] += dp[i];
dp[i-1][j-w[i]]+v[i];
背包 0 1 2 3 4 5 6 7 8 9 10
(2,1) 0 0 1 1 1 1 1 1 1 1 1
(3,3) 0 0 1 3 3 4 4 4 4 4 4
(4,5) 0 1 3 5 5 6 8 8 8 9 9
(7,9) 0 0 1 3 5 5 6 9 9 10 12
f(3-1,5-4) + 5;
动态dp : 一般指将动态规划算法用于数组或者字符串上
进行相关具体问题的求解 当题目求解以下内容时 可以
考虑用序列相关的DP
1.给定数组 求最长/最大/的某种值
2.给定两个字符串 求最长/最大的某种值
此外 在使用序列相关DP的时候 需要注意到 这是一类动态规划
所以需要满足动态规划的三种重要条件
num 1 7 3 5 9 4 8 s1 c a d b c a h s2 a b v c a
求解: 对于数组相关的问题 其状态 通常是一维 类似的
我们也可以可以定义状态dp[i]记录数组的前i个数的最优值
对于 字符串相关的问题 通常我们需要定义一个二维状态dp[i][j]
记录 两个字符串s1的前i个字符s2前面j个字符之间最优值
子序列:子序列指的是数列中不一定连续但先后顺序一致的n个
数字 既可以去掉数列中的部分数字 但不可改变其先后顺序
确定状态 划分阶段 确定状态转移方程
dp[i] 来作为某个以下表开头的上升子序列
1 2 3 4 5
| —————|
dp[1] dp[2] dp[3] d[4] dp[5]
5 4 3 2 1
for (int i = 1;i <= n;i ++) {
last = i+1 //最后一个字符;
for (int j = i+1;j <= n;j ++) {
if (a[i] < a[j]) {
dp[i] += 1; <- but It "枚举" O(n^2);
last = dp[j]; <- NOT good 动态规划 !!!
}
}
}
正解 : dp[1] = 1 dp[2] = 2;
if (dp[1] < dp[i]) dp[i] += dp[1];
dp[1] =1;
dp[2] =2;
dp[3] = max(dp[1],dp[2]) if -> a[1] < a[2] a[2] < a[3]
dp[i][j] = dp[i-1][j-1]+1;
if (a[i] != b[i]) dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
树 :
const int N = 10;
struct Node {
int data;
vector <int> child;
}tree[N];
struct Node {
int v,w;
};
vector <Node> G[110];
G[1].push_back({2,3});
G[2].push_back({4,3});
for (int j = 0;j < G[1].size();j ++) {
cout << G[1][j].w << " ";
}
表达式树是一种特殊的树 它的非
叶子节点是操作符 叶节点是操作数
钞票问题 https://www.acgo.cn/problemset/info/20508?homeworkId=2787&teamCode=1768162775202656256
#include<iostream>
using namespace std;
const int MAXN = 2e6+5;
long long a[MAXN]={0,1,2,3,4,1,2,3,4,5,2},n,ans;
int main() {
cin >> n;
for(int i = 2; i <= n; i ++) {
if(i >= 11) {
ans= min(a[i-11],min(a[i-5],a[i-1]));
ans++;
a[i]=ans;
}
}
cout<<a[n];
return 0;
}
最大公因数 :
#include <bits/stdc++.h>
using namespace std;
int main() {
int x,y;
cin >> x >> y;
cout << __gcd(x,y) << endl;
return 0;
}
数字三角形 : https://www.acgo.cn/problemset/info/20509?homeworkId=2787&teamCode=1768162775202656256
#include<bits/stdc++.h>
using namespace std;
int a[100][100],dp[100][100];
int main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
cin>>a[i][j];
}
}
for(int i=n; i>=1; i--) {
for(int j=1; j<=n; j++) {
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
}
}
cout<<dp[1][1];
return 0;
}
打家劫舍: https://www.acgo.cn/problemset/info/20512?homeworkId=2787&teamCode=1768162775202656256
#include <iostream>
using namespace std;
long long n,a[10000005],maxx=-1,dp[1000005];
int main() {
cin >> n ;
for (int i = 1;i <= n;i ++) {
cin >> a[i];
}
dp[1] = a[1];
dp[2] = a[2];
for(int i = 3;i<=n;i++){
dp[i] = max(dp[i-2],dp[i-3])+a[i];
}
for (int i = 1;i <= n;i ++) {
maxx = max(maxx,dp[i]);
}
cout <<maxx;
return 0;
}
石子合并 https://www.acgo.cn/problemset/info/20513?homeworkId=2787&teamCode=1768162775202656256
#include <bits/stdc++.h>
using namespace std;
int a[305],dp[305][305],s[305];
int main() {
int n;
cin >> n;
for (int i = 1;i <= 300;i ++) {
for (int j = 1;j <= 300;j ++) {
dp[i][j] = 1e9+7;
}
}
for (int i = 1;i <= n;i ++) {
cin >> a[i];
s[i] = s[i-1] + a[i];
dp[i][i] = 0;
//顶点i到顶点i的合并权值为0
}
for (int i = 2;i <= n;i ++) {
// 设定当前合并的区间范围长度
for (int j = 1;j <= n - i + 1;j ++) {
// 枚举范围的起点设置为i
int k = j + i - 1;
// k为当前合并范围的终点
for (int l = j;l <= k - 1;l ++) {
// l为分割点 枚举所有可以分割的顶点
dp[j][k] = min(dp[j][k],dp[j][l]+dp[l+1][k]+s[k]-s[j - 1]);
}
}
}
cout <<dp[1][n];
}
方格取数1 https://www.acgo.cn/problemset/info/20510?homeworkId=2787&teamCode=1768162775202656256
#include<bits/stdc++.h>
using namespace std;
int dp[100][100],a[100][100] = {};
int main(){
int n,m;
cin>>n>>m;
int x,y,z;
while(m--){
cin>>x>>y>>z;
a[x][y] = z;
}
dp[1][1] = a[1][1];
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
dp[i][j] = max(dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j]);
}
}
cout<<dp[n][n];
return 0;
}
传球游戏 https://www.acgo.cn/problemset/info/20514?homeworkId=2787&teamCode=1768162775202656256
#include <bits/stdc++.h>
using namespace std;
int dp[1010][1010],m,n;
int main() {
cin>>m>>n;
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
dp[i][j]=dp[i-1][(j+m-1)%m]+dp[i-1][(j+1)%m];
}
}
cout<<dp[n][0];
return 0;
}
01背包 https://www.acgo.cn/problemset/info/20520?homeworkId=2829&teamCode=1768162775202656256
#include <iostream>
using namespace std;
int c,n,dp[205][205],w[205],v[205];
int main() {
cin >> c >> n;
for (int i = 1;i <= n;i ++) {
cin >> w[i] >> v[i];
}
for (int i = 1;i <= n;i ++) {
for (int j = 1;j <= c;j ++) {
if (j < w[i]) {
dp[i][j] = dp[i-1][j];
}else {
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
cout << dp[n][c];
return 0;
}
完全背包 https://www.acgo.cn/problemset/info/20521?homeworkId=2829&teamCode=1768162775202656256
#include <iostream>
using namespace std;
int m,n,dp[205],w[205],v[205];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++) {
cin >> w[i] >> v[i];
}
for (int i = 1;i <= n;i ++) {
for (int j = w[i];j <= m;j ++) {
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout << "max=" << dp[m];
return 0;
}
完全背包优化（时间优化） https://www.acgo.cn/problemset/info/26081?homeworkId=2829&teamCode=1768162775202656256
#include <iostream>
using namespace std;
int c,n,dp[205][205],w[205],v[205];
int main() {
cin >> c >> n;
for (int i = 1;i <= n;i ++) {
cin >> w[i];
v[i]=w[i];
}
for (int i = 1;i <= n;i ++) {
for (int j = 1;j <= c;j ++) {
if (j - w[i] >= 0) {
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}else {
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[n][c];
return 0;
}
多重背包 https://www.acgo.cn/problemset/info/20108?homeworkId=2829&teamCode=1768162775202656256
#include<bits/stdc++.h>
using namespace std;
int v[1005],w[1005],c[1005],n,m,dp[1005];
int main(){
cin >> m >> n;
for(int i = 1;i <= n;i ++){
cin >> w[i] >> v[i] >> c[i];
}
for(int i = 1;i <= n;i ++){
for(int j = m;j >= 1;j -- ){
for(int k = 1;k <= c[i];k ++){
if(k * w[i] <= j){
dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
}
}
}
}
cout<<dp[m];
return 0;
}
[NOIP2001 普及组] 装箱问题 https://www.acgo.cn/problemset/info/20526?homeworkId=2829&teamCode=1768162775202656256
#include <iostream>
using namespace std;
int c,n,dp[35][20005],w[205],v[205];
int main() {
cin >> c >> n;
for (int i = 1;i <= n;i ++) {
cin >> w[i];
v[i]=w[i];
}
for (int i = 1;i <= n;i ++) {
for (int j = 1;j <= c;j ++) {
if (j - w[i] >= 0) {
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}else {
dp[i][j] = dp[i-1][j];
}
}
}
cout << c-dp[n][c];
return 0;
}
云 https://www.acgo.cn/problemset/info/26080?homeworkId=2829&teamCode=1768162775202656256
#include <iostream>
using namespace std;
long long dp[101][100001],w[1001],v[1001];
int main() {
for (int i = 0;i <= 100;i ++) {
for (int j = 0 ;j <= 100000;j ++) {
dp[i][j] = 2e18;
}
}
int n,c;
cin >> n >> c;
for (int i = 1;i <= n;i ++) {
cin >> w[i] >> v[i];
}
dp[0][0] = 0;
for (int i = 1;i <= n;i ++) {
for (int j = 0;j <= 100000;j ++) {
if (v[i] > j) {
dp[i][j] = min(dp[i][j],dp[i-1][j]);
continue;
}
dp[i][j] = min(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
}
}
for (int i = 100000;i >= 0;i --) {
if (dp[n][i] <= c) {
cout << i << '\n';
return 0;
}
}
return 0;
}
01背包(优化) https://www.acgo.cn/problemset/info/20523?homeworkId=2829&teamCode=1768162775202656256
#include <iostream>
using namespace std;
int c,n,dp[30005],w[30005],v[30005];
int main() {
cin >> c >> n;
for (int i = 1; i <= n; i ++) {
cin >> w[i] >> v[i];
}
for (int i = 1;i <= n;i ++) {
for (int j = c;j >= w[i];j --) {
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout << dp[c];
return 0;
}
完全背包优化（空间优化） https://www.acgo.cn/problemset/info/26082?homeworkId=2829&teamCode=1768162775202656256
#include<bits/stdc++.h>
using namespace std;
long long w[30005],v[300005];
long long dp[205][30005];
int main(){
int n,c;
cin>>c>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=c;j++){
if(j<w[i]){
dp[i][j]=dp[i-1][j];
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
}
}
}
cout<<dp[n][c];
return 0;
}
#######竞赛题目 只记录我AC的题目 仅OI 太简单的不写了
分裂可乐 https://www.acgo.cn/problemset/info/20486?teamCode=1768162775202656256
#include <iostream>
#include <queue>
using namespace std;
int main() {
freopen("cola.in","r",stdin);
freopen("cola.out","w",stdout);
queue<string> q;
q.push("A");
q.push("B");
q.push("C");
q.push("D");
q.push("E");
int n;
cin >> n;
string s="";
for (int i = 1;i <= n;i ++) {
s = q.front();
q.pop();
q.push(s);
q.push(s);
}
cout << q.back();
fclose(stdin);
fclose(stdout);
}
方程 https://www.acgo.cn/problemset/info/20485?teamCode=1768162775202656256
#include <iostream>
#include <cmath>
using namespace std;
double ans=0;
int main() {
freopen("equation.in","r",stdin);
freopen("equation.out","w",stdout);
long long a,b,c,d;
cin >> a >> b >> c;
if (a == 0) {
if (b == 0) {
if (c == 0) {
cout <<-1;
return 0;
}cout << 0;
return 0;
}ans=1.0*(-c)/b;
cout << 1 << "\n";
printf("%.10lf",ans);
}else {
d=b*b-4*a*c;
if (d < 0) {
cout << 0;
return 0;
}else if (d == 0){
cout << 1 << "\n";
ans=1.0*(-b)/(2*a);
printf("%.10lf",ans);
} else {
cout << 2 << "\n";
ans=1.0*(-b-sqrt(d))/(2*a);
printf("%.10lf\n",ans);
ans=1.0*(-b+sqrt(d))/(2*a);
printf("%.10lf",ans);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
农场 https://www.acgo.cn/problemset/info/20487?teamCode=1768162775202656256
#include <bits/stdc++.h>
using namespace std;
int main(){
freopen("farm.in","r",stdin);
freopen("farm.out","w",stdout);
int n,x,sum,a[105],cnt=0,compass=1;
cin >> n >> x;
for(int i = 1;i <= n;i ++){
cin>>a[i];
int ans = n - i + 1;
a[i] = a[i] * ans;
}
sort(a+1,a+n+1);
while(compass <= n){
if(x < sum + a[compass]) break;
sum = sum + a[compass ++];
cnt ++;
}
cout << cnt;
fclose(stdin);
fclose(stdout);
return 0;
}
纸带 https://www.acgo.cn/problemset/info/20488?teamCode=1768162775202656256
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("tape.in","r",stdin);
freopen("tape.out","w",stdout);
int n,x,cnt=0,a[100005];
cin >> n;
for (int i = 1;i <= n;i ++) {
cin >> x;
a[i]=a[i-1]+x;
}
for (int i = 1;i < n;i ++) if (a[i] == a[n] - a[i]) cnt ++;
cout << cnt;
fclose(stdin);
fclose(stdout);
return 0;
}
对手 https://www.acgo.cn/problemset/info/20532?teamCode=1768162775202656256
#include <iostream>
using namespace std;
int main() {
freopen("rival.in","r",stdin);
freopen("rival.out","w",stdout);
int n,d;
cin >> n >> d;
int ans=0,cnt=0;
for (int i = 0;i < d;i ++) {
string s;
cin >> s;
bool flag=0;
for (int j = 0;j < s.size();j ++) {
if (s[j] == '0') {
flag = 1;
}
}
if (flag) {
cnt ++ ;
ans = max(ans,cnt);
}else {
cnt=0;
}
}
cout << ans;
fclose(stdin);
fclose(stdout);
return 0;
}
正解 中缀转前缀:
#include<bits/stdc++.h>
using namespace std;
char s[109],ans[109];
int level(char s){
if(s=='+'||s=='-')return 1;//加减优先级更低
else if(s=='*'||s=='/')return 2;
}
void infix_to_postfix(char str[]){
stack<char>s;
int idx=0;
for(int i=0;str[i]!='\0';i++){
if(str[i]>='a'&&str[i]<='z'){
ans[idx++]=str[i];
}else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'){//碰到运算符
if(s.empty()||level(str[i])>level(s.top())){//若符合栈为空 或 当前符合的优先级>栈顶符合的优先级则直接进栈
s.push(str[i]);
}else{
while(!s.empty()&&level(s.top())>=level(str[i])){//先判空再用s.top()不然会报错
if(s.top()=='('){
break;
}
ans[idx++]=s.top();
s.pop();
}
s.push(str[i]);//最后把扫描到的字符压入栈中
}
}else{//碰到界线符
if(str[i]=='(')s.push(str[i]);
else if(str[i]==')'){
while(s.top()!='('){
ans[idx++]=s.top();
s.pop();
}
s.pop();//左括号也出栈
}
}
}
while(!s.empty()){//将剩余的运算符弹出
ans[idx++]=s.top();
s.pop();
}
}
int main(){
cin>>s;
infix_to_postfix(s);
return 0;
}
有帮助，赞一个