题意
一二题题解 :传送门
百度之星复赛第三题题意 传送门
中文题意,自己看吧
比赛的时候看错了题意,一直没想出,赛后补题
思路
就是按照规律进行中序遍历,情况有点多所以你得分类讨论
先预处理出
每个节点的作为根节点的树的最小节点下标是多少
每个节点的作为根节点的树的节点数是多少
然后我们开始中序遍历
如果两边都有节点,找比当前节点小的最小节点的一边
如果两边的最小节点都比当前节点大那么找,节点数最小的一边遍历
如果只有一边节点,判断这一边的最小节点是否比当前节点小,是则先遍历
AC_code:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135/* Algorithm: 中序遍历 Author: anthony1314 Creat Time: Time Complexity: */ #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <bitset> #include <stack> #include <cmath> #include <deque> #include <queue> #include <list> #include <set> #include <map> #define line printf("---------------------------n") #define mem(a, b) memset(a, b, sizeof(a)) #define pi acos(-1) using namespace std; typedef long long ll; typedef double db; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int maxn = 1e5+5; void add(int &x, int y) { x = (x + y) % mod; } vector<int> node[maxn]; int tot; bool ma[maxn];// 0为根节点 1不为根节点 int mr[maxn], ans[maxn], sz[maxn];//子树最小的节点 每个节点的标号 以该节点为根节点的树 的节点数 int dfs1(int root) { sz[root] = 1; int minroot = maxn+5; for(int i = 0; i < node[root].size(); i++) { int u = node[root][i]; minroot = min(minroot, dfs1(u)); sz[root] += sz[u]; } mr[root] = minroot; return min(root, minroot); } void dfs2(int root) { // cout<<node[root].size()<<endl; if(node[root].size() == 1 && min(node[root][0], mr[node[root][0]]) > root) { ans[root] = ++tot; dfs2(node[root][0]); return; } else if(node[root].size() == 2 && min(node[root][0], mr[node[root][0]]) > root && min(node[root][1], mr[node[root][1]]) > root) { if(sz[node[root][0]] == sz[node[root][1]]) { if(min(node[root][0], mr[node[root][0]]) > min(node[root][1], mr[node[root][1]])) { dfs2(node[root][1]); ans[root] = ++tot; dfs2(node[root][0]); } else { dfs2(node[root][0]); ans[root] = ++tot; dfs2(node[root][1]); } } else if(sz[node[root][0]] > sz[node[root][1]]) { dfs2(node[root][1]); ans[root] = ++tot; dfs2(node[root][0]); } else { dfs2(node[root][0]); ans[root] = ++tot; dfs2(node[root][1]); } return; } for(int i = 0; i < node[root].size(); i++) { if(mr[root] == min(node[root][i], mr[node[root][i]])) { dfs2(node[root][i]); } } ans[root] = ++tot; for(int i = 0; i < node[root].size(); i++) { if(mr[root] != min(node[root][i], mr[node[root][i]])) { dfs2(node[root][i]); } } } ll slove(int n) { ll u = 233LL; ll ret = 0; for (ll i = 1; i <= n; i++) { // cout<<ans[i]<<endl; ret = (ret + (((i ^ ans[i]) % mod) * u) % mod) % mod; u = (u * 233LL) % mod; } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t, n, u, v; cin>>t; while(t--) { tot = 0; cin>>n; for(int i = 0; i <= n; i++) node[i].clear(), ma[i] = 0, sz[i] = 0;//初始化 for(int i = 1; i <= n; i++) { cin>>u>>v; if(u != 0) node[i].push_back(u); if(v != 0) node[i].push_back(v); ma[u] = 1; ma[v] = 1; } int root; for(int i = 1; i <= n; i++) { if(ma[i] == 0) { root = i; break; } } dfs1(root);//预处理 遍历出深度和最小节点 dfs2(root);//中序遍历 cout<<slove(n)<<endl; } return 0; }
最后
以上就是幸福大炮最近收集整理的关于hdu6727 Quasi Binary Search Tree 【2019百度之星复赛】【中序遍历】【dfs】的全部内容,更多相关hdu6727内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复