这道题目要求我们通过天平称重来确定七个砝码的真实重量，每个砝码上贴有数字标签（1到7），但标签与重量可能不匹配。我们需要利用天平称重的结果（左重、平衡、右重）来推断每个标签对应的实际重量，且称重次数应尽可能少。

问题分析

• 有七个砝码，重量分别为1、2、3、4、5、6、7公斤，但标签是随机贴的。
• 每次称重时，我们可以将砝码放在左托盘、右托盘或不放（但必须至少放一个砝码）。
• 称重结果有三种：左重（-1）、平衡（0）、右重（1）。
• 目标是通过称重确定每个标签对应的重量，并提交答案。

解决方案思路

给出的C++代码采用了一种预计算决策树的方法，确保在最多9次称重内解决任何测试用例。以下是核心步骤：

1. 生成所有可能的重量排列：

   • 由于7个砝码的重量是1~7的排列，总共有7! = 5040种可能排列。代码中生成所有排列并存储在perms数组中。

2. 生成所有可能的称重操作：

   • 称重操作由两个位掩码S和T表示，其中S指定放在左托盘的砝码，T指定放在右托盘的砝码。S和T不能重叠，且S <= T以避免重复（因为左右对称的操作等价）。
   • 总操作数量为(2^7 - 1) * (2^7 - 1)，但通过条件过滤后实际可用操作较少。

3. 预计算每个操作的结果：

   • 对于每个操作(S, T)和每个排列，计算称重结果（左重、平衡、右重）。
   • 使用位集res[i][j]存储操作i下结果j对应的排列集合。
   • 筛选出“有用”的操作（uop），即那些称重结果分布较均匀的操作（三个结果集合的大小差不超过3000），以确保每次称重能有效缩小搜索空间。

4. 构建决策树：

   • 使用递归函数build构建决策树，给定当前可能的排列集合和剩余深度（最大为9），尝试选择最优操作使得递归后每个子问题都能在深度内解决。
   • 使用哈希值标识排列集合，并将集合映射到操作索引存储在cho中，以便运行时快速查找。

5. 交互执行：

   • 对于每个测试用例，函数calc使用预计算的决策树进行称重：
     • 如果当前排列集合只有一个元素，直接提交答案。
     • 否则，计算当前集合的哈希值，从cho中获取对应操作，执行称重（先取下所有砝码，再按操作放置）。
     • 根据称重结果更新排列集合，递归调用calc直到唯一确定排列。

代码关键点

• 效率优化：通过预计算和决策树，将每次称重视为三叉树的分支，确保最坏情况下9次称重内解决。
• 操作筛选：只使用结果分布均匀的操作，避免无效称重。
• 哈希映射：使用随机哈希快速标识排列集合，减少运行时计算。

性能保证

• 代码保证在每个测试用例中最多使用9次称重，满足子任务1的满分要求（R ≤ 9）。
• 决策树的构建深度为9，确保任何情况下都能在9步内完成。

使用示例

在样例中，程序通过3次称重完成第一组测试（标签正确），并通过预计算决策树处理第二组测试（标签混乱）。交互库模拟称重过程，程序根据结果动态调整可能排列。

总结

该方案通过预计算所有可能状态和操作，构建了一个高效决策树，使得在运行时能以最优称重次数解决问题。这种方法确保了在最坏情况下的性能，适用于大规模测试数据。