题目分析

题意简述

给定一个大小为 $2^k\times2^k$（$2\leq k\leq20$）的二维非负整数数组，构建一个标签树。标签树中每个节点的值 $q(t, i, j)$ 是其四个子节点 $q(t + 1, 2i, 2j)$、$q(t + 1, 2i, 2j + 1)$、$q(t + 1, 2i + 1, 2j)$ 和 $q(t + 1, 2i + 1, 2j + 1)$ 的最小值。为每个节点关联一个初始值为 $0$ 的升级值 $c(t, i, j)$，按照特定规则对标签树进行编码，编码从顶层节点开始，在父节点编码完成后才能编码子节点。编码时，若 $c(t, i, j)<q(t, i, j)$ 输出 $0$ 并将 $c(t, i, j)$ 加 $1$，若 $c(t, i, j)=q(t, i, j)$ 输出 $1$。编码一个节点后，更新其后代节点的升级值。要求计算对输入数组构建的标签树进行编码所需的总比特数。

输入

• 第一行输入一个正整数 $N$（$N\leq10$），表示测试用例的数量。
• 对于每个测试用例：
  • 第一行输入一个整数 $k$，表示数组大小为 $2^k\times2^k$。
  • 接下来的 $2^k$ 行，每行包含 $2^k$ 个非负整数，构成二维数组。

输出

对于每个测试用例，输出一行，为对该输入数组构建的标签树进行编码所需的总比特数。

解题思路

构建标签树

从最底层的二维数组开始，逐层向上计算每个节点的值，每个节点的值为其四个子节点的最小值。

计算编码比特数

在构建标签树的过程中，对于每个节点，根据其四个子节点的值和该节点的值计算编码所需的比特数。具体来说，计算四个子节点的值与该节点最小值的差值之和，再加上 $4$，即为该节点编码所需的比特数。

汇总结果

将所有节点编码所需的比特数相加，再加上顶层节点的值加 $1$，得到最终的编码总比特数。

代码实现

#include <iostream>
#include <stdio.h>
using namespace std;

int data[2048][2048];

int mn(int a, int b){
    return (a<b) ? a  : b;
}

int mn4(int a, int b, int c, int d){
    return mn(mn(a, b), mn(c,d));
}

int main() {
    int t;
    scanf("%d", &t);
    for(int ii = 0; ii < t; ii++){
        int k;
        scanf("%d", &k);
        int K = (1 << k);
        for(int i = 0; i < K; i++){
            for(int j = 0; j < K; j++){
                scanf("%d", &data[i][j]);
            }
        }
        int cnt = 0;
        for(int q = 0; q < k; q++){
            K /= 2;
            for(int i = 0; i < K; i++){
                for(int j = 0; j < K; j++){
                    int mnn = mn4(data[2*i][2*j], data[2*i][2*j+1], data[2*i+1][2*j], data[2*i+1][2*j+1]);
                    cnt += (data[2*i][2*j]+data[2*i][2*j+1]+data[2*i+1][2*j]+data[2*i+1][2*j+1]-4*mnn+4);
                    data[i][j] = mnn;
                }
            }
        }
        printf("%d\n", cnt + data[0][0] + 1);
    }
    return 0;
}

代码说明

1. 全局变量：
   • data[2048][2048]：用于存储二维数组和标签树节点的值。
2. 函数功能：
   • mn(int a, int b)：返回 $a$ 和 $b$ 中的较小值。
   • mn4(int a, int b, int c, int d)：返回 $a$、$b$、$c$、$d$ 中的最小值。
3. 主函数流程：
   • 读取测试用例的数量 $t$。
   • 对于每个测试用例：
     • 读取 $k$，计算数组大小 $K = 2^k$。
     • 读取二维数组的元素，存储在 data 数组中。
     • 初始化编码比特数计数器 $cnt$ 为 $0$。
     • 进行 $k$ 次循环，每次将数组大小 $K$ 减半，构建标签树的上一层节点：
       • 对于当前层的每个节点，计算其四个子节点的最小值 $mnn$。
       • 计算该节点编码所需的比特数，累加到 $cnt$ 中。
       • 将该节点的值更新为 $mnn$。
     • 输出最终的编码总比特数，即 $cnt + data[0][0] + 1$。