热茶233

分类

未归档(11)

/ 注册

全部文章（共10篇）

6

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[15],b[15],dp[15]; ll dfs(ll pos,bool limit) { if(pos==0) return 1; if...

C++

2023-06-13

0 158

拓扑排序

拓扑排序是一个有向无环图的所有顶点的线性序列。该序列需要满足每个顶点出现且只出现一次和如果有一条 AA 到 BB 的路径，在序列中 AA 出现在 BB 的前面。 queue <int> Q; void toposort() { for(int i = 1; i <= n; i+...

C++ 拓扑排序

2023-06-03

0 280

并查集

循环+路径压缩 int n,m,z,x,y,fa[10005]; int find(int x) { if (x==fa[x]) return x; return fa[x]=find(fa[x]); } int main() { cin>>n>>...

C++ 并查集

2023-06-03

0 176

st表

用来处理区间最值查询的离线算法，用到了倍增的思想。某个区间查询问题是否适用ST表，关键在于其进行的操作是否允许区间重叠。 int n,m,x,y,a[100010],lg[100010],f[100010][20]; int main() { cin>>n>>m; lg...

C++ st表

2023-06-03

0 242

树状数组

int lowbit(int x){return x&-x;} void update(int x,int v) { while(x<=N) { c[x]+=v; x+=lowbit(x); } return ; } int getsum(int x) { int...

C++ 树状数组

2023-05-30

0 209

Dijkstra算法

Dijkstra：从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。适用于单源最短路径问题 //堆优化dijsktra #include <bits/stdc++.h> using namespace std; typedef pa...

C++ 堆(优先队列) Dijkstra

2023-04-11

0 401

排列组合

排列组合 #include<bits/stdc++.h> using namespace std; int n,m; int tmp[22]; void dfs(int dep,int st) { int i; if(dep==m) { for(i=1;i<=dep;i...

C++ 数学

2023-03-28

0 282

二分

二分 int pos=lower_bound(num,num+k,x) - num; 返回数组中第一个小于或等于被查数的值 int pos=upper_bound(num,num+k,x) - num; 返回数组中第一个小于被查数的值 int lb(int x) { int l=1,r=n+...

二分查找 C++

2023-02-22

1 209

二维前缀和

前缀和的用处：可以把它前面所有元素的总和转换成一维数组的等差累加序列的求和求前缀和 cin>>a; s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; 输出 cin>>x1>>y1>>x2&g...

C++ 前缀和数组

2023-02-06

1 248

快速幂

快速幂快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)，与朴素的O(N)相比效率有了极大的提高。位运算版 ll qpow(ll a,ll n) { ll ans=1; while(n) { if(n&1) ans=ans%mod*a%mod; a=...

C++ 快速幂

2022-12-20

2 417