本文共 3210 字，大约阅读时间需要 10 分钟。
赛后才过只能说悲剧了，知道思路，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.
#include #include #include #include #include #include #include #include #include #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 30007using namespace std;//freopen("din.txt","r",stdin);map mp;set 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 ::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< <= 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 ::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< <<"*********"< < ::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< < >%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;}
转载于:https://www.cnblogs.com/E-star/archive/2012/09/22/2698260.html
View Code