对顶堆
对顶堆对顶堆就是通过一个小根堆和一个大根堆来动态维护一个序列上第k大或者第K小的数 序列左侧用小根堆维护,右侧用大根堆维护。 如果题目要求不断动态输出第K大的数,那么小根堆的堆元素就是第K大的元素,大根堆的堆顶元素就是第K+1大的元素。 RMID2 - Running Median Againhttps://www.luogu.com.cn/problem/SP15376 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<bits/stdc++.h>using namespace std;using u32 = unsigned;#define i128 __int128using ll = long long;//#define int llusing u64 = unsigned long long;const int inf = 2147483647;const ll INF = 1e18;void...
代码随想录 动态规划章节
代码随想录 动态规划章节509. 斐波那契数12345678910111213class Solution {public: int fib(int n) { vector<int>dp(n+1); dp[0]=0; if(n>=1)dp[1]=1; for(int i=2;i<=n;i++) { dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; }}; 70. 爬楼梯12345678910111213class Solution {public: int climbStairs(int n) { vector<int>dp(n+1); dp[0]=1; dp[1]=1; for(int i=2;i<=n;i++) ...
常用技巧精选
常用技巧精选尺取法Subsequence尺取法,使用两个指针,让右边的指针往右走知道找到符合条件的位置,如果找不到就break出while循环,左边的指针每次往右移动一位。 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;using u32 = unsigned;#define i128 __int128;using ll = long long;//#define int llusing u64 = unsigned long long;const ll inf = 2147483647;const ll INF = 1e18;signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,s; while(cin>>n>>s) { ...
博弈论
博弈论NIM游戏https://www.cnblogs.com/dx123/p/17263056.html P2197 【模板】Nim 游戏1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;using u32 = unsigned;#define i128 __int128using ll = long long;//#define int llusing u64 = unsigned long long;const ll inf = 2147483647;const ll INF = 1e18;void solve(){ int n; cin>>n; int shu=0; for(int i=1;i<=n;i++) { int x; cin>>x; shu^=x; } ...
背包DP
背包DP0-1 背包P2871 [USACO07DEC] Charm Bracelet Shttps://www.luogu.com.cn/problem/P2871 1234567891011121314151617181920212223242526272829303132// 这一种是01背包的朴素写法#include<bits/stdc++.h>using namespace std;using u32 = unsigned;#define i128 __int128;using ll = long long;//#define int llusing u64 = unsigned long long;const int inf = 2147483647;const ll INF = 1e18;signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin>>n>>m; ...
zzu vjudge暑假训练day5:图论基础
zzu vjudge暑假训练day5:图论基础A 查找文献https://www.luogu.com.cn/problem/P5318 B - 图的遍历https://www.luogu.com.cn/problem/P3916 ==这一题总共做过两遍,第一次的时候从1开始正向dfs没有做出来也不知道哪里错了,后来看了题解学会了反向dfs,第二次想着用正向dfs做一下但是还是失败了,但是已经清除是错在哪里了,现在分享一下正确的做法和错误的思路== 这个是正确做法 123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>using namespace std;using u32 = unsigned;using ll = long long;using u64 = unsigned long long;const int inf = 2147483647;const ll INF = 1e18;int...
zzu vjudge暑假训练day3--动态规划
zzu vjudge暑假训练day3–动态规划B最长上升子序列https://www.luogu.com.cn/problem/B3637 123456789101112131415161718192021222324252627#include<bits/stdc++.h>using namespace std;using u32 = unsigned;using ll = long long;using u64 = unsigned long long;const int inf = 2147483647;const ll INF = 1e18;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<int>a(n+1),dp(n+1,1); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) ...
ST表
ST表oiwiki链接 ST 表(Sparse Table,稀疏表)是用于解决 可重复贡献问题 的数据结构。 可重复贡献问题我的理解是区间重复不会影响结果,比如如果求[1,4]区间和[1,4]区间的最大值,实际上还是求[1,4]区间的最大值,但是如果是求和问题,那么[1,4]和[1,4]放在一起就会得出正确结果的两倍。 P3865 【模板】ST 表 && RMQ 问题RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值 https://www.luogu.com.cn/problem/P3865 1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;using u32 = unsigned;#define i128 __int128;using ll = long long;#define int llusing u64 =...
Meet in the middle
Meet in the middleoiwiki上的内容,具体可以看这个网址 https://oi-wiki.org/search/bidirectional/ P2962 [USACO09NOV] Lights Ghttps://www.luogu.com.cn/problem/P2962 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>using namespace std;using u32 = unsigned;#define i128 __int128;using ll = long long;//#define int llusing u64 = unsigned long long;const int inf = 2147483647;const ll INF = 1e18;signed main(){ ...
Codeforces Round 984 (Div. 3)
Codeforces Round 984 (Div. 3)赛时最后一道没有写出来,但是现在看最后一道依然很难受😡 A. Quintomaniahttps://codeforces.com/contest/2036/problem/A 1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;using u32 = unsigned;#define i128 __int128using ll = long long;//#define int llusing u64 = unsigned long long;const ll inf = 1e9;const ll INF = 1e18;void solve(){ int n; cin>>n; vector<int>a(n+1); for(int...