题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
能通过20%
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
const int N = 1010;
int nums[N];
int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> nums[i];
}
int ans = INT_MIN;
for(int i = 0; i <= n-m; i++){
int tmp = nums[i];
for(int j = 1; j < m; j++){
tmp ^= nums[i + j];
ans = max(ans, tmp);
//cout << "tmp = " << tmp << endl;
}
ans = max(ans, tmp);
}
cout << ans << endl;
return 0;
}
算法2
前缀和+字典树
每次输入数字,计算前缀和,最后要求的就转换为从前缀和中取两个si,sj使它们的异或和最大。
思路就和 https://www.acwing.com/problem/content/145/ 一样了。
用到字典树。
其实没怎么看懂QAQ
而且这里测试用例 1000 1000 。。。。 代码算出的是1804552192,但标准答案写的是1797189764。但是通过了 迷惑
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
const int N = 100010 * 31;
const int M = 100010;
int n, m, idx;
int s[M]; //前缀和
int son[N][2]; //字典树
int cnt[N]; //记录以i为根的子树含有多少个数cnt[i]
void insert(int x, int v){ //v取+1(增加数x)或-1(删除数x)
int p = 0;
for(int i = 30; i >= 0; i--){
int u = x >> i & 1; //u是x的第二位
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
cnt[p] += v;
}
}
int query(int x){ //v取+1(增加数x)或-1(删除数x)
int res = 0, p = 0;
for(int i = 30; i >= 0; i--){
int u = x >> i & 1; //u是x的第二位
if(cnt[son[p][!u]]) {
p = son[p][!u];
res = res * 2 + 1;
}else{
p = son[p][u];
res = res * 2;
}
}
return res;
}
int main(){
int n, m, x;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> x;
s[i] = s[i-1] ^ x;
}
int res = 0;
insert(s[0], 1);
//遍历s[i]
for(int i = 1; i <= n; i++){
if(i > m) insert(s[i - m - 1], -1);
res = max(res, query(s[i]));
insert(s[i], 1);
}
cout << res << endl;
return 0;
}
暴力应该能过50%