hihocoder 1490.Tree Restoration
visibility 61
微软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;
}

评论
email
点击查看/关闭被识别为广告的评论

#