踩不出足迹（T3）

NC227011. 踩不出足迹（T3）

描述

踩不出足迹

希望你在看这道题时，不要成为骄傲无知的现代人。

现代人有一串足迹 a，定义为长度为 n 的数列，每个数字是一个 k 位的二进制数，同时保证 $\forall i\in[1,n], a_i<2^k$ 。

定义以下操作：
令第一次得到的结果为 $a_1$ 。你需要从第二个数开始，每次可以选择与上一次得到的结果异或或者同或起来。

例：k=3时 0（000）同或2（010）=5（101）

最终结果的最大值定义为足迹的密码。
现代人想请你帮忙求出这个密码。

输入描述

第一行两个数，n,k。 
接下来一行共 n 个数，代表 a。

输出描述

仅一个数，最大结果。

示例1

输入:

3 2
3 1 2

输出:

说明:

对于 $100\%$ 的数据： $1\lt n\le10^6,1\le k\le64$ 。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 140ms, 内存消耗: 416K, 提交时间: 2021-09-10 20:14:07

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
int n,k;
ll s,a;
int main(){
	cin>>n>>k;
	while(n--)
		scanf("%llu",&a),s^=a;
	cout<<max(s,~s<<64-k>>64-k);
	return 0;
}

pypy3 解法, 执行用时: 873ms, 内存消耗: 153676K, 提交时间: 2021-10-19 19:50:06

n,k = map(int,input().split())
a = list(map(int,input().split()))
x = 0
for it in a:
    x ^= it
print(max(x,x^((1<<k)-1)))

Python3 解法, 执行用时: 629ms, 内存消耗: 151360K, 提交时间: 2022-04-24 23:21:11

n,k = map(int,input().split())
a=list(map(int,input().split()))
s = 0
for _ in a:
    s^=_
print(max(s,s^(2**k-1)))