データ構造POJ 2431 Expedition二叉樹で、POJ 1182の食物連鎖を調べます.

一山の実現

int heap[MXN],sz=0;
void push(int x){
    int i=sz++;//       
    while(i>0){
        int p=(i-1)/2;//       
        if(heap[p]<=x)break;//             
        heap[i]=heap[p];//       ,     
        i=p;
    }
    heap[i]=x;
}
int pop(){
    int ret=heap[0];//   
    int x=heap[--sz];//       
    int i=0;//        
    while(i*2+1<sz){
        int a=i*2+1,b=i*2+2;//      
        if(b<sz&&heap[b]<heap[a]) a=b;
        if(heap[a]>=x) break;//             
        heap[i]=heap[a];//         
        i=a;
    }
    heap[i]=x;
    return ret;
}

二.POJ 2431 Expedition
乳牛たちは先ほど森でトラックを奪った.乳牛たちの運転技術があまり高くないので、トラックのガソリンタンクが吹っ飛んでしまいました.現在のガソリンタンクの中にP(1≦P≦1,000,000)単位のガソリンがあります.走行単位ごとにガソリンタンクは一つの単位のガソリンを失います.一番近い町はここからL(1≦L≦1,000,000)の単位があります.今道路にN(1≦N≦10,000)のガソリンスタンドがあります.ガソリンスタンドには二つの情報があります.一つは町からの距離で、二つはガソリンスタンドからのガソリン量です.今はガソリンタンクの容量が無限です.ガソリンスタンドは必ず供給できるガソリンを全部供給します.乳牛たちはジャングルの中は危険だと思い、町に届くように、できるだけ少ないガソリンスタンドにとどまることにしました.乳牛たちは少なくともいくつかのガソリンスタンドに停まります.もし彼らが町に着けないなら、出力は-1です.
解法:燃料が0の場合、最大のガソリンスタンドを選択します.

int L,P,N,M;
int A[MXN+1],B[MXN+1];
void Fun(){
    A[N]=L;
    B[N]=0;
    N++;
    priority_queue<int> que;
    int ans=0,pos=0,tank=P;
    for(int i=0;i<N;++i){
        int d=A[i]-pos;
        while(tank-d<0){
            if(que.empty()){
                puts("-1");
                return ;
            }
            tank+=que.top();
            que.pop();
            ans++;
        }
        tank-=d;
        pos=A[i];
        que.push(B[i]);
    }
    printf("%d
",ans);
}

三.二叉樹実現

struct node{
    int val;
    node *lch,*rch;
};

node *insert(node *p,int x){
    if(p==NULL){
        node* q=new node;
        q->val=x;
        q->lch=q->rch=NULL;
        return q;
    }
    else{
        if(x<p->val) p->lch=insert(p->lch,x);
        else p->rch=insert(p->rch,x);
        return p;
    }
}
bool find(node *p,int x){
    if(p==NULL) return false;
    else if(x==p->val) return true;
    else if (x<p->val) return find(p->lch,x);
    else return find(p->rch,x);
}
node *remove(node *p,int x){
    if(p== NULL)  return NULL;
    else if(x<p->val) p->lch=remove(p->lch,x);
    else if(x>p->val) p->rch=remove(p->rch,x);
    else if(p->lch==NULL){
        node *q=p->rch;
        delete p;
        return q;
    }
    else if(p->lch->rch==NULL){
        node *q=p->lch;
        q->rch=p->rch;
        delete p;
        return q;
    }
    else{
        node *q;
        for(q=p->lch;q->rch->rch!=NULL;q=q->rch);
        node *r=q->rch;
        q->rch=r->lch;
        r->lch=p->lch;
        r->rch=p->rch;
        delete p;
        return r;
    }
    return p;
}
node *root=NULL;
root=insert(root,1);
find(root,1);

セットを使う

int main(){
    set<int> s;
    s.insert(3);
    set<int>::iterator ite;
    ite=s.find(1);
    if(ite==s.end()) puts("not found");
    s.erase(3);
    if(s.count(3)!=0) puts("found");
}

mapを使う

int main(){
    map<int,const char *> m;
    m.insert(make_pair(1,"ONE"));
    m.insert(make_pair(10,"TEN"));
    m[10]="TEd";
    map<int,const char*>::iterator ite;
    ite=m.find(1);
    puts(ite->second);
    m.erase(1);
}

四.まとめて調べる

int par[MXN];//  
int rank[MXN];//    

void init(int n){
    for(int i=0;i<n;++i){
        par[i]=i;
        rank[i]=0;
    }
}
int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return ;
    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}

五.POJ 1182食物連鎖
件名:
動物王国には3種類の動物A、B、Cがあります.この3種類の動物の食物連鎖は面白いリングを構成しています.AはB、BはC、CはAを食べます.N個の動物がいます.1－Nで番号を付けます.どの動物もA、B、Cの中の一つですが、どれなのか分かりません.
このN個の動物からなる食物連鎖の関係を二つの言い方で説明する人がいます.
一つ目の言い方は「1 X Y」で、XとYが同類であることを表します.
二番目の言い方は「2 X Y」で、XがYを食べることを表します.
この人はN個の動物に対して、上記の2つの言い方を使って、次から次へとK文を言い出して、このK文の話はあるのは本当で、あるのはにせものです.一つの言葉が次の三つを満たす時、この言葉は嘘です.そうでなければ真実です.
1)今の話が前の話と衝突するというのは嘘です.
2)今の話ではXかYがNより大きいというのが嘘です.
3)今の話はXを食べるということを表しています.
あなたの任務は与えられたN(=N==50,000)とK文(0==K==100,000)に基づいて嘘の総数を出力することです.
解法:
各動物iは3つの元素i-A、i-B、i-Cを作成します.
i-xはiが種類xに属することを表しています.そして、検索集の各グループはグループ内の要素を表しています.または同時に発生しません.
(1)xとyは同じ種類で、x-Aとy-Aを結合し、x-Bとy-Bを結合し、x-Cとy-Cを結合する.
(2)xはyを食べて、x-Aとy-Bを合併して、x-Bとy-Cを合併して、x-Cとy-Aを合併します.

int N,K;
int T[MXK],X[MXK],Y[MXK];
void Fun(){
    init(N*3);//  x,x+N,X+2*N    x-A,x-B,x-C
    int ans=0;
    for(int i=0;i<K;++i) {
        int t=T[i];
        int x=X[i]-1,y=Y[i]-1;//    0,...,N-1  
        if(x<0||N<=x||y<0||N<=y){
            ans++;
            continue;
        }
        if(t==1){
            if(same(x,y+N)||same(x,y+2*N)){//         (x-A,y-B) (x-A,y-C)
                ans++;
            }
            else{
                unite(x,y);
                unite(x+N,y+N);
                unite(x+N*2,y+N*2);
            }
        }
        else{
            if(same(x,y)||same(x,y+2*N)){//           ,         
                ans++;
            }
            else{
                unite(x,y+N):
                unite(x+N,y+2*N);
                unite(x+2*N,y);
            }
        }
    }
    printf("%d
",ans);
}