c++ - 2 名知道最大步数的玩家团队

Question

给定一个要玩 2 人游戏的 N 名玩家的列表。他们每个人要么精通采取特定行动，要么不精通。找出 2 人团队可以知道的最大步数。

并找出有多少团队可以知道最大步数？

例子假设我们有 4 名玩家，5 步，如果 a[i][j] 为 1，则第 i 位玩家精通第 j 步，否则为 0。

10101
11100
11010 
00101

这里一个 2 人团队可以知道的最大步数是 5，他们是两个可以知道最大步数的团队。

解释 : (1, 3) 和 (3, 4) 知道所有 5 步。所以一个 2 人团队知道的最大移动是 5，而且只有 2 个团队可以达到这个目标。

我的方法:对于每对玩家，我检查是否有任何玩家精通 i 步，并为每个玩家保持他可以与其他玩家组成的最大对数及其局部最大值移动组合。

vector<int> pairmemo;
for(int i=0;i<n;i++){
    int mymax=INT_MIN;
    int countpairs=0;
    for(int j=i+1;j<n;j++){
        int count=0;
            for(int k=0;k<m;k++){
                if(arr[i][k]==1 || arr[j][k]==1)
                {
                    count++;
                }
        }
        if(mymax<count){
            mymax=count;
            countpairs=0;
        }
        if(mymax==count){
            countpairs++;
        }

    }
    pairmemo.push_back(countpairs);
    maxmemo.push_back(mymax);
}

所有 N 个玩家的总最大值是答案，计数是正在计算的对的相应总和。

for(int i=0;i<n;i++){
    if(maxi<maxmemo[i])
        maxi=maxmemo[i];
}

int countmaxi=0;

for(int i=0;i<n;i++){
    if(maxmemo[i]==maxi){
        countmaxi+=pairmemo[i];
    }
}

cout<<maxi<<"\n";
cout<<countmaxi<<"\n";

时间复杂度:O((N^2)*M)

代码:我该如何改进它？

约束条件:N<= 3000 和 M<=1000

Answer 1

如果您用一个非常大的整数表示每组移动，问题归结为找到在 MovesI OR MovesJ 中设置了最大位数的一对玩家 (I, J)。

因此，您可以使用位打包并将所有关于移动的信息压缩到长整型数组中。根据约束需要存储 16 个无符号长整数。因此，对于每对玩家，您可以OR 相应的数组并计算其中的个数。这将花费 O(N^2 * 16) ，在给定约束的情况下运行速度非常快。

例子:假设给定矩阵是

11010
00011

并且您使用了 4 位整数来打包它。它看起来像:

1101-0000
0001-1000

也就是说，

13,0
1,8

在 OR 之后，2 人团队的 moves 数组变为 13,8，现在计算为 1 的位。您还必须优化位计数，为此请阅读已接受的答案 here , 否则因子 M 会显得复杂。在处理这些对时，只需维护一个计数变量和一个 maxNumberOfBitsSet 变量。