句容市建设工程管理处网站,wordpress联系表格,网站模板源代码下载,公司推广网站建设话术http://acm.hdu.edu.cn/showproblem.php?pid4409 赛后才过只能说悲剧了#xff0c;知道思路#xff0c;stl不熟悉#xff0c;所以导致写的很慢....占据了很多时间#xff0c;手速代码准确度。。哎。。。 题意#xff1a; 给你一个家谱#xff0c;n个人的姓名#xff0c…http://acm.hdu.edu.cn/showproblem.php?pid4409 赛后才过只能说悲剧了知道思路stl不熟悉所以导致写的很慢....占据了很多时间手速代码准确度。。哎。。。 题意 给你一个家谱n个人的姓名姓名前边的点代表了他是第几代人。每个人的祖先肯定在他之前出现。有三种操作 L输出这个家族的序列不是按层数而是递归的输出还要保证字典序升序 b name 输出name的兄弟个数注意这里堂兄弟不算 c name1 name2 求name1 name2的最近公共祖先。 思路 首先我用set建图这样就能保证L输出时按字典序输出mp用来进行映射rmqlca求最近公共祖先这里注意的是如果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,rt1
#define rc m 1,r,rt1|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);mapstring,intmp;
setstringst[N];int pos[N];//点为i的编号
int bro[N];//记录i的兄弟数int E[N 1],D[N 1],R[N],dp[N 1][30];//rmqlcachar 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;setstring::iterator it;for(it st[u].begin(); it ! st[u].end(); it){int v mp[*it];dfs(v , h1);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] 1i;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){setstring::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]);}//coutstrT[i]*********sendl;mp[s] i;//建立映射关系if (tmpnum ! 0){st[pos[tmpnum - 1]].insert(s);pa[i] pos[tmpnum - 1];//记录该节点的父亲节点}}CL(bro,0);setstring::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];//couttmpendl;bro[tmp] sz;//统计兄弟数量}}bro[0] 1;//这里很容易错注意要初始化//for (i 1; i n; i) printf(%d %d\n,i,bro[i]);//lcarmq的过程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){cintmps;int posn mp[tmps];printf(%d\n,bro[posn]);}else{string s1,s2;int lca;cins1s2;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;
}
