http://poj.org/problem?id=2892

此代碼在POJ上能過 在hdu上過不了

題目大意：

n個村莊相連? 三種操作

D 摧毀一個村莊

Q 查詢包括此村莊在內和此村莊直接和間接相連的村莊數

R 修復上一個被摧毀的村莊

Ttree 寫的很爛呀

思路：

將摧毀的村莊插入二叉樹中

每次詢問 就查找它左邊和右邊最近被摧毀的村莊 就可以知道答案了

修復一個村莊 就把它在樹中刪除

代碼及其注釋：

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<queue> #include<algorithm> #include<stack>using namespace std;const int N=50010; struct node {int k;int l,r,f; }mem[N]; int destroy[N];//是否被摧毀 int treehead,n;//頭結點 和村莊個數 stack<int>str;//保存被摧毀的村莊 void RightTurn(int i)//右轉 {int f=mem[i].f;int l=mem[i].l;if(f==-1){mem[l].f=-1;treehead=l;}else{if(mem[f].l==i)mem[f].l=l;elsemem[f].r=l;mem[l].f=f;}mem[i].l=mem[l].r;if(mem[l].r!=-1)mem[mem[l].r].f=i;mem[l].r=i;mem[i].f=l; } void LeftTurn(int i)//左轉 {int f=mem[i].f;int r=mem[i].r;if(f==-1){mem[r].f=-1;treehead=r;}else{if(mem[f].l==i)mem[f].l=r;elsemem[f].r=r;mem[r].f=f;}mem[i].r=mem[r].l;if(mem[r].l!=-1)mem[mem[r].l].f=i;mem[r].l=i;mem[i].f=r; } void insert(int i,int k)//插入 {if(k<i){if(mem[i].l!=-1){insert(mem[i].l,k);if(mem[mem[i].l].k<mem[i].k){RightTurn(i);}}else{mem[i].l=k;mem[k].f=i;}}else{if(mem[i].r!=-1){insert(mem[i].r,k);if(mem[mem[i].r].k<mem[i].k){LeftTurn(i);}}else{mem[i].r=k;mem[k].f=i;}} } void dele(int i,int k)//刪除 {if(i<k){dele(mem[i].r,k);}else if(i>k){dele(mem[i].l,k);}else{int x=i;while(mem[x].l!=-1||mem[x].r!=-1){if(mem[x].l!=-1){RightTurn(x);}else{LeftTurn(x);}}if(mem[x].f==-1){treehead=-1;return;}if(mem[mem[x].f].l==x)mem[mem[x].f].l=-1;if(mem[mem[x].f].r==x)mem[mem[x].f].r=-1;} } void LeastLeft(int i,int k,int *L)//求最近左被摧毀村莊 {if(i==-1){return;}if(k<=i){LeastLeft(mem[i].l,k,L);}else if(k>i){*L=max(*L,i);LeastLeft(mem[i].r,k,L);}} void LeastRight(int i,int k,int *R)//求最近右被摧毀村莊 {if(i==-1){return;}if(k<i){*R=min(*R,i);LeastRight(mem[i].l,k,R);}else if(k>=i){LeastRight(mem[i].r,k,R);} } void begin()//初始化一些內容 {while(!str.empty())str.pop();memset(destroy,0,sizeof(destroy));treehead=-1; } int main() {int m;while(scanf("%d %d",&n,&m)!=EOF){begin();char c;int i;for(int k=1;k<=m;++k){getchar();scanf("%c",&c);if(c=='D'){scanf("%d",&i);mem[i].l=mem[i].r=-1;mem[i].k=k;if(treehead==-1)//如果樹是空的 {treehead=i;mem[i].f=-1;}else{insert(treehead,i);//否則 插入 }str.push(i);++destroy[i];//記錄}else if(c=='Q'){int ans,L,R;scanf("%d",&i);if(destroy[i]>0)//特殊情況 {ans=0;}else{L=0;LeastLeft(treehead,i,&L);R=n+1;LeastRight(treehead,i,&R);ans=R-L-1;}printf("%d\n",ans);}else{if(str.empty())continue;dele(treehead,str.top());//刪點 并記錄--destroy[str.top()];str.pop();}}}return 0; }

?

轉載于:https://www.cnblogs.com/liulangye/archive/2012/07/15/2592365.html

總結

以上是生活随笔為你收集整理的poj 2892 Tunnel Warfare的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。