Acwing算法笔记
温馨提示：这篇文章已超过374天没有更新，请注意相关的内容是否还可用！
Acwing算法笔记
持续更新中…
（图片来源网络，侵删）
文章目录
- Acwing算法笔记
- 第一章
- 1.快排
- 2.归并排序
- 3.整数二分
- 4.差分
- c++库模版
- 二分的记忆方法
- 5.高精度
- 第四章：数论
- 1.判断素数
- 2.质因数分解
- 3.快速幂和快速幂求逆元
- 4.欧几里得定理和拓展欧几里得定理
- 第五章 STL
- 1.map
- 使用map模拟链表
- 2.unordered_map：
- 3.priority_queue:
- 第六章 dp
- 1.十一讲背包
- （1）01背包
- （2）完全背包
- （3）多重背包1
- （4）多重背包2
- （5）多重背包3
- （6）混合三种背包问题
- （7）分组背包问题
- （8）二维费用的背包问题
- （9）背包问题求方案数
- （10）背包问题求具体方案数
- （11）01背包装满背包的情况
第一章
1.快排
#include using namespace std; const int N = 1e5+10; int main() { int a[N]; int n; cin>>n; for (int i = 0; i >a[i]; } sort(a,a+n); for (int i = 0; i >k; check(k,n); } return 0; }4.差分
定义： 首先给定一个原数组a：a[1], a[2], a[3], a[n]；然后我们构造一个数组b ： b[1] ,b[2] , b[3], b[i];使得 a[i] = b[1] + b[2 ]+ b[3] +, + b[i]；也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。
一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。
https://www.acwing.com/problem/content/description/799/
#include #define int long long typedef long long ll; using namespace std; const int N = 2e5 + 10; const int mod = 998244353; void solve(){ int n,m; cin>>n>>m; vector a(n+1,0); for (int i = 1; i cin>a[i]; } vector b(n+10,0); for (int i = 1; i b[i] = a[i] - a[i-1]; } while(m--){ int l,r,c; cin>l>>r>>c; b[l]+=c; b[r+1] -= c; } int sum = 0; for (int i = 1; i a[i] = a[i-1] + b[i]; cout ios::sync_with_stdio(false); cin.tie(0); int t = 1; //cint; while(t--){ solve(); } return 0 ; } while (l > 1;//(加) if(q[mid] = 0, B >= 0 { vectorC; int t = 0; for (int i = 0; i >a>>b; vector A,B; for(int i = a.size() - 1;i >= 0;i --){ A.push_back(a[i]-'0'); } for(int i = b.size() - 1;i >= 0;i --){ B.push_back(b[i]-'0'); } auto C = add(A,B); for(int i = C.size() - 1; i >= 0;i --){ cout ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); int t = 1; //cin>t; while(t--){ solve(); } return 0 ; }高精度减法(https://www.acwing.com/problem/content/794/)
#include #define int long long typedef long long ll; using namespace std; const int N = 1e5 + 10; const int mod = 1e9 + 7; //首先判断A和B的大小 bool cmp(vector &A,vector &B){ if(A.size() != B.size()) return A.size() > B.size(); for (int i = A.size()-1; i >= 0; i -- ){ if(A[i] != B[i]){ return A[i] > B[i]; } } return true; // A和B相等 } vector sub(vector &A,vector &B) // C = A - B, A >= 0, B >= 0 { vector C; int t = 0; for (int i = 0; i 1 && C.back() == 0) C.pop_back(); //删除前导零 return C; } void solve(){ string a,b; cin>>a>>b; vector A,B; for(int i = a.size() - 1;i >= 0;i --){ A.push_back(a[i]-'0'); } for(int i = b.size() - 1;i >= 0;i --){ B.push_back(b[i]-'0'); } if(cmp(A,B)){ auto C = sub(A,B); for(int i = C.size() - 1; i >= 0;i --){ cout auto C = sub(B,A); cout cout ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); int t = 1; //cint; while(t--){ solve(); } return 0 ; }高精乘低精(https://www.acwing.com/activity/content/problem/content/827/)
#include #define int long long typedef long long ll; using namespace std; const int N = 1e5 + 10; const int mod = 1e9 + 7; vector mul(vector &A,int b) // C = A*b { vectorC; int t = 0; //进位 for (int i = 0; i 1 && C.back() == 0) C.pop_back(); //去除前导零 return C; } void solve(){ string a; int b; cin>>a>>b; vector A; for(int i = a.size() - 1;i >= 0;i --){ A.push_back(a[i]-'0'); } auto C = mul(A,b); for(int i = C.size() - 1; i >= 0;i --){ cout ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); int t = 1; //cin>t; while(t--){ solve(); } return 0 ; }高精度除法(https://www.acwing.com/problem/content/796/)
高精除以低精
#include #define int long long typedef long long ll; using namespace std; const int N = 1e5 + 10; const int mod = 1e9 + 7; vector div(vector &A,int b,int &r) // C = A/b ,r为余数 { vectorC; r = 0; //余数 for (int i = A.size()-1; i >= 0; i -- ){ r = r*10 + A[i]; C.push_back(r/b); r%=b; } reverse(C.begin(),C.end()); while(C.size()>1 && C.back() == 0) C.pop_back(); //去除前导零 return C; } void solve(){ string a; int b; cin>>a>>b; vector A; for(int i = a.size() - 1;i >= 0;i --){ A.push_back(a[i]-'0'); } int r; auto C = div(A,b,r); for(int i = C.size() - 1; i >= 0;i --){ cout ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); int t = 1; //cint; while(t--){ solve(); } return 0 ; } if(x >w[i]; } //dp[i]背包容量为i的最大价值 //需要注意的是一维度需要逆序更新，因为正序更新 //对于第i个，可能由i-2转移，却还是使用的i-1转移，所以逆序 for (int i = 1; i //枚举物品 for (int j = m; j = v[i]; --j) { //从大容积向小容积枚举，注意j小于v[i]就不必更新 dp[j] = max(dp[j],dp[j - v[i]] + w[i]); //更新最大价值 } } cout cinn>>m; for (int i = 1; i cin>v[i]>>w[i]; } //dp[i][j]代表i个物品，背包容量为j的最大价值 for (int i = 1; i //枚举容量,最大容量为m for (int j = 0; j //注意与01背包的差别，01背包是倒序 //优化可以去掉k层循环 dp[i][j] = dp[i-1][j]; if(j = v[i]){ dp[i][j] = max(dp[i][j],dp[i][j-v[i]] + w[i]);//注意与01背包的差别，01背包是与dp[i-1][j - v[i]] + w[i]比 } } } cout cinn>m; for (int i = 1; i cin>v[i]>>w[i]; } //dp[i]代表背包容量为i的最大价值 for (int i = 1; i //枚举容量,最大容量为m for (int j = v[i]; j //注意与01背包的差别，01背包是倒序 dp[j] = max(dp[j],dp[j - v[i]] + w[i]); //注意与01背包区分 } } cout //注意数组的大小不要开小了 int v,w,s; int t = 0; //跟新数组下标，把n个物品全都放到一个数组中 cinnm; while (n--){ cin>>v>>w>>s; while (s--){ a[++t] = v; b[t] = w; } //拆开，把多重背包拆成一个背包; } for (int i = 1; i //01背包模板 for (int j = m; j = a[i]; --j) { dp[j] = max(dp[j],dp[j-a[i]] + b[i]); } } cout //注意数组的大小不要开小了 cinn>>m; int cnt = 0; //分组的类别 for (int i = 1; i int a,b,s; cin>a>>b>>s; int k = 1; //每个组的个数 while (k cnt++; v[cnt] = a*k; //整体体积 w[cnt] = b*k; //整体价值 s -= k; //s要减小 k *= 2; } if(s 0){ cnt ++; v[cnt] = a*s; w[cnt] = b*s; } } n = cnt; //01背包模板 for (int i = 1; i for (int j = m; j = v[i]; --j) { dp[j] = max(dp[j],dp[j-v[i]] + w[i]); } } cout //注意数组的大小不要开小了 cinnm; for (int i = 1; i cin>v[i]>>w[i]>>s[i]; } for (int i = 1; i memcpy(g,dp,sizeof g); for (int r = 0; r s; if(s == -1){ s = 1; } else if(s == 0){ s = m/a; //若为完全背包，则在最优情况下，只能取总体积/该物品体积向下取整 } int k = 1; //计算当前物品分为0,2,4,6..... while (k //多重背包转化为01背包，二进制优化转化过程 v[cnt] = a*k; w[cnt] = b*k; s -= k; k *= 2; cnt++; } if(s 0){ //计算剩下的一部分 v[cnt] = a*s; w[cnt] = b*s; cnt++; } } //01背包模版 for (int i = 1; i for (int j = m; j = v[i]; --j) { dp[j] = max(dp[j],dp[j - v[i]] + w[i]); } } cout //注意数组的大小不要开小了 cinnm; for (int i = 1; i cin>s[i]; for (int j = 1; j cin>v[i][j]>>w[i][j]; } } //模仿01背包的写法； /* for (int i = 1; i for (int j = m; j = 0; --j) { //从大体积向小体积枚举 for (int k = 1; k if(j = v[i][k]) dp[j] = max(dp[j],dp[j-v[i][k]] + w[i][k]); } } } cout //注意数组的大小不要开小了 cinnmz; for (int i = 1; i cin>v[i]>>x[i]>>w[i]; } //类似01背包，在循环里面再多加一层循环 for (int i = 1; i for (int j = m; j = v[i]; --j) { for (int k = z; k >= x[i]; --k) { dp[j][k] = max(dp[j][k],dp[j - v[i]][k - x[i]] + w[i]); } } } cout //注意数组的大小不要开小了 cinnm; for (int i = 1; i cin>v[i]>>w[i]; } //先初始化，初始什么也不装为1； for (int i = 0; i cnt[i] = 1; } for (int i = 1; i for (int j = m; j = v[i]; --j) { int value = dp[j-v[i]] + w[i]; if(value dp[j]){ //如果转移的话，cnt也跟着转移 dp[j] = value; cnt[j] = cnt[j - v[i]]; }else if(value == dp[j]){ //相等的话，cnt[j] += cnt[j-v[i]] cnt[j] = (cnt[j] + cnt[j-v[i]])%mod; } } } cout //注意数组的大小不要开小了 cinnm; for (int i = 1; i cin>v[i]>>w[i]; } /* * 01背包模版求最大价值 * 不同的是要求输出字典序最小的方案，所以我们求最大价值应当倒序 */ for (int i = n; i >= 1; --i) { for (int j = 0; j dp[i][j] = dp[i+1][j]; if(j = v[i]){ dp[i][j] = max(dp[i][j],dp[i+1][j - v[i]] + w[i]); } } } /** * 正序求路径 */ for (int i = 1,j = m; i if(j = v[i] && dp[i][j] == dp[i+1][j-v[i]] + w[i]){ path.push_back(i); j -= v[i]; } } for (int i = 0; i w[i]; } for (int i = 1; i for (int j = m; j = v[i]; --j) { dp[j] = max(dp[j-v[i]] + w[i],dp[j]); } } cout for (int j = m; j = v[i]; --j) { dp[j] = max(dp[j-v[i]] + w[i],dp[j]); } } if(dp[m]
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
