算分期末复习

文章目录

dijkstra求最短路(不能有负边)

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f,N=1e5+5;
struct Edge{int to,len,nex;}edge[N<<1];int head[N],tot=0;
void add(int from,int to,int len){
    edge[++tot]=(Edge){to,len,head[from]},head[from]=tot;
}
typedef pair<int,int> pi;
priority_queue<pi,vector<pi>,greater<pi> >q;
int d[N];
void dijkstra(int s){
    q.push({0,s}),d[s]=0;
    while(!q.empty()){
        pi cur=q.top();q.pop();
        int x=cur.second;
        for(int i=head[x];i;i=edge[i].nex){
            int y=edge[i].to,l=edge[i].len;
            if(d[y]>d[x]+l){
                d[y]=d[x]+l;
                q.push(make_pair(d[y],y));
            }
        }
    }
}
int main(){
    int n,m;//n个点 m条边
    cin>>n>>m;
    for(int i=1;i<=n;++i) d[i]=INF;
    for(int i=1,x,y,w;i<=m;++i) cin>>x>>y>>w,add(x,y,w);
    int s;cin>>s;//从s到n个点的最短距离
    dijkstra(s);
    for(int i=1;i<=n;++i) printf("%d%c",d[i],(i==n)?'\n':' ');
}

spfa求最短路及判环

P3385

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
typedef long long ll;
struct Edge{
    int to,len,nex;//其实nex是指上一条边
}edge[N<<1];
int head[N],tot;
void add(int from,int to,int len){
    edge[++tot]=(Edge){to,len,head[from]};head[from]=tot;
}
queue<int>q;
int d[N],vis[N],depth[N],INF=0x3f3f3f3f;
int spfa(int n){
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;++i) d[i]=INF,vis[i]=0,depth[i]=0;
    d[1]=0,q.push(1),vis[1]=1;
    while(!q.empty()){
        int x=q.front();q.pop();vis[x]=0;
        if(depth[x]>=n) return 0;
        for(int i=head[x];i;i=edge[i].nex){
            int y=edge[i].to,l=edge[i].len;
            if(d[y]>d[x]+l){
                d[y]=d[x]+l,depth[y]=depth[x]+1;
              //  if(depth[y]==n) return 0;
                if(!vis[y]) vis[y]=1,q.push(y);
            }
        }
    }
    return 1;
}
int main(){
    int T;cin>>T;
    while(T--){
        memset(head,0,sizeof head);tot=0;
        int n,m;scanf("%d%d",&n,&m);
        while(m--){
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            if(w>=0) add(v,u,w);
        }
        puts(spfa(n)?"NO":"YES");
    }
}

快排及查找第K大

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int a[N];
int adjust(int l,int r){
    int x=a[l],i=l,j=r;
    while(i<j){
        while(i<j&&a[j]>=x) --j;
        if(i<j) a[i++]=a[j];
        while(i<j&&a[i]<x) ++i;
        if(i<j) a[j--]=a[i];
    }
    a[i]=x;
    return i;
}
void quick_sort(int l,int r){
    if(l>=r) return;
    int mid=adjust(l,r);
    quick_sort(l,mid-1);
    quick_sort(mid+1,r);
}
//查找第K大
int findK(int l,int r,int K){
    while(K){
        int mid=adjust(l,r);
        if(K==r-mid+1) return a[mid];
        if(K<r-mid+1) l=mid+1;
        else K-=r-mid+1,r=mid-1;
    }
}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    quick_sort(1,n);
    for(int i=1;i<=n;++i) printf("%d%c",a[i],(i==n)?'\n':' ');
}

基数排序

基数排序：百度百科
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
14, 22, 28, 39, 43, 55, 65, 73, 81, 93

#include<bits/stdc++.h>
using namespace std;
#define m(a,b) memset(a,b,sizeof a)
const int N=3e3+5;
int a[N],cnt[10],tmp[N];
int main(){
    int n,mx=0;cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i],mx=max(mx,a[i]);
    int exp=1;
    while(mx/exp){
        m(cnt,0);
        for(int i=1;i<=n;++i) ++cnt[a[i]/exp%10];
        for(int i=1;i<=9;++i) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i) tmp[cnt[a[i]/exp%10]--]=a[i];
        for(int i=1;i<=n;++i) a[i]=tmp[i];
        exp*=10;
    }
    for(int i=1;i<=n;++i) printf("%d%c\n",a[i],(i==n)?'\n':' ');
}

堆排序

先建立一个堆，然后从最大到最小依次排好。自下向上。

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int a[N],n;
void max_heapify(int x,int r){
    int son=x;
    while(x*2<=r){
        if(a[x<<1]>a[x]) son=x<<1;
        if(x*2+1<=r&&a[x<<1|1]>a[x]&&a[x<<1|1]>a[x<<1]) son=x<<1|1;
        if(son==x) break;
        swap(a[x],a[son]),x=son;
    }
}
void heap_sort(){
    for(int i=n/2;i>=1;--i) max_heapify(i,n);//建立一个大根堆
    for(int i=n;i>1;--i) swap(a[1],a[i]),max_heapify(1,i-1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    heap_sort();
    for(int i=1;i<=n;++i) printf("%d%c",a[i],(i==n)?'\n':' ');
}

手写堆

//小根堆
int heap[N],sz;
void push(int val){
    int x;heap[x=++sz]=val;
    while(x!=1){
        if(heap[x>>1]>heap[x]) swap(heap[x>>1],heap[x]),x>>=1;
        else break;
    }
}
int pop(){
    int val=heap[1];heap[1]=heap[sz--];
    int x=1,son=x;
    while(x*2<=sz){
        if(heap[x<<1]<heap[x]) son=x<<1;
        if(x*2+1<=sz&&heap[x<<1|1]<heap[x]&&heap[x<<1|1]<heap[x<<1]) son=x<<1|1;
        if(son==x) break;
        swap(heap[x],heap[son]),x=son;
    }
    return val;
}

LCA

并查集

kmp

manacher

HDU3086

//manacher板子
#include<bits/stdc++.h>
using namespace std;
const int N=110000+5;
char str[N],s[N<<1];int len[N<<1];
int main(){
    while(~scanf("%s",str+1)){
        int n=strlen(str+1);s[0]='@';
        for(int i=1;i<=2*n;i+=2) s[i]='#',s[i+1]=str[(i+1)>>1];
        s[2*n+1]='#',s[2*n+2]='$',s[2*n+3]='\0';
        int mx=0,po=0,ans=0;
        for(int i=1;i<=2*n;++i){
            (mx>i)?(len[i]=min(mx-i+1,len[2*po-i])):(len[i]=1);
            while(s[i-len[i]]==s[i+len[i]]) ++len[i];
            if(i+len[i]-1>mx) mx=i+len[i]-1,po=i;
            ans=max(ans,len[i]-1);
        }
        printf("%d\n",ans);
    }
}

贪心