arrays - 数组子集中存在的值的 XOR

Question

给定一个大小为 n 的仅包含正整数的 A 数组。设 l 为数组 A 中的最大数。生成大小为 0 到 l 的数组 B，使得 B[j] 为数组 A 的异或值等于 j 的最大子集的大小。

约束:数组 A 的大小可以从 1 到 10000。数组 A 中的元素范围为 1 到 1000。

例如:如果数组 A 有 (1,2,3,4)，那么数组 B 将生成如下。

B(0)=3，因为 XOR 值为 0 的最大子集是 (1,2,3) 并且大小为 3。

B(1)=2 因为 XOR 值为 1 的最大子集是 (2,3) 并且大小为 2。

B(2)=2 因为 XOR 值为 2 的最大子集是 (1,3) 并且大小为 2。

B(3)=2 因为 XOR 值为 3 的最大子集是 (1,2) 并且大小为 2。

B(4)=4，因为具有 XOR 值 4 的最大子集是 (1,2,3,4) 并且大小为 4。

我的蛮力方法:生成数组 A 的所有非空子集并计算每个子集的异或并将具有异或值 j 的最大大小子集保存在 B[j] 中。

有没有更有效的方法来做到这一点？

Answer 1

我相信这会奏效，我已经添加了评论以寻求帮助

#include <iostream>
using namespace std;
#define max(a, b) (a>b?a:b)
int dp[10005][1001]= {0};
int main() {
    // your code goes here
    int n, a[10005]={0}, m, i,j, ans[1005]={0};
    // n denotes number of elements in array, m denotes the range(0, m) where you want to loop
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++){
        // taking input
        scanf("%d",&a[i]);
    }
    for(i=0;i<=10000;i++){
        for(j=0;j<=1000;j++){
            dp[i][j] = -1;
        }
    }
    dp[0][0] = 0;
    // dp[i][j] denotes what's the max num of elements whose xor = j using the first i elements
    for(i=1; i<=n; i++){
        for(j=0; j<=1000; j++){
            if(dp[i-1][j] != -1){
                // if j was possible using i-1 elements the using a[i] (a[i]^j) can be made using i elements
                dp[i][j^a[i]] = max(dp[i][j^a[i]], dp[i-1][j]+1);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            if(dp[i][j] != -1){
                ans[j] = max(ans[j], dp[i][j]);
            }
        }
    }
    for(i=0;i<=m;i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}

检查 http://ideone.com/QuICHN 处的输出