字典树专题
01 trie 找序列中任意两数的最大异或和 123456789101112131415161718192021222324252627282930313233343536int n, m;int a[N];int idx=0;int ch[N*31][2];void insert(int x){ int p=0; for(int i=30;i>=0;i--){ int u=(x>>i)&1; if(!ch[p][u])ch[p][u]=++idx; p=ch[p][u]; }}int query(int x){ int p=0;int ans=0; for(int i=30;i>=0;i--){ int u=(x>>i)&1; if(ch[p][!u]){ p=ch[p][!u]; ans+=1<<i; } else p=ch[p][u]; } return ans;}void...
概率dp
概率dp 首先是正着递推的计算概率的dp问题 https://ac.nowcoder.com/acm/contest/28263/A 纯数学题 对随机的数字大小分类讨论，计算概率的时候利用高中几何概型的线性规划手法进行计算。 123456789101112131415161718double g=0.5;void solve(){ double k,x;cin>>k>>x; double ans=0; if(k==x)ans=g; else if(k>=2*x)ans=0; else if(k<x){ ans=g*(x*x-k*k); ans/=x*x; ans+=g; } else { ans=g*(2*x-k)*(2*x-k); ans/=x*x;; } baoliu(ans,2); cout<<endl;} CF148D Bag of...
枚举子集+预处理优化dp+贪心视角转化成可做dp
https://www.acwing.com/problem/content/531/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 12, M = 1 << N, INF = 0x3f3f3f3f;int n, m;int d[N][N], g[N][M];int f[M][N];int main(){ scanf("%d%d", &n, &m); memset(d, 0x3f, sizeof d); for (int i = 0; i < n; i ++ ) d[i][i] = 0; while (m...
CCF认证202109-4——之状态压缩dp加期望（记忆化搜索
https://www.acwing.com/problem/content/description/4012/ Acwing long double卡常，注意cin读小数。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include <bits/stdc++.h>using namespace std;#define ll long long//# define int long long#define ull unsigned long long#define pii pair<int,int>//#define double long double#define baoliu(x, y) cout << fixed << setprecision(y) << x#define endl ...
dp优化
dp优化 单调队列优化DP 优化方法大杂烩 I. - qAlex_Weiq - 博客园 (cnblogs.com) 123456789101112131415161718192021222324#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int N=1e5+10;int n,k,q[N];LL w[N],f[N],sum;int main(){ cin>>n>>k; k++; // for(int i=1;i<=n;i++) cin>>w[i],sum+=w[i]; int h=1,t=0; LL s=1e18; for(int i=1;i<=n;i++){ while(h<=t && f[q[t]]>=f[i-1]) t--; q[++t]=i-1; ...
SOSdp
从子集和问题到and卷积 枚举子集：O(3n)O(3^{n})O(3n) 12345678910111213141516171819202122 int u=15; for (int s = u; s; s = (s - 1) & u) { b=s ; cout<<b<<endl;}/*111111101101110010111010100110000111011001010100001100100001*/ 子集和问题参考好的博客https://ottffyzy.github.io/algos/dp/sosdp/ 其实这类算法更多的是解决子集和 （sum of subset） 问题，因此也叫 SOS DP。 也就是对于i从1-n我们希望求出sum[i]=∑j⊆ia[j]sum[i] = \sum_{j \subseteq i} a[j]sum[i]=∑j⊆ia[j] 一个平凡的做法是直接枚举子集：O(3n)O(3^{n})O(3n) 12345for (int i = 0; i < n; i++) { ...
二分图最大匹配——网络流
二分图最大匹配可以转换成网络流模型。 将源点连上左边所有点，右边所有点连上汇点，容量皆为1。原来的每条边从左往右连边，容量也皆为1，最大流即最大匹配。 如果使用 Dinic 算法 求该网络的最大流，可在O(sqrt(n) * m)求出。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#define N 1010#define M 2000010int n,m,k,S,T;struct edge{int v,c,ne;}e[M];int h[N],idx=1; //从2,3开始配对int d[N],cur[N];void add(int a,int b,int c){ e[++idx]={b,c,h[a]}; h[a]=idx;}bool bfs(){ //对点分层，找增广路 ...
二分图最大权完美匹配
时间复杂度为Θ(n^3) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495const int inf =0x3f3f3f3f;const int N=505;long long w[N][N];long long la[N],lb[N];bool va[N],vb[N];long long match[N];long long n,m,upd[N];long long last[N];bool dfs(int x,int fa){ va[x]=1; for(int y = 1; y<=n; y++) { if(!vb[y]) { ...
三元环计数
三元环计数 无向图三元数计数：G - Triangle 给一个邻接矩阵表示无向边关系，求有多少个三元环？ Solution：考虑直接使用bitset优化，枚举两个点，对两个点的边表与起来，找到共同能到达的点。 时间复杂度：O(nm/w)O(nm/w)O(nm/w)(只有两个点有才会进入bitset两个序列相与) debug: 1.首先注意到对于这样的连续的不能一个一个读，不然会出问题 考虑一个三元环按我们枚举的偏序关系，总共会计算三次，所以最后要除3 123456789101112131415161718192021222324bitset<3001>b[3001];void solve(){ cin>>n; for(int i=1;i<=n;i++){ string s;cin>>s; for(int j=0;j<n;j++){ int x=s[j]-'0'; b[i][j+1]=x; } ...
网络流 最大流 Dinic 算法
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#define LL long long#define N 10010#define M 200010using namespace std;int n,m,S,T;//n,m,s,t，分别表示点的个数、有向边的个数、源点序号、汇点序号struct edge{LL v,c,ne;}e[M];int h[N],idx=1; //从2,3开始配对int d[N],cur[N];void add(int a,int b,int c){ e[++idx]={b,c,h[a]}; h[a]=idx;}bool bfs(){ //对点分层，找增广路 memset(d,0,sizeof d); queue<int>q; q.push(S);...
最新文章