解题思路

本题要求用训练样本（m 个二值特征，标签为 0/1）构建一个二叉决策树（ID3），再对 q 个查询样本进行预测。 核心要点：

1. 划分准则：使用信息增益（Entropy + Information Gain）。

   • 节点样本集合 $S$ 的熵 $H(S)=-\sum p_i\log_2 p_i$（二分类时就是看 0/1 的占比）。
   • 选择尚未使用的特征 $f$ 进行二分（按 0/1 分到 $S_0,S_1$），条件熵为 $H(S|f)=\frac{|S_0|}{|S|}H(S_0)+\frac{|S_1|}{|S|}H(S_1)$，

题目内容

通过分析基站的关键性能指标（如信息强度，干扰水平，用户数量等）。可以预测网络是否处于正常状态（标签0）或劣化状态（标签1）.决策树算法因其直观的判断逻辑和快速的响应能力，被广泛应用于无线网络智能运维场景。

给定一组基站性能特征数据和对应的网络质量标签，请实现一个基于信息增益的决策树分类器。用于判断网络质量是否劣化。信息熵定义为：

信息熵 = 划分前熵 - 划分后条件熵

特殊情况处理：

• 当多个特征对应的信息增益相等时，优先选择索引较小的特征进行样本划分；
• 当没有特征对样本进一步划分时，该节点预测为样本数较多的标签（若标签0和标签1数量一致，则默认该节点预测为0）。

输入描述

第一行：整数 $n \ (1 \leq n \leq 1000)$，表示训练样本数量，整数 $m \ (2 \leq m \leq 10)$ 表示特征数。

接下来 $n$ 行，每行包含 $m + 1$ 个整数，前 $m$ 个是特征 1 ~ 特征 $m$ 对应的特征值（取值为 0 或 1），最后一个是要预测的标签（ 0 或 1）。

下一行，整数 $q (1 \le q \le 100)$，表示查询样本数量。

接下来 $q$ 行，每行包括 $m$ 个整数，表示查询样本的特征值 (0 或 1)。

输出描述

输出 $q$ 行，每行为一个整数（0或1），表示对应查询样本的预测类别。

样例1

输入

10 3
1 0 1 1
1 0 0 0
1 1 1 1
1 1 0 1
0 0 1 0
0 0 0 0 
0 1 1 1
0 1 0 0
1 0 1 1
0 1 1 1 
3
1 0 1
0 0 0 
1 1 0

输出

1
0
1

说明

数据包含 $10$ 个样本，每个样本包含三个特征。基于训练数据，可以构建出如下决策树：

样例2

输入

6 2
1 1 1
0 0 0 
1 0 1
0 1 0
1 1 1
0 0 0 
2 
1 1 
0 0

输出

1
0

说明

训练数据包含 $6$ 个样本，每个样本包含两个特征(特征 $1$ 和特征 $2$ )，构建得到的决策树如下：

原始信息熵：$-1/2$ $log(1/2)-1/2log(1/2)=1$

使用特征 $1$ 进行划分后：信息熵 $=1log(1)=0$ ，增益为 $1$

使用特征 $2$ 进行划分后：信息熵 $=0.5×0.9183+0.5×0.9183=0.9183$，增益为 $0.0817$