APIO2007风铃

题目解答

题目的程序实现并不困难,算法整体也相当容易,主要的坎坷就是考虑问题的全面性。事实上,题目的很多限定让程序的实现更接近DP,所以我们可以借助树状DP的思想来分析题目。首先我们按照程序实现的顺序逐一分析:

  1. 不合法:分析题目,最大层次只能差1,因而这是一个完全二叉树,所以凡是不满足的均要输出-1;当左右子树的节点深度差均为1时,也不可能满足,输出-1.
  2. 在合法的前提下:计数需要几种情况:
    1. 右子树的节点深度差值为1,则向右迭代转化为子问题,不计数。
    2. 左子树的最小深度浅于右子树的最大深度,向左迭代,计数。
    3. 不满足2的情况下,如果左子树自身的深度不一样,向左迭代,不计数。
      以上3条就包含所有情况了。
  3. 对于深度,只需记录一个子树的最浅和最深即可,用DFS可以很简单的得到。

运行情况

APIO 2007 - 风铃

程序清单

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
#include<iostream>
#include<cmath>
#define BIG 100005
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;

long dp[BIG][2],dep[BIG][2],n,tot,ult;

bool deep(int index,int lev){
if(lev>ult) return 0;
if(index==0) {
dep[index][0]=dep[index][1]=1;
return 1;
}
if(!deep(dp[index][0],lev+1)) return 0;
if(!deep(dp[index][1],lev+1)) return 0;
int l=dp[index][0],r=dp[index][1];
dep[index][0]=MAX(dep[l][0],dep[r][0])+1;
dep[index][1]=MIN(dep[l][1],dep[r][1])+1;
return 1;
}

bool work(int index){
//如果不成立
if(dep[dp[index][0]][0]-dep[dp[index][0]][1]>0 && dep[dp[index][1]][0]-dep[dp[index][1]][1]>0){
tot=-1;
return 0;
}
//左子树需要旋转
if(dep[dp[index][0]][1] < dep[dp[index][1]][0]){
tot++;
if(!work(dp[index][0])) return 0;
} else if(dep[dp[index][0]][1] < dep[dp[index][0]][0])
if(!work(dp[index][0])) return 0;

//右子树需要旋转
if(dep[dp[index][1]][1] < dep[dp[index][1]][0])
if(!work(dp[index][1])) return 0;

return 1;
}

int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>dp[i][0]>>dp[i][1];
if(dp[i][0]==-1) dp[i][0]++;
if(dp[i][1]==-1) dp[i][1]++;
}

ult=(int)log2(n)+2;
if(!deep(1,1)) {
cout<< -1 << endl;
return 0;
}
if(dep[1][0]-dep[1][1]>1) {
cout<< -1 << endl;
return 0;
} else work(1);
cout<< tot << endl;
return 0;
}

注意事项

考虑要全面。

难易等级

Middle Up(提高+/省选-)