模板汇总
2026-10-05 18:44:51
发布于：广东
24阅读
0回复
0点赞
一、树状数组
struct BIT{
ll n;
vector<ll> tr;
BIT(){}
BIT(ll len){
init(len);
}
void init(ll len){
n=len;
tr.resize(n+1);
}
ll lowbit(ll x){
return x&-x;
}
void add(ll x,ll d){
for(;x<=n;x+=lowbit(x))
tr[x]+=d;
}
ll ask(ll x){
ll res=0;
for(;x>=1;x-=lowbit(x))
res+=tr[x];
return res;
}
ll sum(ll x,ll y){
return ask(y)-ask(x-1);
}
};
二、建图
struct GRA{
ll n;
vector<vector<ll>> gr;
GRA(){}
GRA(ll len){
init(len);
}
void init(ll len){
n=len;
gr.resize(n+1);
}
void add(ll x,ll y){
gr[x].push_back(y);
gr[y].push_back(x);
}
};
三、树的重心
struct TZX{
ll n;
GRA g;
vector<ll> sz,w,pr,ans;
TZX(){}
TZX(ll len){
n=len;
g.init(len);
sz.resize(n+1);
w.resize(n+1);
pr.resize(n+1);
}
void ins(){
for(ll i=1;i<n;i++){
ll u,v;
cin>>u>>v;
g.add(u,v);
}
}
void dfs(ll x,ll p){
sz[x]=1;
pr[x]=p;
for(ll s:g.gr[x]){
if(s==p)
continue;
dfs(s,x);
sz[x]+=sz[s];
w[x]=max(w[x],sz[s]);
}
w[x]=max(w[x],n-sz[x]);
}
void gas(){
dfs(1,0);
ll mn=INF;
for(ll i=1;i<=n;i++)
mn=min(mn,w[i]);
for(ll i=1;i<=n;i++)
if(w[i]==mn)
ans.push_back(i);
}
};
四、大数乘法
#define ull unsigned long long
// 计算 (x*p)%n 的值
ull sm(ull x,ull p,ull n){
ull res=0;
while(p>0){
if(p&1){
if(x>=n-res){
res-=n-x;
}
else{
res+=x;
}
}
if(x>=n-x){
x-=n-x;
}
else{
x+=x;
}
p>>=1;
}
return res;
}
还有待更新……
有帮助，赞一个