首页 > 代码库 > NWERC 2013 - J (codeforces gym - 100405J)
NWERC 2013 - J (codeforces gym - 100405J)
题目描述：给你一颗二叉树，保证每个点要么是叶子节点，要么有左右两个儿子。某些叶子节点上放着灯，请你移动最少的灯，使得整棵树平衡
对平衡的定义：对于树上的每个点左右儿子中灯数的差的绝对值≤1，那么这棵树平衡。总灯数sum≤1000.
解题思路：题目中强调的是移动，不能往里面添加，也不能从树中拿走。这个移动操作就给我们造成了一些困难，起初想一些dp的方法，感觉都不是很靠谱。
于是看了官方题解，题解中用了一步巧妙地转化，然后递归求解，很有借鉴意义。
首先对于移动操作次数最少，我们可以转化成，往树里插入sum个点，尽量把点放入本来有灯的位置，最大覆盖多少个的问题。那么原来没有灯，现在要放点，这些位置的个数就是答案。
完成这一步转化之后就要挖掘题目性质，绝对值差1这个性质十分重要，因为这近似于一步二分，也就是如果我们从顶点开始递归地往下放，那么最多进行logSUM层就能使得剩下的 可放点数达到0或1，这就使我们得到一种很可行的分治求解的方法：Get(x, cnt)表示向x这个点插入cnt个灯，向空点放的情况最少有多少个（也就是移动次数最少有多少次）。对于cnt是偶数的情况，就直接Get(x.left, cnt >> 1), Get(x.right, cnt >> 1), 而对于cnt是奇数，就要讨论一下左右放多放少这两种情况，取个min了。
递归的终止条件：①cnt == 0，返回0 ②x == 0 && cnt > 0返回INF（无解）③cnt == 1 子树中本来有灯返回1，无灯返回0
P.S.题目中并没有给总点数，经过分析总点数不会超过叶子节点的二倍。但是题目读入比较繁琐，字符串长度要开至少4000。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 8 const int MaxN = 3000; 9 const int INF = 2000;10 struct Node {11 int left, right, father;12 int cLoc, cOn;13 }tree[MaxN + 5];14 int n, tot, ans;15 char s[MaxN * 2 + 5];16 17 void Init()18 {19 memset(tree, 0, sizeof(tree));20 int len = strlen(s);21 int p = 0; n = 0;22 for (int i = 0; i < len; i++) {23 if (s[i] == ‘(‘) {24 if (tree[p].left == 0) tree[p].left = ++n;25 else tree[p].right = ++n;26 tree[n].father = p;27 p = n;28 }29 else if (s[i] == ‘B‘) {30 tree[p].cOn = 1;31 tree[p].cLoc = 1;32 p = tree[p].father;33 i++;34 }35 else {36 int L = tree[p].left;37 int R = tree[p].right;38 tree[p].cOn = tree[L].cOn + tree[R].cOn;39 tree[p].cLoc = tree[L].cLoc + tree[R].cLoc;40 if (tree[p].cLoc == 0) tree[p].cLoc = 1;41 p = tree[p].father;42 }43 }44 //for (int i = 1; i <= n; i++) printf("%d %d %d\n", i, tree[i].cOn, tree[i].cLoc);45 }46 47 int Get(int x, int cnt)48 {49 if (cnt == 0) return 0;50 if (x == 0) return INF;51 if (cnt == 1) return (int)(tree[x].cOn == 0);52 if (cnt & 1) {53 int cL1 = Get(tree[x].left, cnt >> 1);54 int cR1 = Get(tree[x].right, cnt - (cnt >> 1));55 int cL2 = Get(tree[x].left, cnt - (cnt >> 1));56 int cR2 = Get(tree[x].right, cnt >> 1);57 return min(cL1 + cR1, cL2 + cR2);58 }59 else {60 int cL = Get(tree[x].left, cnt >> 1);61 int cR = Get(tree[x].right, cnt >> 1);62 return cL + cR;63 }64 }65 66 int main()67 {68 while (~scanf("%s", s)) {69 Init();70 ans = Get(1, tree[1].cOn);71 if (ans >= INF) printf("impossible\n");72 else printf("%d\n", ans);73 }74 }
NWERC 2013 - J (codeforces gym - 100405J)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。