0-1背包 设n个物体,体积v,价值w,背包总容量M 状态转移方程:f[j]=max(f[j],f[j-v[i]]+w[i]) 代码: for(int i=1;i<=n;i++) { for(i…
标签:算法
ST表、树上倍增、LCA(模板合集)
st表 模板题:洛谷 P3865 代码: #include <bits/stdc++.h> #define ll long long using namespace std; int f[…
牛客:滑动窗口(单调队列)
之前只系统学习过单调栈,以为单调队列和单调栈差不多,就没学。结果做到一道单调队列的题时,发现自己根本写不出来(高估自己了。。。。) 这是牛客每日一题中的,原题链接:https://ac.nowcode…
Codeforces Global Round 7 D2.Prefix-Suffix Palindrome (Hard version) 马拉车算法
原题链接:https://codeforces.com/contest/1326/problem/D2 字符串问题,D1数据较小,暴力过了 题意大体是:给你一个字符串 s ,让你找一个字符串 t ,字…
树形DP(模板+题目合集)
做了好几天的树形DP的题,没做那种特别难的,感觉类型都差不多,大同小异吧 参考OI WiKi 首先是经典的树形DP题目 洛谷P1352 没有上司的舞会 题目链接:https://www.luogu.c…
鸽巢原理+扩展欧几里得+欧拉筛
鸽巢原理: 转自CSDN博客 链接:https://blog.csdn.net/guoyangfan_/article/details/102559097 扩展欧几里得 其实扩欧求最大公约数这个都晓得…
模板:(单源最短路径+链式前向星)
洛谷中的一道模板题 原题链接:https://www.luogu.com.cn/problem/P3371 以前学链式前向星的时候没怎么认真学,觉得没啥用,用邻接矩阵不香吗 刚刚做了洛谷这道dijsk…
专题:树状数组及其应用(附线段树模板)
线段树和树状数组其实在暑假就学过,但我当时没理解,也没怎么用过,渐渐地就忘掉了。 之前在做牛客训练营的时候有一道题用到了线段树,于是重新学习了一下线段树 当时以为,只要会了线段树,还学树状数组干啥 知…