P3621 [APIO2007] 风铃
题目描述
你准备给弟弟 Ike 买一件礼物，但是，Ike 挑选礼物的方式很特别：他只喜欢那些能被他排成有序形状的东西。
你准备给 Ike 买一个风铃。风铃是一种多层的装饰品，一般挂在天花板上。
每个风铃都包含一些由竖直线连起来的水平杆。每根杆的两头都有线连接，下面或者挂着另一根水平杆，或者挂着一个玩具。下面是一个风铃的例子：
为了满足弟弟，你需要选一个满足下面两个条件的风铃：
风铃可以按照下面的规则重新排列：任选一根杆，将杆两头的线“交换”。也就是解开一根杆左右两头的线，然后将它们绑到杆的另一头。这个操作不会改变更下面的杆上线的排列顺序。
正在训练信息学奥林匹克的你，决定设计一个算法，判断能否通过重新排列，将一个给定的风铃变为 Ike 喜欢的样子。
考虑上面的例子，上图中的风铃满足条件
1
1
1，却不满足条件
2
2
2 ——最左边的那个玩具比它右边的要高。
但是，我们可以通过下面的步骤把这个风铃变成一个 Ike 喜欢的：
1
1
1 的左右两边交换，这使得杆
2
2
2 和杆
3
3
3 的位置互换，交换的结果如下图所示：
2
2
2 的左右两边交换，这使得杆
4
4
4 到了左边，原来在左边的玩具到了右边，交换的结果发下图所示：
现在的这个风铃就满足 Ike 的条件了。
你的任务是：给定一个风铃的描述，求出最少需要多少次交换才能使这风铃满足 Ike 的条件(如果可能)。
输入格式
输入的第一行包含一个整数
n
n
n，表示风铃中有多少根杆。
接下来的
n
n
n 行描述杆的连接信息。这部分的第
i
i
i 行包含两个由空格分隔的整数
l
i
l_i
li 和
r
i
r_i
ri，描述杆
i
i
i 的左右两边悬挂的东西。如果挂的是一个玩具，则对应的值为-1，否则为挂在下面的杆的编号。
输出格式
输出仅包含一个整数。表示最少需要多少次交换能使风铃满足 Ike 的条件。如果不可能满足，输出-1。
输入输出样例 #1
输入 #1
6
2 3
-1 4
5 6
-1 -1
-1 -1
-1 -1
输出 #1
2
说明/提示
数据规模与约定
- 对于
100
%
100\\%
100% 的数据，满足1
≤
n
≤
10
5
1 \\le n \\le 10^5
1≤n≤105，−
1
≤
l
i
,
r
i
≤
n
-1 \\leq l_i, r_i \\leq n
−1≤li,ri≤n，l
i
,
r
i
≠
0
l_i, r_i \\neq 0
li,ri=0。
C++实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5, inf = 0x3f3f3f3f;
int n, son[N][2], mi = inf, ma, ans;
void dfs(int u, int k) {
if(u == –1)
return (mi=min(mi, k)), (ma=max(ma, k)), void();
dfs(son[u][0], k+1);
dfs(son[u][1], k+1);
}
int dfs2(int u, int k) {
if(u == –1) return (k != mi);
int x = dfs2(son[u][0], k+1);
int y = dfs2(son[u][1], k+1);
ans += ((!x && y) || (x == 2 && y == 1));
if(x == 2 && y == 2) exit((puts("-1"), 0));
if(x == 2 || y == 2 || x + y == 1) return 2;
if(!(x + y)) return 0;
return 1;
}
int main() {
scanf("%d", &n);
for(int i=1;i<=n;i++)
scanf("%d%d", &son[i][0], &son[i][1]);
dfs(1, 0);
if(ma – mi > 1)
return puts("-1"), 0;
if(ma == mi)
return puts("0"), 0;
int _ = dfs2(1, 0);
printf("%d\\n", ans);
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
