[置顶] 各种实用的模板和黑科技（缓更）

这个博客是记录我的各种模板和黑科技，遇到有关就更新一个点。

1.SPFA

q.push(st);
while (q.size())
    {
int now=q.front();
        q.pop();
for (int i=ls[now];i;i=e[i].next)
        {
if (e[i].w+dis[now]<dis[e[i].y])
            {
                dis[e[i].y]=e[i].w+dis[now];
if (!vis[e[i].y])
                {
                    vis[e[i].y]=true;
                    q.push(e[i].y);
                }
            }
        }
        vis[now]=false;
    }

这个模板的核心就是用了优先队列，充分发挥了优先队列的存放特点。

2.堆排序

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <iostream>
using namespace std;
int main()
{
int a,n;
scanf("%d",&n);
    priority_queue<int>q;
while(n--)
    {
scanf("%d",&a);
        q.push(-a);
    }
while(!q.empty())
    {
printf("%d\n",-q.top());
        q.pop();
    }
}

这里充分了利用队列从大到小的特点来排序，因为是从小到大,所以用负号，但是有点点慢。

3.线筛

       memset(vis,false,sizeof(vis));
       fun=int(double(sqrt(m)));
        F(i,2,fun)
        {
if(!vis[i])
                {
for(int j=i;j<=m/i;j++)
                        {
                                vis[i*j]=true;
                                f[i*j]=i;
                        }
                }
        }

4.快速幂

ll ksm(ll x,ll n)  //求x^n % mod；
{  
    ll res=1;  //答案
while(n>0)  
    {  
if(n & 1)  
            res=(res*x) % mod; //根据a^(2^(i-1))*a^(2^(i-1))=a^(2^i)的原理来算。

        x=(x*x) % mod;  //取模
        n>>=1;  //操作完成后去掉处理过的一位。
    }  
return res;  
} 

时间复杂度（log n）。

5.高精度乘法

node chengfa(node n1,int x)
{
int i;node no;
no.len=n1.len;
for(i=1;i<=no.len;i++) no.a[i]=n1.a[i]*x;
for(i=1;i<=no.len;i++)
{
no.a[i+1]+=no.a[i]/10;
no.a[i]%=10;
}
i=no.len;
while(no.a[i+1]>0)
{
i++;
no.a[i+1]+=no.a[i]/10;
no.a[i]%=10;
}

while(no.a[i]==0&&i>1) i--;

no.len=i;
return no;
}

运用了位运算，还可以进行压位处理，时间会快很多

6.set容器

#include<set>//头文件
using namespace std;
int main()
{
set<int >s;//定义一个名称为s的set容器。
int x;
   s.insert(x);//在set容器里插入一个元素x。
   s.erase(x);//在set容器里删除一个元素x。
multiset <ll> :: iterator k = s.lower_bound(x),在容器里面用二分查找找到第一个比x大的元素
return 0;
}