草庐IT

c++ - 添加每个可能的 xor-sum 子数组的和的算法

coder 2024-02-11 原文

我参加了一次算法竞赛。我遇到了一个问题，我在这里问同样的问题。

问题陈述

XOR-sum array 是对该子数组的所有数字进行异或。 给你一个数组，你必须添加所有可能的异或子数组。

为了更好的理解，问题陈述是here还有。

示例

输入

数组:- 1 2

输出:- 6

解释

F(1, 1) = A[1] = 1, F(2, 2) = A[2] = 2 和 F(1, 2) = A[1] XOR A[2] = 1 XOR 2 = 3。

因此答案是 1 + 2 + 3 = 6。

我的代码

时间复杂度:- O(N^2)，(效率低下，未参加比赛)

#include<iostream>

using namespace std;

long long int input[100001];

main() {
    int T;
    int N;
    long long int val;
    long long int temp = 0;
    long long int answer = 0;
    cin >> T;

    while(T--) {
        cin >> N;
        for(int i = 0; i < N; i++) {
            cin >> val;
            temp = temp^val;
            answer += temp;
            input[i] = temp;
        }

        for( int i = 0; i < N; i++ ) {
            for( int j = i+1; j < N; j++ ) {
                answer += input[i]^input[j];
            }
        }
        cout << answer << endl;
        answer = 0;
        temp = 0;
    }
    return 0;
}

问题:-

我在this link 上看到了这个问题的最佳解决方案|

但是在这段代码中，我不明白下面的模块，请帮助我理解。

for (int i=0, p=1; i<30; i++, p<<=1) {
            int c=0;
            for (int j=0; j<=N; j++) {
                if (A[j]&p) c++;
            }
            ret+=(long long)c*(N-c+1)*p;
        }

提前致谢。期待您的回复。

最佳答案

我认为您遗漏了一些非常重要的细节:

int A[MAXN];// the arrays contain int values
//xor all the elements of the array as you read them
for (int i=1; i<=N; i++) {
    scanf("%d", &A[i]);
    A[i]^=A[i-1];
}

阅读输入后，您将得到:

A[0] = A[0]
A[1] = A[1]^A[0]
...
A[N] = A[N]^A[N-1]^...^A[0]

这是 O(N) 并且您基本上可以免费获得它，因为无论如何您都必须阅读输入。 这需要注意或 XOR 部分。现在你只剩下问题的 SUM 部分了。 您有 N 个 int 数字(32 位)，这是您显示的部分所在的位置:

for (int i=0, p=1; i<30; i++, p<<=1) {
            int c=0;
            for (int j=0; j<=N; j++) {
                if (A[j]&p) c++;
            }
            ret+=(long long)c*(N-c+1)*p;
        }

对于每一位，你遍历数组并计算 1 的数量并将它们添加到最终结果。

这部分是 O(30*N)，它仍然是线性时间，所以 O(N)。这比 O(N^2) 更好。

希望这对此事有所启发。

关于c++ - 添加每个可能的 xor-sum 子数组的和的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20113622/

ampxor-sumstrongcodeintc++algorithmmath

有关c++ - 添加每个可能的 xor-sum 子数组的和的算法的更多相关文章

  1. ruby - 我需要将 Bundler 本身添加到 Gemfile 中吗？ - 2

    当我使用Bundler时，是否需要在我的Gemfile中将其列为依赖项？毕竟，我的代码中有些地方需要它。例如，当我进行Bundler设置时:require"bundler/setup" 最佳答案 没有。您可以尝试，但首先您必须用鞋带将自己抬离地面。 关于ruby-我需要将Bundler本身添加到Gemfile中吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/4758609/

  2. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  3. ruby - 将 Bootstrap Less 添加到 Sinatra - 2

    我有一个ModularSinatra应用程序，我正在尝试将Bootstrap添加到应用程序中。get'/bootstrap/application.css'doless:"bootstrap/bootstrap"end我在views/bootstrap中有所有less文件，包括bootstrap.less。我收到这个错误:Less::ParseErrorat/bootstrap/application.css'reset.less'wasn'tfound.Bootstrap.less的第一行是://CSSReset@import"reset.less";我尝试了所有不同的路径格式，但它

  4. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  5. ruby - 续集在添加关联时访问many_to_many连接表 - 2

    我正在使用Sequel构建一个愿望list系统。我有一个wishlists和itemstable和一个items_wishlists连接表(该名称是续集选择的名称)。items_wishlists表还有一个用于facebookid的额外列(因此我可以存储opengraph操作)，这是一个NOTNULL列。我还有Wishlist和Item具有续集many_to_many关联的模型已建立。Wishlist类也有:selectmany_to_many关联的选项设置为select:[:items.*,:items_wishlists__facebook_action_id].有没有一种方法可以

  6. ruby - 可以通过多少种方法将方法添加到 ruby​​ 对象？ - 2

    当谈到运行时自省(introspection)和动态代码生成时，我认为ruby​​没有任何竞争对手，可能除了一些lisp方言。前几天，我正在做一些代码练习来探索ruby​​的动态功能，我开始想知道如何向现有对象添加方法。以下是我能想到的3种方法:obj=Object.new#addamethoddirectlydefobj.new_method...end#addamethodindirectlywiththesingletonclassclass这只是冰山一角，因为我还没有探索instance_eval、module_eval和define_method的各种组合。是否有在线/离线资

  7. ruby - 如何在 Ruby 中向现有方法定义添加语句 - 2

    我注意到类定义，如果我打开classMyClass，并在不覆盖的情况下添加一些东西我仍然得到了之前定义的原始方法。添加的新语句扩充了现有语句。但是对于方法定义，我仍然想要与类定义相同的行为，但是当我打开defmy_method时似乎,def中的现有语句和end被覆盖了，我需要重写一遍。那么有什么方法可以使方法定义的行为与定义相同，类似于super，但不一定是子类？ 最佳答案 我想您正在寻找alias_method:classAalias_method:old_func,:funcdeffuncold_func#similartoca

  8. ruby-on-rails - 添加回形针新样式不影响旧上传的图像 - 2

    我有带有Logo图像的公司模型has_attached_file:logo我用他们的Logo创建了许多公司。现在，我需要添加新样式has_attached_file:logo,:styles=>{:small=>"30x15>",:medium=>"155x85>"}我是否应该重新上传所有旧数据以重新生成新样式？我不这么认为……或者有什么rake任务可以重新生成样式吗？ 最佳答案 参见Thumbnail-Generation.如果rake任务不适合你，你应该能够在控制台中使用一个片段来调用重新处理!关于相关公司

  9. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

  10. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

随机推荐