Solve

APIO2007风铃

题目解答

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

  1. 不合法：分析题目，最大层次只能差1，因而这是一个完全二叉树，所以凡是不满足的均要输出-1；当左右子树的节点深度差均为1时，也不可能满足，输出-1.
  2. 在合法的前提下：计数需要几种情况：
  3. 右子树的节点深度差值为1，则向右迭代转化为子问题，不计数。
  4. 左子树的最小深度浅于右子树的最大深度，向左迭代，计数。
  5. 不满足2的情况下，如果左子树自身的深度不一样，向左迭代，不计数。
    以上3条就包含所有情况了。
  6. 对于深度，只需记录一个子树的最浅和最深即可，用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(提高+/省选-)