存档

个人存的算法/数据结构板子，ACGO IDE 爆了，发个帖

//迪杰斯特拉，邻接矩阵实现
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=0x3f3f3f3f;
int mp[1005][1005];
int n,m,s;
int ans;
int dis[1005]={-1},vis[1005];
//迪杰斯特拉函数
void dij(int n,int s){
    //将所有的点距离设置为无穷
    for(int i=0;i<=n;i++){
        dis[i]=N;
    }dis[s]=0;//s为起点，s到s的点的距离为0
    //遍历所有的点
    for(int i=1;i<=n;i++){
        int u=0;//认为当前距离最短的点为0
        for(int j=1;j<=n;++j){
            if(!vis[j] and dis[j] < dis[u])u=j;//如果这个点没有选定且当为j点的距离比u的距离更短，对最短路径u点更新
        }vis[u]=1;//选定了u点，对u点进行标记
        for(int j=1;j<=n;j++){//遍历检查所有点
            if(mp[u][j]){//如果u到j点有边
                int w = mp[u][j];//获取u点到j点的距离
                if(dis[j]>dis[u]+w){//检查如果u点到j点的距离，小于原本j点的距离
                    dis[j]=dis[u]+w;//将到j点的距离数组更新。
                }
            }
        }
    }
}
signed main(){
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        int tmp=mp[u][v]?mp[u][v]:N;//邻接矩阵储存图，如果该位置，没有边则设置为无限（既0x3f3f3f3f）。否则为原本的边与当前边的较小者。
        mp[u][v]=min(tmp,w); //人话就是处理重边
    }dij(n,s);//函数调用，n为点的个数，s为起点
    for(int i=1;i<=n;i++){//依次输出所有点从起点s的最短路径
        if(dis[i]==N)cout << -1 << " "; //不能到达则输出-1
        else cout << dis[i] << " ";//能到达输出最短路径
    } 
    return 0;
}*/

//贝尔曼福特

/*#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int from,to,len;//出发点，要去的点，长度
}a[10010];
int n,m,s,t;//依托不知名的东西,分别是节点数，边数，起点，终点
int dis[10010];
signed main(){
    cin >> n >> m >> s >> t;
    for(int i=1;i<=n;i++){
       dis[i]=1e9; //初始化数组
    }
    dis[s]=0;//起点
    for(int i=1;i<=m;i++){
        cin >> a[i].from >> a[i].to >> a[i].len;//输入图的相关数据
	}
    int from,to,len;//出发点，要去的点，长度
    for(int k=1;k<n;k++){
        bool p=false;
        for(int i=1;i<=m;i++){
            from=a[i].from,to=a[i].to,len=a[i].len;//赋值。
            if(dis[to]>dis[from]+len){
                p=true;
                dis[to]=dis[from]+len;
            }
            //判断走到to这个点能否更新最短距离
        }if(p==false)break;                                                                                                                         
    }
    cout << dis[t];
    //输出走到t的最短路径
    return 0;
}	 */

//SPFA
/*
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int dis[10010],vis[10010],mp[5010][5010];
signed main(){
    cin >> n >> m >> s >>t;
    for(int i=1;i<=n;i++){
        dis[i]=1e9; //初始化数组
    }for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            mp[i][j]=1e9;//初始化*2
        }
    }for(int i=1;i<=m;i++){
        int s,t,v;
        cin >> s >> t >> v;
        mp[s][t]=v;//输入图并储存
	}dis[s]=0;
    vis[s]=1;
    queue<int> a;
    a.push(s);
    while(a.size()){
        int u=a.front();//取出队首
        a.pop();//取出
        vis[u]=0;//将该点标记为不在队列中
        for(int i=1;i<=n;i++){
            if(dis[i]>dis[u]+mp[u][i]){
                dis[i]=dis[u]+mp[u][i];//更新，进行松弛操作
                if(!vis[i]){//如果该点被更改
                    vis[i]=1; //标记
                    a.push(i);//入队
                }
            }
        }
    }
    cout << dis[t];
    return 0;
}	 */
// 弗洛伊德
/*#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;//计数器
int dis[101][101],a[10001];//距离数组及必经之路数组
int main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++)cin >> a[i];//输入必经之路
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> dis[i][j];//输入距离
        }
    }for(int k=1;k<=n;k++){//中转点
        for(int i=1;i<=n;i++){//在邻接矩阵的x坐标
            for(int j=1;j<=n;j++){ //在邻接矩阵的y坐标
               dis[i][j]=min(dis[i][j],dis[k][j]+dis[i][k]);//松弛操作
            }
        }
    }for(int i=2;i<=m;i++){
        ans+=dis[a[i-1]][a[i]];//计数
    }cout << ans;
    return 0;
}*///归并
/*#include<iostream>
using namespace std;
int n,a[1010],temp[1010];
void MergeSort(int l,int r){
	//2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回 
	if(l==r){
        return ;
    }
	//2.2、找到中间位置，递归处理左半部分，递归处理右半部分 
	int mid=(l+r)/2;
	MergeSort(l,mid);
    MergeSort(mid+1,r);
	//3、合并，两个序列分别10.14.223.45为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组temp，下标右移 
	int i=l,j=mid+1,k=l;
	while(i<=mid and j<=r){
		if(a[i]<=a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	//3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 temp 
	while(i<=mid)
		temp[k++]=a[i++];
	while(j<=r)
		temp[k++]=a[j++];
	//4、把结果数组 temp 重新赋给 a 数组 
    for(int i=l;i<=r;i++)
        a[i]=temp[i];
}
int main(){
	//1、定义变量 n 和数组 
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	//2、划分，左端点为 1，右端点为 n，递归处理 
	MergeSort(1,n);
	for(int i=1;i<=n;i++)
		cout << a[i]<<" "; 
	return 0;
}*/
//欧拉筛
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
int sz[10000005];
int prime[10000005];
signed main(){
    int a;
    cin >> a;
    int cnt = 0;
    sz[1] = 1;
    for(int i=2;i<=a;i++){
        if(sz[i]==0){
            prime[cnt++] = i;
        }for(int j=0;j<cnt and i*prime[j]<=a;j++){
            sz[i*prime[j]] = 1;
            if(i%prime[j]==0){
                break;
            }
        }
    }for(int i=1;i<=a;i++){
        if(sz[i]==0){
            cout << i << " ";
        }
    }
    return 0;
}*/
//埃氏筛
/*#include <bits/stdc++.h>
using namespace std;
int main(){
    int a;
    cin >> a;
    int sz[10000005]={0};
    sz[1]=1;
    for(int i=1;i*i<=a;i++){
        if(sz[i]==0){
            for(int j=2*i;j<=a;j+=i){
                sz[j]=1;
            }
        }
    }for(int i=1;i<=a;i++){
        if(sz[i]==0){
            cout << i << " ";
        }
    }
    return 0;
}*/
//lis
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
int sz[1005]={},lis[1005]={};
signed main(){
    int a;
    cin >> a;
    for(int i=1;i<=a;i++){
        cin >>sz[i];
    }for(int i=1;i<=a;i++){//lis
        lis[i]=1;
        for(int j=1;j<i;j++){ 
            if(sz[j]<sz[i]){
                lis[i]=max(lis[i],lis[j]+1);
            }
        }
    }
    cout << lis[a];
    return 0;
}  */
//lds
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
int sz[1005]={},lds[1005]={};
signed main(){
    int a;
    cin >> a;
    for(int i=1;i<=a;i++){
        cin >>sz[i];
    }for(int i=1;i<=a;i++){//lds
        lds[i]=1;
        for(int j=1;j<i;j++){ 
            if(sz[j]>sz[i]){
                lds[i]=max(lds[i],lds[j]+1);
            }
        }
    }
    cout << lds[a];
    return 0;
}*/
//快速排序
/*#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int a[N];
int n;
void partition(int a[],int l,int r){
    int x=a[l],i=l,j=r;
    if(l>=r) return;
    while(i<j) {
        while(i<j and a[j]>=x) j--;
        a[i]=a[j];
        while(i<j and a[i]<=x) i++;
        a[j]=a[i];
        
    }a[i]=x;
    partition(a,l,i-1);
    partition(a,i+1,r);
}

int main(){
   	cin>>n; 
    for(int i=0;i<n;i++)  cin>>a[i];
    partition(a,0,n-1);
    for(int i=0;i<n;i++)cout << a[i]<<" ";
    return 0;
}*/



//小根堆STL
/*#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int>> heap;//小根堆
int main(){
    int x;
    heap.top();//取堆顶元素
    heap.pop();//删除堆顶元素
    heap.push(x);//将元素 x 插入堆
    heap.size();//堆的大小
    heap.empty();//判空
    return 0;
}*/

//dij堆优化
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=0x3f3f3f3f3f3f3f;
int mp[1005][1005];
int n,m,s;
int dis[1005],vis[1005];
void dij(int n,int s){
    for(int i=1;i<=n;i++){
        dis[i]=N;
    }
    dis[s]=0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
    heap.push({0,s});
    while(!heap.empty()){//主循环
        int u=heap.top().second;
        heap.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int j=1;j<=n;j++){
            if(mp[u][j]){
                int w=mp[u][j];
                if(dis[j]>dis[u]+w){
                    dis[j]=dis[u]+w;
                    heap.push({dis[j],j});
                }
            }
        }
    }
}
signed main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        int tmp=mp[u][v]?mp[u][v]:N;//重边
        mp[u][v]=min(tmp,w);
    }dij(n,s);
    for(int i=1;i<=n;i++){
        if(dis[i]==N)cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}*/
//十进制转n进制
/*#include <iostream>
using namespace std;
void m(int a,int b){
    if(a==0){
        return;
    }
    m(a/b,b);
    if(a%b<=9)cout << a%b;
    else cout << char(a%b+'A'-10);
}
int main(){
    int a,b;
    cin >> a >> b;
    m(a,b);
}*/
//p进制转十进制

/*#include <bits/stdc++.h>
using namespace std;
#define int long long
int p;
string b;
vector<char> a;
signed main(){
    cin >> p;//65
    cin >> b;
    for(int i=b.size()-1;i>=0;i--){
        a.push_back(b[i]);
    }int ans;
    for(int i=0;i<=a.size()-1;i++){
        if(a[i]>='A' and a[i]<='Z'){
            a[i]-=55;
        }else a[i]-='0';
        ans+=(int)pow(p,i)*a[i];
    }cout << ans;
    return 0;
}  */ 

//大根堆STL
/*#include <bits/stdc++.h>
using namespace std;
priority_queue<int> heap;//大根堆
int main(){
    int x;
    heap.top();//取堆顶元素
    heap.pop();//删除堆顶元素
    heap.push(x);//将元素 x 插入堆
    heap.size();//堆的大小
    heap.empty();//判空
    return 0;
}*/
//重组运算符
/*struct node{
    int x,y;
    friend bool cmp<(node a,node b){
        if(a.x==b.x) return a.y>b.y;
        return a.x>b.x;
    }
}a[15];
sort(a+1,a+n+1);
*/
//高精度加法
/*#include <bits/stdc++.h>
using namespace std;
int a[10086],b[10086],c[10086];
string n,m;
void And(string n,string m){
    int ln=n.size(),lm=m.size();
    for(int i=0;i<ln;i++){
        a[i]=n[ln-i-1]-'0';
    }for(int i=0;i<lm;i++){
        b[i]=m[lm-i-1]-'0';
    }int l=max(ln,lm),jw=0;
    for(int i=0;i<l;i++){
        c[i]=b[i]+a[i]+jw;
        if(c[i]>9){  
            c[i]-=10;
            jw=1;
        }else jw=0;
    }if(jw)cout << 1;
    for(int i=0;i<l;i++)cout << c[l-i-1];
}
int main(){
    cin >> n >> m;
    And(n,m);
    return 0;
}*/
//高精度减法
/*#include <bits/stdc++.h>
using namespace std;
int a[10086],b[10086],c[10086];
string n,m;
void sub(string n,string m){
    int ln=n.size(),lm=m.size();
    for(int i=0;i<ln;i++)a[i]=n[ln-i-1]-'0';
    for(int i=0;i<lm;i++)b[i]=m[lm-i-1]-'0';
    int l=max(ln,lm),jw=0;
    for(int i=0;i<l;i++) {
        c[i]=a[i]-b[i]-jw;
        if(c[i]<0){
            c[i]+=10;
            jw=1;
        }else jw=0;
    }while(l>1 and c[l-1]==0)l--;
    for(int i=l-1;i>=0;i--)cout << c[i];
}
int main() {
    cin >> n >> m;
    if(n.size()<m.size() or n.size()==m.size() and n<m){
        swap(n,m);
        cout << "-";
    }
    sub(n,m);
    return 0;
}*/
//并查集
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m;
struct FA{
    int fa[N],h[N];
    int find(int x){
        if(fa[x]==x)return x;
        else return fa[x]=find(fa[x]);
    }void merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        if(h[y]<h[x])swap(x,y);
        if(h[x]==h[y])h[y]=h[x]+1;
        fa[y]=x;
    }void init(int n){
        for(int i=1;i<=n;i++)fa[i]=i,h[i]=1;
    }
};
signed main(){
    cin >> n >> m;
    FA fa;
    fa.init();
    while(m--){
        int op,x,y;
        cin >> op >> x >> y;
        if(op==1){
            fa.merge(x,y);
        }else{
            cout << (fa.find(x)==fa.find(y)?"Y\n":"N\n");
        }
    }
    return 0;
}*/

//快读快写
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int x=0,f=1;
    int ch=getchar();
    while(ch<'0' or ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }while(ch>='0' and ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }return x*f;
}
void write(int x){
    if(x==0){
        putchar('0');
        return ;
    }if(x<0){
        putchar('-');
        x=-x;
    }if(x>9)write(x/10);
    putchar(x%10+'0');
}
signed main(){
    int n;
    n=read();
    write(n);
    return 0;
}*/
//哈希表
/*#include <bits/stdc++.h>
using namespace std;
const int N=1e7+19; 
struct Hash{
	int h[N];//哈希表
	int e[N],ne[N],idx=0; //链表的东西
	void push(int x){ 
		int hsh=(x%N+N)%N;
		e[idx]=x;
		ne[idx]=h[hsh];
		h[hsh]=idx++;
		return;
	}bool find(int x){ 
		int hsh=(x%N+N)%N;
		for(int i=h[hsh];i!=-1;i=ne[i])
			if(e[i]==x)return true; 
		return false;
	}void init(){        
		for(int i=1;i<=N;i++)h[i]=-1; //初始化，让h中的初始值都为-1
		return;
	}
};
int main(){
    return 0;
}*/
//手写小根堆
/*#include <bits/stdc++.h>
using namespace std;
struct Heap{
    int heap[100005],siz=0;
    void push(int x){
        int son,pa;
        heap[++siz]=x;
        son=siz;
        while(son>1){
            pa=son/2;
            if(heap[pa]<=heap[son])break;
            swap(heap[pa],heap[son]); 
            son=pa;
        }
    }int top(){
        return heap[1];
    }
    void pop(){
        int pa,son;
        heap[1]=heap[siz--];
        pa=1;
        while(pa*2<=siz){
            son=2*pa;
            if(son<siz and heap[son+1]<heap[son])son++;
            if(heap[pa]<=heap[son])break;
            swap(heap[pa],heap[son]);
            pa=son;
        }
    }int size(){
        return siz;
    }bool empty(){
        return !siz; 
    }
};
int main(){
    Heap heap;
    return 0;
}*/
//大根堆手写
/*#include <bits/stdc++.h>
using namespace std;
struct Heap{
    int heap[100005],siz=0;
    void push(int x){
        int son,pa;
        heap[++siz]=x;
        son=siz;
        while(son>1){
            pa=son/2;
            if(heap[son]<=heap[pa])break;
            swap(heap[pa],heap[son]); 
            son=pa;
        }
    }int top(){
        return heap[1];
    }
    void pop(){
        int pa,son;
        heap[1]=heap[siz--];
        pa=1;
        while(pa*2<=siz){
            son=2*pa;
            if(son<siz and heap[son]<heap[son+1])son++;
            if(heap[son]<=heap[pa])break;
            swap(heap[pa],heap[son]);
            pa=son;
        }
    }int size(){
        return siz;
    }bool empty(){
        return !siz; 
    }
};
int main(){
    Heap heap;
    return 0;
}*/
//BST二叉搜索树
/*#include <bits/stdc++.h>
#define int long long
const int INF=0x7fffffff;
const int N=1000010;
using namespace std;
int cont;
struct BST{
    int vals[N],siz[N],cnt[N],ls[N],rs[N];
    void push(int x,int v){//插入
        siz[x]++;
        if(vals[x]==v){
            cnt[x]++;
            return ;
        }if(vals[x]>v){
            if(ls[x]!=0)
                push(ls[x],v);
            else{
                cont++;
                vals[cont]=v;
                siz[cont]=cnt[cont]=1;
                ls[x]=cont;
            }
        }else{
            if(rs[x]!=0)
              push(rs[x],v);
            else{
                cont++;
                vals[cont]=v;
                siz[cont]=cnt[cont]=1;
                rs[x]=cont;
            }
        }
    }
    int queryfr(int x,int val,int ans){//找前驱
        if (vals[x]>=val){
            if(ls[x]==0)return ans;
            else return queryfr(ls[x],val,ans);
        }else{
            if(rs[x]==0)return vals[x];
            return queryfr(rs[x],val,vals[x]);
        }
    }
    int queryne(int x, int val, int ans) {//找后继
        if(vals[x]<=val){
            if(rs[x]==0)return ans;
            else return queryne(rs[x],val,ans);
        }else{
            if(ls[x]==0)return vals[x];
            return queryne(ls[x],val,vals[x]);
        }
    }
    int queryrk(int x,int rk){//按排名找值
        if(x==0)return INF;
        if(siz[ls[x]]>=rk)return queryrk(ls[x],rk);
        if(siz[ls[x]]+cnt[x]>=rk)return vals[x];
        return queryrk(rs[x],rk-siz[ls[x]]-cnt[x]);
    }
    int queryval(int x,int val){//按值找排名
        if(x==0)return 0;
        if(val==vals[x]) return siz[ls[x]];
        if(val<vals[x]) return queryval(ls[x],val);
        return queryval(rs[x],val)+siz[ls[x]]+cnt[x];
    }
};
int n,opt,xx;
signed main(){
    BST bst;
    cin >> n;
    while(n--){
        cin >> opt >> xx;
        if(opt==1) printf("%lld\n",bst.queryval(1,xx)+1);
        else if(opt==2) printf("%lld\n",bst.queryrk(1,xx));
        else if(opt==3) printf("%lld\n",bst.queryfr(1,xx,-INF));
        else if(opt==4) printf("%lld\n",bst.queryne(1,xx,INF));
        else{
            if(cont==0){
                cont++;
                bst.cnt[cont]=bst.siz[cont]=1;
                bst.vals[cont]=xx;
            }
            else bst.push(1,xx);
        }
    }
    return 0;
}*/
//链式前向星
/*#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Edge{
    int head[N],cnt;
    int next[N],to[N],w[N];
    void add(int u,int v,int w1){
        to[++cnt]=v;          // 表示新边的节点
        w[cnt]=w1;           // 边权
        next[cnt]=head[u];   // 新节点指向 u 的链表的链头
        head[u]=cnt;         // 新节点作为新的链头
    }int sum(int n){//统计所有边权重之和，可以参考作为遍历的基本代码
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=head[i];j;j=next[j]){
                ans+=w[j];
            }
        }return ans;
    }void tvl(int x){
        for(int j=head[x];j;j=next[j]){
            cout << to[j] << " " << w[j] << endl;
        }
    }void init(){
        memset(head,0,sizeof(head));
        cnt=0; 
    }
};
signed main(){ 
    Edge edge;
    return 0;
}  */