头像

BUPT-Spider


访客:904

离线:8分钟前



BUPT-Spider
18小时前

伸展树声明和初始化

//北京邮电大学 计算机学院 Spider

#ifndef _Splay_H

struct SplayNode;
typedef struct SplayNode *SplayTree;

SplayTree MakeEmpty(SplayTree T);
SplayTree Find(ElementType X, SplayTree T);
SplayTree FindMin(SplayTree T);
SplayTree FindMax(SplayTree T);
SplayTree Initialize(void);
SplayTree Insert(ElementType X, SplayTree T);
SplayTree Remove(ElementType X, SplayTree T);
ElementType Retrieve(SplayTree T);

#endif

struct SplayNode
{
    ElementType Element;
    SplayTree Left;
    SplayTree Right;
};

typedef struct SplayNode *Position;
static Position NullNode = NULL;

SplayTree Initialize(void)
{
    if(NullNode == NULL)
    {
        NullNode = malloc(sizeof(struct SplayNode);
        if(NullNode == NULL)
            FatalError("Out of space!!!");
        NullNode->Left = NullNode->Right = NullNode;
    }
    return NullNode;
}



分享 AVL树

AVL树相关代码

#ifndef _AvlTree_H

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType X, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
AvlTree Delete(ElementType X, AvlTree T);
ElementType Retrieve(Position P);

#endif /*_AvlTree_H*/

/*Place in the implementation file*/
struct AvlNode
{
    ElementType Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
};

//calculate the height
static int Height(Position P)
{
    if(P == NULL) return -1;
    else return P->Height;
}

AvlTree Insert(ElementType X, AvlTree T)
{
    if(T == NULL)
    {
        /*Create and return a one-node tree*/
        T = malloc(sizeof(struct AvlNode));
        if(T == NULL) FatalError("Out of space!!!");
        else
        {
            T->Element = X;
            T->Height = 0;
            T->Left = T->Right = NULL;
        }
    }
    else if(X < T->Element)
    {
        T->Left = Insert(X, T->Left);
        if(Height(T->Left) - Height(T->Right) == 2)
        {
            if(X < T->Left->Element) T = SingleRotateWithLeft(T);
            else T = DoubleRotateWithLeft(T);
        }
        else if(X > T->Element)
        {
            T->Right = Insert(X, T->Right);
            if(Height(T->Right - Height(T->Left) == 2)
            {
                if(X > T->Right->Element) T = SingleRotateWithRight(T);
                else T = DoubleRotateWithRight(T);
            }
        }
    }
    /*Else X is in the tree already; we'll do nothing*/

    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}

static Position SingleRotateWithLeft(Position K2)
{
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;

    return K1;
}

static Position DoubleRotateWithLeft(Position K3)
{
    K3->Left = SingleRotateWithRight(K3->Left);

    return SingleRotateWithLeft(K3);
}




分享 再散列

再散列代码实现

HashTable Rehash(HashTable H)
{
    int i,OldSize;
    Cell *OldCells;

    OldCells=H->TheCells;
    OldSize=H->TableSize;

    /*Get a new,empty table*/
    H=InitializeTable(2*OldSize);

    /*Scan through old table,reinserting into new*/
    for(i=0;i<OldSize;i++)
        if(OldCells[i].Info==Legitimate)
            Insert(OldCells[i].Element,H);

    free(OldCells);

    return H;
}



C++代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=10010;

int msize,n,m;
int h[N];

bool is_prime(int x)
{
    if(x==1) return false;

    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}//is_prime

int main(void)
{
    scanf("%d%d%d",&msize,&n,&m);
    for(int i=msize;;i++)
    {
        if(is_prime(i)) 
        {
            msize=i;
            break;
        }
    }

    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);

        int index=x%msize;
        if(h[index])
        {
            int j;
            for(j=1;j<msize;j++)
            {
                int index_=index+j*j;
                if(index_>=msize) index_%=msize;

                if(!h[index_])
                {
                    h[index_]=x;
                    break;
                }
            }
            if(j==msize) printf("%d cannot be inserted.\n",x);
        }
        else h[index]=x;
    }

    int sum=0;
    for(int i=0;i<m;i++)
    {
        int x;
        scanf("%d",&x);

        int j;
        for(j=0;j<msize;j++)
        {
            int index=x%msize+j*j;
            if(index>=msize) index%=msize;
            if(h[index]==x||!h[index]) break;
        }
        sum+=j+1;
    }
    printf("%.1f\n",sum*1.0/m);

    return 0;
}




BUPT-Spider
1个月前

C++代码

//双链表
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;

int e[N],l[N],r[N],idx;

void init()
{
    r[0]=1,l[1]=0,idx=2;
}//init

void add(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}//add

void remove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}//remove

int main(void)
{
    int m;
    cin>>m;

    init();

    while(m--)
    {
        string op;
        cin>>op;

        int k,x;

        if(op=="L")
        {
            cin>>x;
            add(0,x);
        }
        else if(op=="R")
        {
            cin>>x;
            add(l[1],x);
        }
        else if(op=="D")
        {
            cin>>k;
            remove(k+1);
        }
        else if(op=="IL")
        {
            cin>>k>>x;
            add(l[k+1],x);
        }
        else 
        {
            cin>>k>>x;
            add(k+1,x);
        }
    }

    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<' ';
    cout<<endl;

    return 0;
} 





BUPT-Spider
1个月前

C++代码

#include<iostream>

using namespace std;

const int M=1e5+10;

int m;
int head,e[M],ne[M],idx;

void init()
{
    idx=0;
    head=-1;
}//init

void add_to_head(int x)
{
    e[idx]=x,ne[idx]=head,head=idx++;
}//add_to_head

void remove(int k)
{
    ne[k]=ne[ne[k]];
}//remove

void add(int k,int x)
{
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}//add

int main(void)
{
    init();

    cin>>m;
    while(m--)
    {
        int k,x;

        char op;
        cin>>op;
        switch(op)
        {
            case 'H':
                cin>>x;
                add_to_head(x);
                break;
            case 'D':
                cin>>k;
                if(!k) head=ne[head];
                remove(k-1);
                break;
            case 'I':
                cin>>k>>x;
                add(k-1,x);
                break;
        }
    }

    for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<' ';
    cout<<endl;

    return 0;
}




BUPT-Spider
1个月前

C++代码

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=110;

int n,t;
bool g[N][N];
bool st[N][N];
pair<int,int> match[N][N];

bool find(int x,int y)
{
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

    for(int i=0;i<4;i++)
    {
        int cur_x=x+dx[i],cur_y=y+dy[i];

        if(cur_x>=1&&cur_x<=n&&cur_y>=1&&cur_y<=n&&
            !g[cur_x][cur_y]&&!st[cur_x][cur_y])
        {
            st[cur_x][cur_y]=true;

            if(match[cur_x][cur_y].first==0||
                find(match[cur_x][cur_y].first,match[cur_x][cur_y].second))
            {
                match[cur_x][cur_y]={x,y};
                return true;
            }
        }
    }

    return false;
}//find

int main(void)
{
    scanf("%d%d",&n,&t);
    while(t--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x][y]=true;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            match[i][j]={0,0};

    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(((i+j)%2==1)&&!g[i][j])
            {
                memset(st,false,sizeof st);
                if(find(i,j)) res++;
            }

    printf("%d\n",res);

    return 0;
}







BUPT-Spider
1个月前

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N=1e5+10;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N],cnt[N];
bool vis[N];

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx,w[idx]=c;
    idx++;
}//add

int spfa()
{   
    queue<int> q;

    for(int i=1;i<=n;i++)
    {
        q.push(i);
        vis[i]=true;
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();

        vis[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;

                if(cnt[j]>=n) return true;

                if(!vis[j])
                {
                    q.push(j);
                    vis[j]=true;
                }
            }
        }
    }
    return false;
}//spfa

int main(void)
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    if(spfa()) puts("Yes");
    else puts("No");

    return 0;
}



BUPT-Spider
1个月前

C++代码

//spfa
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N=1e5+10;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool vis[N];

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx,w[idx]=c;
    idx++;
}//add

int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    queue<int> q;
    q.push(1);
    vis[1]=true;

    while(q.size())
    {
        int t=q.front();
        q.pop();

        vis[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!vis[j])
                {
                    q.push(j);
                    vis[j]=true;
                }
            }
        }
    }

    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}//spfa

int main(void)
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    int res=spfa();
    if(res==-1) puts("impossible");
    else printf("%d\n",res);

    return 0;
}



BUPT-Spider
1个月前

C++代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=210,INF=1e9;;

int n,m,k;
int d[N][N];

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}//floyd

int main(void)
{
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;

    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        d[a][b]=min(d[a][b],w);
    }

    floyd();

    while(k--)
    {
        int a,b;
        cin>>a>>b;

        if(d[a][b]>INF/2) puts("impossible");
        else cout<<d[a][b]<<endl;
    }

    return 0;
}