代码随想录 动态规划章节
代码随想录 动态规划章节 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
背包DP 0-1 背包 P2871 [USACO07DEC] Charm Bracelet S https://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 main(){ ...
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 = unsigned...
Meet in the middle
Meet in the middle oiwiki上的内容,具体可以看这个网址 https://oi-wiki.org/search/bidirectional/ P2962 [USACO09NOV] Lights G https://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. Quintomania https://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...
AtCoder Beginner Contest 377
AtCoder Beginner Contest 377 D - Many Segments 2 https://atcoder.jp/contests/abc377/tasks/abc377_d 创建一个dp数组，dp[i]为第i个位置右边第一个区间的右边界。题中给了n组l和r，对于l来说,dp[l]=r;对于其他位置来说，从右往左传递状态，dp[i]=min(dp[i],dp[i+1])，然后对于每一个位置l来说，r所能到达的最右边的位置就是dp[l]-1，所以对于每一个l来说，有dp[l]-l个区间。 123456789101112131415161718192021222324252627282930313233343536#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 =...
