1 条题解

  • 0
    @ 2025-5-29 20:54:05

    时间复杂度分析

    这段代码的时间复杂度主要由以下几个部分组成:

    1. 枚举所有可能的4元素子集:从16个元素中选择4个元素的组合数为C(16,4) = 1820种。

    2. 生成每个子集的全排列:每个4元素子集有4! = 24种排列方式。

    3. 哈希表操作:对于每个排列,计算其加权和并检查是否存在互补的子集,时间复杂度为O(1)。

    4. 最终计数阶段:遍历所有可能的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 次操作,在现代计算机上可以接受。

    解题思路

    这段代码通过巧妙的分治策略和位运算来解决天平平衡问题,主要思路如下:

    1. 问题分解

      • 将16个数字分成左右两组,每组8个数字。
      • 每组再进一步分解为两个4元素子集,分别对应天平方程的左侧和右侧。
    2. 预处理阶段

      • 枚举所有4元素子集:生成所有可能的4元素子集,并计算每个子集的所有排列。
      • 计算加权和:对于每个排列,计算其加权和(如x14 + x23 + x3*2 + x4)。
      • 哈希表存储:使用哈希表(vector数组)记录每个加权和对应的所有4元素子集状态。
    3. 组合匹配阶段

      • 检查互补子集:对于每个4元素子集,检查是否存在另一个不相交的4元素子集,使得它们的加权和相等。
      • 位运算优化:使用位运算快速判断两个子集是否不相交,并记录所有可能的8元素组合。
    4. 最终计数

      • 对称性处理:通过位运算枚举所有可能的8元素组合,并统计互补对的数量。
      • 去重处理:最终结果除以2,消除重复计数。

    代码关键逻辑解析

    1. judge函数

      • 检查一个二进制状态是否恰好包含4个元素。
    2. solve函数

      • 预处理阶段:枚举所有可能的4元素子集,生成每个子集的所有排列,并计算其加权和。
      • 哈希表存储:将每个排列的加权和作为键,对应的子集状态作为值存入哈希表。
      • 组合匹配:遍历每个排列,检查哈希表中是否存在不相交的子集,使得它们的加权和相等。
      • 最终计数:统计所有互补对的数量,并处理对称性。
    3. 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
    上传者