十模板HJR
Hjr1141451931 · · 个人记录
赛前必备模板
一.线段树
struct ST{
ll A[MAXN];
struct node{
int l,r;
ll val,lazy;
}tree[MAXN*4];
void build(int u,int l,int r){
tree[u].l=l,tree[u].r=r,tree[u].lazy=0;
if(l==r){tree[u].val=A[l];return;}
int mid=(l+r)/2;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
tree[u].val=tree[u*2].val+tree[u*2+1].val;
return;
}
void Spread(int u){
if(tree[u].lazy){
tree[u*2].val+=tree[u].lazy*(tree[u*2].r-tree[u*2].l+1);
tree[u*2+1].val+=tree[u].lazy*(tree[u*2+1].r-tree[u*2+1].l+1);
tree[u*2].lazy+=tree[u].lazy;
tree[u*2+1].lazy+=tree[u].lazy;
tree[u].lazy=0;
}
}
ll Ask(int u,int l,int r){
int pl=tree[u].l,pr=tree[u].r;
ll val=tree[u].val;
if(l<=pl&&r>=pr) return val;
int mid=(pl+pr)/2;ll ans=0;
Spread(u);
if(l<=mid) ans+=Ask(u*2,l,r);
if(r>=mid+1) ans+=Ask(u*2+1,l,r);
return ans;
}
void Add(int u,int l,int r,ll add){
int pl=tree[u].l,pr=tree[u].r;
if(l<=pl&&r>=pr){tree[u].val+=add*(pr-pl+1);tree[u].lazy+=add;return;}
int mid=(pl+pr)/2;
Spread(u);
if(l<=mid) Add(u*2,l,r,add);
if(r>=mid+1) Add(u*2+1,l,r,add);
tree[u].val=tree[u*2].val+tree[u*2+1].val;
}
}T;二.树链剖分
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
template<typename T> inline void read(T &x){
x=0;T w=1,ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=x*w;
}
const int MAXN=200005;
int P,top[MAXN],adr[MAXN],tot;
struct node{
int Hc,f,siz,dep,val;
}t[MAXN];
int root;
int n,m;
int head[MAXN],cnt;
struct edge{
int to,nxt;
}e[MAXN];
void add(int u,int v){
cnt++;
e[cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
struct ST{
ll A[MAXN];
struct node{
int l,r;
ll val,lazy;
}tree[MAXN*4];
void build(int u,int l,int r){
tree[u].l=l,tree[u].r=r,tree[u].lazy=0;
if(l==r){tree[u].val=A[l];return;}
int mid=(l+r)/2;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
tree[u].val=tree[u*2].val+tree[u*2+1].val;
return;
}
void Spread(int u){
if(tree[u].lazy){
tree[u*2].val+=tree[u].lazy*(tree[u*2].r-tree[u*2].l+1);
tree[u*2+1].val+=tree[u].lazy*(tree[u*2+1].r-tree[u*2+1].l+1);
tree[u*2].lazy+=tree[u].lazy;
tree[u*2+1].lazy+=tree[u].lazy;
tree[u].lazy=0;
}
}
ll Ask(int u,int l,int r){
int pl=tree[u].l,pr=tree[u].r;
ll val=tree[u].val;
if(l<=pl&&r>=pr) return val;
int mid=(pl+pr)/2;ll ans=0;
Spread(u);
if(l<=mid) ans+=Ask(u*2,l,r);
if(r>=mid+1) ans+=Ask(u*2+1,l,r);
return ans;
}
void Add(int u,int l,int r,ll add){
int pl=tree[u].l,pr=tree[u].r;
if(l<=pl&&r>=pr){tree[u].val+=add*(pr-pl+1);tree[u].lazy+=add;return;}
int mid=(pl+pr)/2;
Spread(u);
if(l<=mid) Add(u*2,l,r,add);
if(r>=mid+1) Add(u*2+1,l,r,add);
tree[u].val=tree[u*2].val+tree[u*2+1].val;
}
}T;
int dfs1(int u){
t[u].siz=1;
int si=0,Hvs=-1;
for(int i=head[u];i;i=e[i].nxt){
if(e[i].to!=t[u].f){
t[e[i].to].f=u,t[e[i].to].dep=t[u].dep+1;
int sic=dfs1(e[i].to);
if(sic>Hvs) Hvs=sic,t[u].Hc=e[i].to;
si+=sic;
}
}
t[u].siz+=si;
return t[u].siz;
}
void dfs2(int u,int tp){
top[u]=tp;
adr[u]=++tot;
T.A[tot]=t[u].val;
if(t[u].Hc!=u&&t[u].Hc) dfs2(t[u].Hc,tp);
for(int i=head[u];i;i=e[i].nxt)
if(e[i].to!=t[u].Hc&&e[i].to!=t[u].f) dfs2(e[i].to,e[i].to);
return;
}
void Radd(int x,int y,int val){
while(top[x]!=top[y]){
if(t[top[x]].dep<t[top[y]].dep) swap(x,y);
T.Add(1,adr[top[x]],adr[x],val);
x=t[top[x]].f;
}
if(t[x].dep>t[y].dep) swap(x,y);
T.Add(1,adr[x],adr[y],val);
}
ll qRange(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(t[top[x]].dep<t[top[y]].dep) swap(x,y);
ans+=T.Ask(1,adr[top[x]],adr[x]);
ans%=P;
x=t[top[x]].f;
}
if(t[x].dep>t[y].dep) swap(x,y);
return (ans+T.Ask(1,adr[x],adr[y]))%P;
}
void adds(int x,int val){
T.Add(1,adr[x],adr[x]+t[x].siz-1,val);
}
ll qs(int x){
return T.Ask(1,adr[x],adr[x]+t[x].siz-1)%P;
}
signed main()
{
cin>>n>>m>>root>>P;
for(int i=1;i<=n;i++) cin>>t[i].val;
for(int i=1;i<=n-1;i++){
int a,b;
read(a),read(b);
add(a,b),add(b,a);
}
t[root].dep=1;
dfs1(root);
dfs2(root,root);
T.build(1,1,n);
for(int i=1;i<=m;i++){
int o,x,y,z;
read(o),read(x);
if(o==1){
read(y),read(z);
Radd(x,y,z);
}
if(o==2){
read(y);
cout<<qRange(x,y)<<endl;
}
if(o==3){
read(y);
adds(x,y);
}
if(o==4) cout<<qs(x)<<endl;
}
return 0;
}三.最短路
#include<bits/stdc++.h>
using namespace std;
int n,m,st;
bool book[1000005];
struct edge
{
int to,val;
};
struct node
{
int d,upper;
int operator <(const node &b)
const{
return d>b.d;
}
};
vector <edge> s[2000005];
int dis[1000005];
priority_queue<node> q;
void dijkstra()
{
while(!q.empty())
{
while(book[q.top().upper]&&q.top().upper!=st){
if(q.empty())
return;
q.pop();
}
int u=q.top().upper;
book[u]=true;
int v=dis[u];
for(int i=0;i<s[u].size();i++)
{
int t=s[u][i].to;
if(s[u][i].val+v<dis[t]&&!book[t])
dis[t]=s[u][i].val+v;
if(!book[t])
q.push({dis[t],t});
}
q.pop();
}
}
int main()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
cin>>n>>m>>st;
dis[st]=0;
book[st]=true;
q.push({0,st});
for(int i=1;i<=m;i++)
{
int f,t,v;
cin>>f>>t>>v;
s[f].push_back({t,v});
}
dijkstra();
for(int i=1;i<=n;i++)
{
if(dis[i]!=0x3f3f3f3f)
cout<<dis[i]<<' ';
else
cout<<"2147483647"<<' ';
}
cout<<endl;
return 0;
}四.KMP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=20000005;
char str1[MAXN],str2[MAXN];
int z[MAXN],Z[MAXN];
int n,m;
void getext(){
int l=0,r=0;
z[1]=m;
for(int i=2;i<=m;i++){
if(i>r){
while(str2[z[i]+1]==str2[i+z[i]])
z[i]++;
l=i,r=i+z[i]-1;
}
else if(z[i-l+1]<r-i+1) z[i]=z[i-l+1];
else{
z[i]=r-i;
while(str2[z[i]+1]==str2[i+z[i]])
z[i]++;
l=i,r=i+z[i]-1;
}
}
}
signed main(){
scanf("%s%s",str1+1,str2+1);
n=strlen(str1+1),m=strlen(str2+1);
getext();
int res=z[1]+1;
for(int i=2;i<=m;i++) res^=i*(z[i]+1);
cout<<res<<endl;
int l=0,r=0;
for(int i=1;i<=n;i++){
if(i>r){
while(1+Z[i]<=m&&i+Z[i]<=n&&str2[Z[i]+1]==str1[i+Z[i]])
Z[i]++;
l=i,r=i+Z[i]-1;
}
else if(z[i-l+1]<r-i+1) Z[i]=z[i-l+1];
else{
Z[i]=r-i+1;
while(1+Z[i]<=m&&i+Z[i]<=n&&str2[Z[i]+1]==str1[i+Z[i]])
Z[i]++;
l=i,r=i+Z[i]-1;
}
}
res=Z[1]+1;
for(int i=2;i<=n;i++) res^=i*(Z[i]+1);
cout<<res<<endl;
return 0;
}
五.AC自动机
#include<bits/stdc++.h>
using namespace std;
const int MAXN=800005;
int Trie[MAXN][27],tot,End[MAXN];
void Insert(string s,int up){
int u=0,len=s.size();
for(int i=0;i<len;i++){
int c=s[i]-'a';
if(!Trie[u][c])
Trie[u][c]=++tot;
u=Trie[u][c];
}
End[u]=up;
}
int n,fail[MAXN];
string a[MAXN],b;
void buildfail(){
queue<int> q;
for(int i=0;i<26;i++)
if(Trie[0][i]){
q.push(Trie[0][i]);
fail[Trie[0][i]]=0;
}
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){
if(Trie[u][i])
fail[Trie[u][i]]=Trie[fail[u]][i],q.push(Trie[u][i]);
else Trie[u][i]=Trie[fail[u]][i];
}
}
}
int ans[MAXN];
void query(){
int len=b.size(),u;
for(int i=0,u=0;i<len;i++){
u=Trie[u][b[i]-'a'];
for(int j=u;j;j=fail[j]) ans[End[j]]++;
}
return;
}
int main(){
cin>>n;
while(n!=0){
for(int i=0;i<=tot;i++)
for(int j=0;j<=26;j++)
Trie[i][j]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
Insert(a[i],i);
}
memset(fail,0xcf,sizeof(fail));
fail[0]=0;
buildfail();
cin>>b;
query();
int ma=INT_MIN;
vector<int> maans;
for(int i=1;i<=n;i++)
if(ans[i]>ma){
ma=ans[i];
maans.clear();
maans.push_back(i);
}
else if(ans[i]==ma){
maans.push_back(i);
}
cout<<ma<<endl;
for(int i=0;i<maans.size();i++)
cout<<a[maans[i]]<<endl;
for(int i=1;i<=n;i++) ans[i]=0;
cin>>n;
}
return 0;
}六.混合背包
复制代码到粘帖板
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=10010;
int n,m,v[MAXN],w[MAXN],tot;
bool flag[MAXN];
ll ans,f[MAXN];
int main(){
memset(f,0xcf,sizeof(f));
f[0]=0;
cin>>m>>n;
for(int i=1;i<=n;i++){
int V,W,cnt;
cin>>V>>W>>cnt;
if(cnt){
for(int j=1;j<cnt;j*=2){
v[++tot]=V*j;
w[tot]=W*j;
flag[tot]=1;
cnt-=j;
}
if(cnt){
v[++tot]=V*cnt;
w[tot]=W*cnt;
flag[tot]=1;
}
}
else{
v[++tot]=V;
w[tot]=W;
flag[tot]=0;
}
}
for(int i=1;i<=tot;i++)
if(flag[i])
for(int j=m;j>=v[i];j--)
ans=max(ans,f[j]=max(f[j],f[j-v[i]]+w[i]));
else
for(int j=v[i];j<=m;j++)
ans=max(ans,f[j]=max(f[j],f[j-v[i]]+w[i]));
cout<<ans<<endl;
return 0;
}七.状压DP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
ll f[13][103][1<<10];
vector<int> allst,head[1<<10];
int cnt[1<<10];
bool check(int s){
for(int i=0;i<n;i++) if((s>>i&1)&&(s>>i+1&1)) return false;
return true;
}
int Count(int s){
int res=0;
for(int i=0;i<n;i++){
if(s>>i&1)
res++;
}
return res;
}
int main(){
cin>>n>>m;
for(int i=0;i<(1<<n);i++)
if(check(i)){
allst.push_back(i);;
cnt[i]=Count(i);
}
for(int i=0;i<allst.size();i++)
for(int j=0;j<allst.size();j++)
if((allst[i]&allst[j])==0&&check(allst[i]|allst[j]))
head[i].push_back(j);
f[0][0][0]=1;
for(int i=1;i<=n+1;i++)
for(int j=0;j<=m;j++)
for(int a=0;a<allst.size();a++)
for(int b=0;b<head[a].size();b++)
if(cnt[allst[a]]<=j)
f[i][j][allst[a]]+=f[i-1][j-cnt[allst[a]]][allst[head[a][b]]];
cout<<f[n+1][m][0]<<endl;
return 0;
}八.EXGCD
int ex_gcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int d=ex_gcd(b,a%b,x,y);
int temp=x;
x=y;
y=temp-a/b*y;
return d;
}九.EXCRT
ll EXCRT(){
for(int i=2;i<=n;i++){
ll a1=a[i-1],a2=a[i],m1=m[i-1],m2=m[i],c=(a2-a1%m2+m2)%m2;
ll M=lcm(m1,m2);
ll x,y;
ll d=exgcd(m1,m2,x,y);
ll p=Mul(x,c/d,m2);
a[i]=a1+m1*p;
a[i]=(a[i]%M+M)%M,m[i]=M;
}
return a[n];
}十.模拟退火
#include<bits/stdc++.h>
using namespace std;
double T=90000,Down=0.998,eps=1e-14;
/*
T++,时间++,精度++;
Down++,时间++,精度++;
eps--,时间++,精度++;
*/
//样例函数：y=x^4+x^3-3*x^2-x 极点：(-1.63,-3.61) (1,-2)
double f(int x){
return x*x*x*x+x*x*x-3.0*x-x;
}
int random(int x){
return rand()*rand()%x;
}
int main(){
//x -100~100
srand(time(NULL));
double x=0,F;
x=100-random(200);
F=f(x);
while(T>eps){
// cout<<x<<' '<<T<<endl;
double nx=101;
while(nx>100||nx<-100){
double dx=(2*random(100)-100)*T;
nx=x+dx;//保证落到值域内
}
double Fn=f(nx);
if(Fn<F) x=nx,F=Fn;//如果更优则替换
else{
double chance=exp(-abs(Fn-F)/T);//如果不能满足，也有一定的概率替换
if(rand()<RAND_MAX*chance) x=nx,F=Fn;//防止小数运算
}
T*=Down;//温度下降
}
cout<<x<<' '<<F<<endl;
return 0;
}