hihocoder 1490.Tree Restoration

260

微软2017年预科生计划在线编程笔试
原题链接:http://hihocoder.com/problemset/problem/1490?sid=1299846
题目看上去很麻烦,先看样例
第一行:节点数N,层数M,叶子数K
第二行:M个数,表示每层的节点数A[I]
接下来M行,每行A[I]个数,表示该层节点编号B[I][j](从左到右顺序)
然后是一行K个数,表示叶子的编号
最后K×K的矩阵表示叶子间距离D[I][j]


根据两个节点间的距离,可以得知两个节点是否是同一个节点的子节点(距离为1)
由于给了节点顺序,因此我们只需要贪心地往左面的节点连接子节点即可

因此,问题转换成判断同一层相邻两个节点间的距离是否为2
如果为2,则接到同一个节点;否则,接到上一层的下一个非叶子节点上

至于距离,可以找到该节点下面的任意一个叶子节点,用这个叶子节点到目标的值减去层数差即可

#include <cstdio>
#include <cstring>
using namespace std;

#define Log(format, ...) //printf(format, ##__VA_ARGS__)

const int maxn = 105;

int nodeNum[maxn];
int nodeIdx[maxn][maxn];
int leaves[maxn];
bool isLeaf[maxn];
int dis[maxn][maxn];

int parents[maxn];
int child[maxn];
int delta[maxn];

int findAndUpdateLastNode(int &lastNode, int &lastNodeIdx, int deep,
int nowIdx) {
// 查找并更新上一层的第一个有孩子的节点
for (int k = lastNode+1; k < nodeNum[deep - 1]; ++k) {
if (!isLeaf[nodeIdx[deep - 1][k]]) {
lastNode = k;
break;
}
}
lastNodeIdx = nodeIdx[deep - 1][lastNode];

child[lastNodeIdx] = child[nowIdx];
delta[lastNodeIdx] = delta[nowIdx] + 1;

return lastNode;
}

int main() {
memset(parents, 0, sizeof(parents));
memset(isLeaf, false, sizeof(isLeaf));
memset(delta, 0, sizeof(delta));
memset(parents, 0, sizeof(parents));
memset(delta, 0, sizeof(delta));

int N, M, K;
scanf("%d%d%d", &N, &M, &K);
for (int i = 0; i < M; ++i)
scanf("%d", &nodeNum[i]);
for (int i = 0; i < M; ++i)
for (int j = 0; j < nodeNum[i]; ++j)
scanf("%d", &nodeIdx[i][j]);
for (int i = 0; i < K; ++i) {
scanf("%d", &leaves[i]);
isLeaf[leaves[i]] = true;
child[leaves[i]] = i;
}
for (int i = 0; i < K; ++i)
for (int j = 0; j < K; ++j)
scanf("%d", &dis[i][j]);

Log("input ok\n");

for (int i = M - 1; i > 0; --i) { // 处理第i层
Log("\tdepth:%d\n", i);
int lastNode = -1;
int lastNodeIdx = -1;

for (int j = 0; j < nodeNum[i]; ++j) { // 处理当前层的第j个节点
int nowIdx = nodeIdx[i][j]; // 当前节点的编号
Log("\t\tnowIdx:%d\n", nowIdx);
if (lastNode == -1) {
// 处理第一个节点
findAndUpdateLastNode(lastNode, lastNodeIdx, i, nowIdx);
parents[nowIdx] = lastNodeIdx;
} else {
int preNodeIdx = nodeIdx[i][j - 1];
Log("\t\t\tpreNodeIdx:%d\n", preNodeIdx);

int distance = dis[child[nowIdx]][child[preNodeIdx]] -
delta[nowIdx] - delta[preNodeIdx];
Log("\t\t\tdistance:%d dis:%d(%d %d) del:%d %d\n", distance,
dis[child[nowIdx]][child[preNodeIdx]], child[nowIdx],
child[preNodeIdx], delta[nowIdx], delta[preNodeIdx]);
if (distance == 2) {
parents[nowIdx] = lastNodeIdx;
} else {
findAndUpdateLastNode(lastNode, lastNodeIdx,
i, nowIdx);
parents[nowIdx] = lastNodeIdx;
}
}
Log("\t\t\tlastNode:%d LastNodeIdx:%d\n", lastNode, lastNodeIdx);
}
}
for (int i = 1; i <= N; ++i) {
printf("%d ", parents[i]);
}
printf("\n");
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论