些许板子

yaoyg · 2025-11-23 09:31:48 · 算法·理论

双端队列

#include<bits/stdc++.h>
using namespace std;
//有个东西叫做deque
struct Dque
{
  int q[10000*2];
  int head=10000;
  int tail=10000-1;
}
bool r;
bool empty(Dque p)
{
  return p.tail<p.head;
}
int size(Dque p)
{
  return p.tail-p.head+1;
}
int front(Dque p,bool r)
{
  if(r)
  {
    return p.q[p.tail];
  }
  else
  {
    return p.q[p.head];
  }
}
int back(Dque p,bool r)
{
  if(!r)
  {
    return p.q[p.tail];
  }
  else
  {
    return p.q[p.head];
  }
}
int push_front(Dque p,int x,bool r)
{
  if(r)
  {
    p.q[++p.tail]=x;
  }
  else
  {
    p.q[--p.head]=x;
  }
}
int push_back(Dque p,int x,bool r)
{
  if(!r)
  {
    p.q[++p.tail]=x;
  }
  else
  {
    p.q[--p.head]=x;
  }
}
int pop_front(Dque p,bool r)
{
  if(r)
  {
    p.tail--;
  }
  else
  {
    p.head++;
  }
}
int pop_back(Dque p,bool r)
{
  if(!r)
  {
    p.tail--;
  }
  else
  {
    p.head++;
  }
}
void reverse(bool r)
{
  r^=1;
}
//代码有亿点长，使用三目运算符可以简化一下代码
int main()
{
  //主函数内容不必多说了吧（^-^）
    return 0;
}

并查集

#include<bits/stdc++.h>
using namespace std;

int fa[1000000],n,m;

int find(int x)//寻找父亲
{
    if(fa[x]!=x)
    {
        fa[x]=find(fa[x]);
    }
    return fa[x];
}

int merge(int x,int y)//合并
{
    x=find(x),y=find(y);
    if(x!=y)
    { 
        fa[x]=y;
    }
    return 0;
}

int haveCA(int x,int y)//有无共同祖先
{
    x=find(x),y=find(y);
    if(x==y)
    { 
        //cout<<"Y"<<endl;
        return 1;
    }
    else
    {
        //cout<<"N"<<endl;
        return 0;
    }
}

int main(){
    //...(0-O)你说这里应该不需要给出来的，对吧？
    return 0;
}

平衡树

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int gen1,id;
int n,opt,x;
struct node 
{
    int l,r;//左子右子
    int key;//值
    int val;//随机值（随缘旋转）
    int size;//子树长度
    int cnt;//有多少个数
}tr[N];
int get(int key)
{
    tr[++id].key=key;
    tr[id].val=rand();
    tr[id].size=tr[id].cnt=1;
    return id;
}
void push_up(int q)
{
    tr[q].size=tr[tr[q].r].size+tr[tr[q].l].size+tr[q].cnt;
    return;
}
void build()
{
    get(-inf);
    get(inf);
    gen1=1;
    tr[1].r=2;
    push_up(1);
}
void zig(int& p)//左
{
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    push_up(tr[p].r);
    push_up(p);
}
void zag(int& p)//右
{
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    push_up(tr[p].l);
    push_up(p);
}
void insert(int& p,int key)
{
    if (!p)
    {
        p=get(key);
        return;
    }
    else
    {
        if (tr[p].key==key)
        {
            tr[p].cnt++;
        }
        else
        {
            if (tr[p].key>key)
            {
                insert(tr[p].l,key);
                if(tr[tr[p].l].val>tr[p].val)
                {
                    zig(p);
                }
            }
            else
            {
                insert(tr[p].r,key);
                if(tr[tr[p].r].val>tr[p].val)
                {
                    zag(p);
                }
            }
        }
        push_up(p);
    }
}
void remove(int& p,int key)
{
    if (!p)
    {
        return;
    }
    if (tr[p].key==key)
    {
        if (tr[p].cnt>1)
        {
            tr[p].cnt--;
        }
        else
        {
            if (tr[p].l||tr[p].r)
            {
                if (!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
                {
                    zig(p);
                    remove(tr[p].r,key);
                }
                else
                {
                    zag(p);
                    remove(tr[p].l,key);
                }
            }
            else
            {
                p=0;
            }
        }
    }
    else if (tr[p].key>key)
    {
        remove(tr[p].l,key);
    }
    else
    {
        remove(tr[p].r,key);
    }
    push_up(p);
}

int get_rank(int p,int key)
{
    if(!p)
    {
        return 1;
    }
    if(tr[p].key==key)
    {
        return tr[tr[p].l].size+1;
    }
    else if(tr[p].key>key)
    {
        return get_rank(tr[p].l,key);
    }
    else
    {
        return tr[tr[p].l].size+tr[p].cnt+get_rank(tr[p].r,key);
    }
}
int get_key(int p,int rank)
{
    if(!p)
    {
        return inf;
    }
    if(tr[tr[p].l].size>=rank)
    {
        return get_key(tr[p].l,rank);
    }
    else if(tr[tr[p].l].size+tr[p].cnt>=rank)
    {
        return tr[p].key;
    }
    else
    {
        return get_key(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
    }
}
int get_last(int p,int key)
{
    if(!p)
    {
        return -inf;
    }
    if(tr[p].key>=key)
    {
        return get_last(tr[p].l,key);
    }
    else
    {
        return max(tr[p].key,get_last(tr[p].r,key));
    }
}
int get_next(int p,int key)
{
    if(!p)
    {
        return inf;
    }
    if(tr[p].key<=key)
    {
        return get_next(tr[p].r,key);
    }
    else
    {
        return min(tr[p].key,get_next(tr[p].l,key));
    }
}
int main()
{
    //...(-.-)zZ  我是一个懒人
    return 0;
}

dijkstra

#include <bits/stdc++.h>

using namespace std;
long long n, m, s;

struct Edge
{
    long long to,w;
    bool operator<(const Edge &s) const
    {
        return w>s.w;
    }
};

bool S[10001]; 
vector<Edge> G[10001]; 
long long dis[10001];

long long dijkstra(long long start)
{

    priority_queue<Edge> q;

    q.push({start, 0});
    for(long long i=1;i<=n;i++)
    {
        dis[i]=INT_MAX;
    }

    dis[start]=0;
    while (q.size()>0) 
    {
        Edge a=q.top();
        q.pop();

        long long u=a.to;
        if(S[u]) 
        {
            continue;
        }
        S[u]=1;
        for (int i=0;i<G[u].size();i++) 
        {
            int v = G[u][i].to;
            if (S[v] == 0) {
                dis[v] = min(dis[v],G[u][i].w+a.w);
                q.push({v,dis[v]});
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m>>s;
    for(long long i=0;i<m;i++)
    {
        long long u,v,w;
        cin>>u>>v>>w;
        G[u].push_back({v,w});
    }
    dijkstra(s);
    for(long long i=1;i<=n;i++)
    {
        cout<<dis[i]<<" ";
    }
    return 0;
}

Prim

#include <bits/stdc++.h>

using namespace std;

int n,m;
int q[5001][5001];
bool visited[5001];

int MST()
{
    vector<int> dist(n+1,0x3f3f3f3f); 
    dist[1]=0;     
    int mst_sum=0;   

    for (int i=0;i<n;i++) 
    {
        int u=-1; 
        int min_dist=0x3f3f3f3f; 
        for (int j=1;j<=n;j++)
         {
            if (!visited[j]&&dist[j]<min_dist) 
            {
                min_dist=dist[j];
                u=j;
            }
        }
        if(u==-1)
        {
            return -1;
        }
        visited[u]=1;
        mst_sum+=dist[u];
        for (int v=1;v<=n;v++) 
        {
            if (!visited[v]&&q[u][v]<dist[v])
            {
                dist[v]=q[u][v];
            }
        }
    }
    return mst_sum;
}

int main()
{
    memset(q, 0x3f, sizeof(q));
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        q[u][v]=min(q[u][v],w);
        q[v][u]=min(q[v][u],w);
    }
    int ans=MST();
    if(ans==-1)
    {
        cout<<"orz"<<endl;
    }
    else
    {
        cout<<ans<<endl;
    }
    return 0;
}