10410 这题说的是给了一棵多叉树的 bfs遍历轨迹 和dfs 遍历 轨迹 在父节点向叶子节点扩展的时候优先遍历编号较小的节点。我还原出这课树特殊判定
根据bfs的顺序来建立这课树，用一个队列安排要构造的这课子树 条件是这棵树拥有孩子节点，判定这个点的下一层孩子ij(i<j)节点之间的在dfs中 的间隔节点 将这些点分配给i节点因为可以知道这些节点肯定是i的孩子节点或者孙子节点 如果这些在dfs中 间 隔 的 节 点 个 数 大 于 0 就 把 i 点 推 入 队 列 当 中 （ 因 为 i 节 点有孩子节点） 这样不断的去构造这棵树的子树，还有就是当一层当中只有一个节点的时候且这个节点的编号比孩子节点来得大的时候这样就得特判 因为像我那样就直接将他们归为一层了要进行特判的条件他们有同样的祖先且前者大于后者这样后者就一定是前者的孩子而不可能是后者的兄弟节点
#include <string.h> #include <cstdio> #include <iostream> #include <vector> #include <queue> using namespace std; const int maxn = 1005; vector<int> map[maxn]; int dfs[maxn],bfs[maxn],n; int locdfs[maxn],locbfs[maxn],per[maxn]; int work(int a, int b){ int num = 0; for( int i = locdfs[a]+1 ; i<n; ++ i ){ if( per[dfs[i]] != per[a] || dfs[i] == b )break; per[dfs[i]] = a; num++; } return num; } void solve(){ queue<int>Q; Q.push(dfs[0]); while(!Q.empty()){ int t = Q.front(); Q.pop(); int start = locdfs[t] + 1; int F = locbfs[dfs[start]]; for( int i = F ; i <n ; i++ ){ int t1 = bfs[i],t2 = bfs[i+1]; if(per[t1]!=t)break; if(t1>t2){ int num=work(t1,0); if(num>0) Q.push(t1); map[t].push_back(t1); break; } int num = work(t1,t2); if(num>0) Q.push(t1); map[t].push_back(t1); } } } int main(){ while( scanf("%d",&n) == 1 ){ for(int i = 1 ; i <= n ; ++ i) map[i].clear(); for(int i = 0 ; i < n ; ++ i){ scanf("%d",&bfs[i]); locbfs[bfs[i]] = i ; } bfs[n] = 0; for(int i = 0 ; i < n ; ++ i){ scanf("%d",&dfs[i]); locdfs[dfs[i]] = i ; } dfs[n] = 0; for( int i =1 ; i <=n ; ++ i) per[i] = dfs[0]; solve(); for( int i = 1 ; i <= n ; ++ i){ printf("%d:",i); for( int j = 0 ; j <map[i].size() ; ++ j ) printf(" %d",map[i][j]); printf(" "); } } return 0; } /* 4 3 5 1 2 8 6 7 9 10 4 3 1 7 10 2 6 9 5 8 */
10895 这题比较简单说的是给了一个矩阵然后转置后输出
#include <cstdio> #include <string.h> #include <iostream> #include <queue> using namespace std; const int maxn=10005; struct node{ int column,value; node(int a=0 ,int b= 0 ){ column = a; value = b; } bool operator <(const node &A)const{ return column>A.column; } }T[maxn]; priority_queue<node>ans[2][maxn]; int main(){ int n,m; while(scanf("%d%d",&n,&m)==2){ for( int i = 1 ; i <= n ; ++ i ) while(!ans[0][i].empty())ans[0][i].pop(); for( int i = 1; i <= m ; ++i ) while(!ans[1][i].empty())ans[1][i].pop(); for( int i=1 ;i <= n ; i++){ int num; scanf("%d",&num); for( int j = 0 ; j < num ; ++ j) scanf("%d",&T[j].column); for( int j = 0 ; j< num ; ++ j) scanf("%d",&T[j].value); for( int j= 0 ; j< num ; ++ j) ans[0][i].push(T[j]); } for( int i = 1 ; i <=n ; ++ i ){ while(!ans[0][i].empty()){ node t = ans[0][i].top(); ans[0][i].pop(); ans[1][t.column].push(node(i,t.value)); } } printf("%d %d ",m,n); for( int i = 1 ; i <= m ; i++ ){ int num = ans[1][i].size(); for( int j = 0 ; j< num ; j++){ T[j]=ans[1][i].top(); ans[1][i].pop(); } printf("%d",num); for( int j = 0 ; j < num ; ++ j){ printf(" %d",T[j].column); } printf(" "); if(num>0){ for( int j = 0 ; j < num-1 ; ++ j) printf("%d ",T[j].value); printf("%d",T[num-1].value); } printf(" "); } } return 0; }