1 条题解
-
0
时间复杂度分析
这段代码的时间复杂度主要由以下几个部分组成:
-
枚举所有可能的4元素子集:从16个元素中选择4个元素的组合数为C(16,4) = 1820种。
-
生成每个子集的全排列:每个4元素子集有4! = 24种排列方式。
-
哈希表操作:对于每个排列,计算其加权和并检查是否存在互补的子集,时间复杂度为O(1)。
-
最终计数阶段:遍历所有可能的16位二进制数,时间复杂度为O(2^16) = O(65536)。
综合以上分析,代码的总时间复杂度为:
- 组合生成:C(16,4) = 1820
- 排列生成:4! = 24
- 哈希表操作:O(1)
- 最终计数:O(2^16)
总时间复杂度约为 O(C(16,4) × 4! × 2^16) = O(1820 × 24 × 65536) ≈ 2.8 billion 次操作,在现代计算机上可以接受。
解题思路
这段代码通过巧妙的分治策略和位运算来解决天平平衡问题,主要思路如下:
-
问题分解:
- 将16个数字分成左右两组,每组8个数字。
- 每组再进一步分解为两个4元素子集,分别对应天平方程的左侧和右侧。
-
预处理阶段:
- 枚举所有4元素子集:生成所有可能的4元素子集,并计算每个子集的所有排列。
- 计算加权和:对于每个排列,计算其加权和(如x14 + x23 + x3*2 + x4)。
- 哈希表存储:使用哈希表(vector数组)记录每个加权和对应的所有4元素子集状态。
-
组合匹配阶段:
- 检查互补子集:对于每个4元素子集,检查是否存在另一个不相交的4元素子集,使得它们的加权和相等。
- 位运算优化:使用位运算快速判断两个子集是否不相交,并记录所有可能的8元素组合。
-
最终计数:
- 对称性处理:通过位运算枚举所有可能的8元素组合,并统计互补对的数量。
- 去重处理:最终结果除以2,消除重复计数。
代码关键逻辑解析
-
judge函数:
- 检查一个二进制状态是否恰好包含4个元素。
-
solve函数:
- 预处理阶段:枚举所有可能的4元素子集,生成每个子集的所有排列,并计算其加权和。
- 哈希表存储:将每个排列的加权和作为键,对应的子集状态作为值存入哈希表。
- 组合匹配:遍历每个排列,检查哈希表中是否存在不相交的子集,使得它们的加权和相等。
- 最终计数:统计所有互补对的数量,并处理对称性。
-
main函数:
- 读取输入数据,调用solve函数计算结果,并输出。
这种方法通过分治和哈希表大大减少了计算量,有效解决了原问题中的组合爆炸问题。
C++代码
#include <stdio.h> #include <string.h> #include <vector> #include <algorithm> using namespace std; int num[16], st[16], Sum[(1<<16)]; vector<int> sum[22222]; bool judge(int state) { int sn = 0; for (int i = 0; i < 16; i++) { if (state&(1<<i)) st[sn++] = num[i]; } if (sn == 4) return true; return false; } int solve() { int ans = 0; memset(sum, 0, sizeof(sum)); memset(Sum, 0, sizeof(Sum)); sort(num, num + 16); for (int i = 0; i < (1<<16); i++) { if (judge(i)) { do { int s = st[0] * 4 + st[1] * 3 + st[2] * 2 + st[3]; for (int j = 0; j < sum[s].size(); j++) { if ((i&sum[s][j]) == 0) Sum[(i|sum[s][j])]++; } sum[s].push_back(i); } while(next_permutation(st, st + 4)); } } for (int k = 0; k < (1<<16); k++) ans += Sum[k] * Sum[k^((1<<16)-1)]; return ans / 2; } int main() { int cas = 0; while (~scanf("%d", &num[0]) && num[0]) { for (int i = 1; i < 16; i++) scanf("%d", &num[i]); printf("Case %d: %d\n", ++cas, solve()); } return 0; }
-
- 1
信息
- ID
- 2140
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者