@TopCoder - 12197@ XorAndSum ﹏ヽ暗。殇╰゛Y 2021-11-10 01:34 145阅读 0赞 目录 * @description@ * @solution@ * @accepted code@ * @details@ -------------------- ## @description@ ## 给出 N 个数,每次操作可以任意选择两个数,将其中一个替换为两个数的异或。 求任意次操作后,最终所有数的和的最大值。 **Class:** XorAndSum **Method:** maxSum **Parameters:** long\[\] **Returns:** long **sample:** \{1,2,3\} Returns: 8 **constraints** 数的数量 N <= 50,保证所有数的权值 <= 10^15。 ## @solution@ ## 最大、异或这些关键字,不难想到线性基。 同时可以发现,题目中给出的操作颇有些像高斯消元中,将一个方程异或到另一个方程的操作。 这更坚定了我们写线性基的决心。 我们可以类比高斯消元的做法,将线性基外的数全部消成 0,然后再通过线性基异或成可以异或得到的最大值。 考虑线性基中的数怎么才能取到最大值。 我们将线性基继续类比高斯消元进行简化,将每一行的主元(如果有)所在列全部异或成 0。 然后?可以发现一个大小为 k 的线性基可以异或出 2^k 种数,而我们一共有 k 个主元,决定每一个主元是选还不是选的方案数也是 2^k。进而两者是一一对应的。 我们希望最终线性基中的每一个数都是最大值:即选择所有的主元的那种方案。但是我们可以发现,根据线性基的定义可以简单反证假如有两个以上的主元在自己所在列的每一行中都为 1,会导致矛盾。 这意味着对于主元所在的列,必然存在一个 0,只有一列会例外。显然我们将这个例外放在最大的主元是最优的。 于是线性基中最大和就可以构造出来了:有一个数是选择所有主元(即能异或出的最大值),其他数总是缺一个主元。 我也不知道我上面写了啥。大家也可以看看[yhn学长的博客][yhn]。 ## @accepted code@ ## #include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef long long ll; class XorAndSum{ public: ll b[60 + 5]; void insert(ll x) { for(int i=60;i>=0;i--) if( x & (1LL<<i) ) { if( b[i] == 0 ) b[i] = x; x ^= b[i]; } } ll get_max() { for(int i=60;i>=0;i--) for(int j=i-1;j>=0;j--) if( b[i] & (1LL<<j) ) b[i] ^= b[j]; ll ret = 0; for(int i=60;i>=0;i--) ret ^= b[i]; return ret; } ll maxSum(vector<ll>v) { for(int i=0;i<v.size();i++) insert(v[i]); ll x = get_max(), ans = v.size()*x; bool fir = true; for(int i=60;i>=0;i--) if( b[i] ) { if( fir ) fir = false; else ans = ans - x + (x^b[i]); } return ans; } }; ## @details@ ## 老师:这个不是线性基的入门题?你考试的时候连这个都写不起? 我:…… 怎么办整个世界都在嘲讽我。。。 转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11128702.html [yhn]: https://blog.csdn.net/qq_34454069/article/details/83791081
相关 【热门活动】欢迎参加TopCoder Open程序设计竞赛 美团点评雇主品牌组最近的宗旨就是 搞事搞事搞事 不光和高校勾搭 还入局顶尖赛事 目的只有一个 人才,统统到我们碗里来! ![0?wx\_fmt=png][0_wx_ 不念不忘少年蓝@/ 2023年10月18日 23:02/ 0 赞/ 62 阅读
相关 TopCoder 636 B 【暴力】 题意:给出一个排列,其中的一些数字不小心给擦掉了。但是知道这个序列满足 i < j && a\[ i \] < a\[ j \] 的元素对有n个,然后让你求还原这个排列之后有几 我就是我/ 2022年08月13日 06:29/ 0 赞/ 95 阅读
相关 TopCoder SRM 731 Div2 Easy题解报告 Problem Statement Hero has an infinite periodic string t. You are given the string s 秒速五厘米/ 2022年05月28日 04:45/ 0 赞/ 70 阅读
相关 topcoder srm 480 div1 problem1 [link][] 直接模拟即可。 problem2 [link][link 1] 首先,网关一定是安装在client与server之间的链路上。而不会安 Bertha 。/ 2022年03月29日 08:48/ 0 赞/ 74 阅读
相关 TopCoder 2019线下比赛 文章目录 warmup 解法代码1 解题代码2 1 描述 解答 2 描述 解答 3 描述 Love The Way You Lie/ 2022年01月14日 07:47/ 0 赞/ 124 阅读
相关 一道挺好玩的题,可用来作面试题【来自20111224 Topcoder DIVI 250题】 一道挺好玩的题,可用来作面试题【来自20111224 Topcoder DIVI 250题】 有N个数,编号1到n。按照以下规则进行删除数,求最后剩下的那个数。【1<= 水深无声/ 2021年12月14日 15:57/ 0 赞/ 148 阅读
相关 @TopCoder - 12197@ XorAndSum 目录 @description@ @solution@ @accepted code@ @details@ -------------------- ﹏ヽ暗。殇╰゛Y/ 2021年11月10日 01:34/ 0 赞/ 146 阅读
相关 topcoder srm 662 div1 -3 1、给出$n$个数字将其排列成一个环,使得相邻两个数字差的最大值最小。 思路:首先排序。然后从最小的数字开始,依次枚举将下一个数字放在左侧或者右侧。令$f[i][j][... 骑猪看日落/ 2021年05月02日 12:19/ 0 赞/ 206 阅读
还没有评论,来说两句吧...