又是一道非常水的普及 T4，直接按照题目意思算就好了。
题意解读
给你一个二叉树，让你找其中最大的对称二叉树的节点数。
对称二叉树，简单来说就是以中间一条线轴对称的二叉树。
思路
首先非常好想，暴力遍历正个数，以每个节点为根，和其所有后代构成的二叉树，然后判断这棵树是否是对称二叉树，算出其节点数。最后找到最大的输出就好了。
时间复杂度分析
一眼 $ O(n^2) $，抱着必死的想法测试大样例，跑了 2s 多一点。我一看，没想到这机子跑这么快啊，然后加了个输入输出优化，没想跑到了 0.4s 的优秀成绩……
我当时就傻眼了。什么时候 $ O(n^2) $ 能跑过 1e6 了。这怕不会是老师把机子换成了 神威·太湖之光 吧……
后来，经过思考，发现：
虽然看起来是 $ O(n^2) $， 但祂实际上是 $O(nlogn)$的。
对于一棵满二叉树，我们从每个节点出发遍历这个结点的子树。
对于第一层的结点，子树大小为 $O(n)$，只有一个结点，所以时间是$O(n)$。
对于第二层的结点，子树大小 $O(\frac{n}{2})$，有两个结点，时间开销仍然是 $O(\frac{n}{2}) * 2 = O(n)$。
类似地，从任何一层出发遍历的时间都是 $O(n)$。
而树一共只有 $O(logn)$ 层。所以总时间复杂度是 $O(n) * O(logn) = O(nlogn)$
如果不是满二叉树，会因为不对称更早退出搜索，时间开销更低。
AC 记录
洛谷神鸡最慢才 176ms, 比 400ms 可快多了。
所以得出不是这机子跑得快，相比与洛谷神鸡，完全就是个垃圾。
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, v[N], l[N], r[N], maxans;
bool check(int x, int y)
{
if (1ll * x * y < 0)
return 0;
if (x == -1)
return 1;
if (v[x] != v[y])
return 0;
return check(l[x], r[y]) && check(r[x], l[y]);
}
int find(int x)
{
int ans = 1;
if (l[x] != -1)
ans += find(l[x]);
if (r[x] != -1)
ans += find(r[x]);
return ans;
}
void dfs(int x)
{
if (check(l[x], r[x]))
maxans = max(maxans, find(x));
if (l[x] != -1)
dfs(l[x]);
if (r[x] != -1)
dfs(r[x]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++)
cin >> l[i] >> r[i];
dfs(1);
cout << maxans;
}
|
暴力出奇迹！！！
