http://acm.hdu.edu.cn/showproblem.php?pid=4409

賽后才過只能說悲劇了，知道思路，stl不熟悉，所以導致寫的很慢....占據了很多時間，手速+代碼準確度。。哎。。。

題意：

給你一個家譜，n個人的姓名，姓名前邊的點代表了他是第幾代人。每個人的祖先肯定在他之前出現。有三種操作：

L：輸出這個家族的序列，不是按層數，而是遞歸的輸出，還要保證字典序升序；

b name 輸出name的兄弟個數，注意這里堂兄弟不算：

c name1 name2 求name1 name2的最近公共祖先。

思路：

首先我用set建圖這樣就能保證L輸出時按字典序輸出，mp用來進行映射，rmq+lca求最近公共祖先，這里注意的是如果x,y的lca等于x或者y就要輸出lca的父親才是他們的LCA。還有如果訪問Mr.X的兄弟的話要輸出1.

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x))#define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 100007 #define N 30007 using namespace std; //freopen("din.txt","r",stdin); map<string,int>mp; set<string>st[N];int pos[N];//點為i的編號 int bro[N];//記錄i的兄弟數int E[N << 1],D[N << 1],R[N],dp[N << 1][30];//rmq+lcachar strT[N][66]; int pow2[32],pa[N];//記錄i點的父節點 int n,top;void dfs(int u,int h){E[++top] = u;D[top] = h;R[u] = top;set<string>::iterator it;for(it = st[u].begin(); it != st[u].end(); ++it){int v = mp[*it];dfs(v , h+1);E[++top] = u;D[top] = h;}return; } int Min(int i,int j){if (D[i] < D[j]) return i;else return j; }//rmq的初始化 void init_rmq() {for (int i = 0; i < 30; ++i) pow2[i] = 1<<i;for(int i = 1;i <= top; ++i){dp[i][0] = i;}for(int j = 1; pow2[j] <= top; ++j){for(int i = 1; (i + pow2[j] - 1) <= top; ++i){dp[i][j] = Min(dp[i][j-1],dp[i + (1 << (j-1))][j-1]);}}return; }int rmq(int l,int r){int d = log((double)(r - l + 1)) / log(2.0);return Min(dp[l][d],dp[r - pow2[d] + 1][d]); } //L順序輸出，這里set直接排序了 void dfspath(int u){set<string>::iterator it;for (it = st[u].begin(); it != st[u].end(); it++){int v = mp[*it];printf("%s\n",strT[v]);dfspath(v);} } int main(){// freopen("din.txt","r",stdin);int i,j;while (~scanf("%d",&n)){if (!n) break;CL(pos,0); mp.clear();for (i = 0; i <= n; ++i) st[i].clear();for (i = 0; i < n; ++i){scanf("%s",strT[i]);//找點的個數int tmpnum = 0;int sz = strlen(strT[i]);for (j = 0; j < sz; ++j){if (strT[i][j] == '.') tmpnum++;else break;}//點為tmpnum的編號pos[tmpnum] = i;string s;for (; j < sz; ++j){s.push_back(strT[i][j]);}//cout<<strT[i]<<"*********"<<s<<endl;mp[s] = i;//建立映射關系if (tmpnum != 0){st[pos[tmpnum - 1]].insert(s);pa[i] = pos[tmpnum - 1];//記錄該節點的父親節點 }}CL(bro,0);set<string>::iterator it;for (i = 0; i < n; ++i){//printf("%d %s>>\n",i,strT[i]);int sz = st[i].size();for (it = st[i].begin(); it != st[i].end(); ++it){int tmp = mp[*it];//cout<<tmp<<endl;bro[tmp] = sz;//統計兄弟數量 }}bro[0] = 1;//這里很容易錯，注意要初始化//for (i = 1; i < n; ++i) printf(">>%d %d\n",i,bro[i]);//lca+rmq的過程top = 0;dfs(0,0);init_rmq();char op[3];int q;scanf("%d",&q);while (q--){scanf("%s",op);string tmps;if (op[0] == 'L'){printf("%s\n",strT[0]);dfspath(0);}else if (op[0] == 'b'){cin>>tmps;int posn = mp[tmps];printf("%d\n",bro[posn]);}else{string s1,s2;int lca;cin>>s1>>s2;int x = mp[s1];int y = mp[s2];if (R[x] <= R[y]) lca = E[rmq(R[x],R[y])];else lca = E[rmq(R[y],R[x])];if (lca == x || lca == y) lca = pa[lca];//注意這里的處理int t;int L = strlen(strT[lca]);for (t = 0; t < L; ++t){if (strT[lca][t] != '.') printf("%c",strT[lca][t]);}printf("\n");}}}return 0; }

?

?

?

總結

以上是生活随笔為你收集整理的hdu 4409 Family Name List LCA +stl的全部內容，希望文章能夠幫你解決所遇到的問題。

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