题解 - Vijos

1

twd2 LV 9 MOD @ 2017-01-17 19:40:27

这道题目的题意就是要求计算
\( \sum_{i = 1}^{N} \max_{1 \leq j \leq \min \{ K, N - i + 1 \} } \{ A_i \oplus A_{i + 1} \oplus ... \oplus A_{ i + j - 1} \} \)

连续的异或运算不好处理，首先做如下的变换

xor_sum[0] = 0

xor_sum[i] = A[1] ⊕ A[2] ⊕ ... ⊕ A[i]

这样，由异或的交换律、结合律、x ⊕ x === 0 以及 0 ⊕ y === y，就是计算
\( \sum_{i = 1}^{N} \max_{1 \leq j \leq \min \{ K, N - i + 1 \} } \{ xor\_sum_{i-1} \oplus xor\_sum_{ i + j - 1} \} \)
先考虑对于一个给定的数x以及y[1], ..., y[k]，计算x ⊕ y[i]的最大值。也就是希望异或结果的高位尽可能为1，也就是希望x和y[i]的高位尽可能相反。

于是，可以对y[i]的二进制表示串建立trie树，**高位在浅层**（因高位尽可能和x的相反，且树的浅层先达到）。搜索到某一位的时候尽可能向与x这一位相反的方向走（走不了那也只能同方向了），这样，搜索结果能确保与x进行异或得到的值是最大的。

对于该题，对于每个i=1, ..., N，可以建立xor_sum[i], ..., xor_sum[min{i + K - 1, N}]的trie树，然后用xor_sum[i - 1]来搜索。注意到i=1时只需找xor_sum[i], ..., xor_sum[min{K, N - i + 1}]中最大值，根据变换中xor_sum[0] = 0，考虑异或的性质0 ⊕ y === y，可以用同样的算法来搜索。

事实上，如果有删除的接口，每一次不需要重新建树，只需要删除前一个没用的（即xor_sum[i - 1]），如果还有可以加入的（ i + K - 1 <= N），还需加入最后一个需要的（即xor_sum[i + K - 1] ）即可。

做变换的时间复杂度是O(N)，trie树插入、查找、删除时间复杂度都是O(1)，建树时间复杂度是O(K)，更新时间复杂度O(1)。由于K < N，所以，总体的时间复杂度是O(N)。

做变换需要额外O(N)的空间来存储；trie树在本程序中实际上是一个二叉树，并且叶子节点规模不超过O(K)，所以trie树的空间复杂度是O(2K) = O(K)。总体空间复杂度，由于K < N，是O(N)的。

1

LiuWeiMing1997 LV 8 @ 2016-12-22 23:02:29

字典树要开够内存
设perXor[i]表示1---i的前缀异或值。

那么要得到某一段的异或值，只需要perXor[j] ^ perXor[i - 1]

那么我们把perXor[n]先加入去字典树，然后用perXor[n - 1]去找，找到的就是下标n的贡献。

同理，然后把perXor[n - 1]插进去，用perXor[n - 2]找，就会是下标n - 1的贡献。因为这个时候它可以是

perXor[n - 2] ^ perXor[n - 1]（因为perXor[n - 1]已经在字典树了，）那么这个时候对应的就是a[n - 1] 自己了。

同理它可以是perXor[n - 2] ^ perXor[n]，就是a[n - 1] ^ a[n]了。

当然，它还有个m的限制，这个可以加个删除操作即可。

需要注意的是：

1、unsigned int并不是保留低31位，它是对2^32取模，而2^32有33位。

2、字典树的大小要开好，字典树的struct node *pNext[]只需2个即可。因为状态只有0或1

3、判断第i位是否是1或者0，是((1 << i) & val) >= 1 不要忘记判断，不然re

4、cin、cout请取消同步，卡了我TLE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>

const int maxn = 5e5 + 20;
int a[maxn];
int perXor[maxn];
struct node {
    int cnt;
    struct node * pNext[2];
}tree[maxn * 40];
int t;
struct node * create() {
    struct node *p = &tree[t++];
//    p->cnt = 0;
//    for (int i = 0; i <= 9; ++i) {
//        p->pNext[i] = NULL;
//    }
    return p;
}
void toInsert(struct node **T, int val) {
    struct node *p = *T;
    if (p == NULL) {
        p = *T = create();
    }
    for (int i = 30; i >= 0; --i) {
        int id = ((1 << i) & val) >= 1;
        if (p->pNext[id] == NULL) {
            p->pNext[id] = create();
        }
        p = p->pNext[id];
        p->cnt++;
    }
}
void toDel(struct node **T, int val) {
    struct node *p = *T;
    if (p == NULL) return;
    for (int i = 30; i >= 0; --i) {
        int id = ((1 << i) & val) >= 1;
        p = p->pNext[id];
        p->cnt--;
    }
}
int toFind(struct node *T, int val) {
    struct node *p = T;
    if (p == NULL) return 0;
    int ans = 0;
//    cout << val << endl;
    for (int i = 30; i >= 0; --i) {
        int id = ((1 << i) & val) >= 1;
        if (p->pNext[!id] && p->pNext[!id]->cnt >= 1) {
            ans |= (1 << i);
            p = p->pNext[!id];
        } else {
            p = p->pNext[id];
        }
    }
    return ans;
}
int listToAdd[maxn];
const LL MOD = (1LL << 31);
void work() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        perXor[i] = perXor[i - 1] ^ a[i];
    }
//    for (int i = 1; i <= n; ++i) {
//        cout << perXor[i] << " " ;
//    }
//    cout << endl;
//    unsigned int t = (1LL << 32);
//    cout << t << endl;
    long long int ans = 0;
    struct node *T = NULL;
    toInsert(&T, perXor[n]);
    int len = 0;
    listToAdd[++len] = perXor[n];
    int cur = 1;
//    cout << toFind(T, perXor[n]) << endl;
    for (int i = n - 1; i >= 0; --i) {
        ans += toFind(T, perXor[i]);
        if (ans >= MOD) ans %= MOD;
//        cout << toFind(T, perXor[i]) << endl;
        toInsert(&T, perXor[i]);
        listToAdd[++len] = perXor[i];
        if (len - cur + 1 > m) {
            toDel(&T, listToAdd[cur++]);
        }
    }
//    cout << endl;
    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    IOS;
    work();
    return 0;
}

http://www.cnblogs.com/liuweimingcprogram/p/6213220.html

0

ljh2000 LV 8 @ 2016-11-03 22:51:41

似乎不会用markdown...
```c++
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int inf = (1<<30);
const int MAXN = 10000011;
int n,m,a[MAXN],sum[MAXN];
int tr[MAXN][2],ci[MAXN],cnt;
LL ans;

inline int getint()
{
int w=0,q=0; char c=getchar();
while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar();
while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
}
inline void insert(int x){
int u=1,num; ci[u]++;
for(int i=30;i>=0;i--) {
num=(x>>i)&1; if(!tr[u][num]) tr[u][num]=++cnt;
u=tr[u][num]; ci[u]++;
}
}
inline void del(int x){ int u=1,num; ci[u]--; for(int i=30;i>=0;i--) { num=(x>>i)&1; u=tr[u][num]; ci[u]--; } }
inline void query(int x){
int u=1,num; int now_ans=0;
for(int i=30;i>=0;i--) {
num=(x>>i)&1;
if(!tr[u][num^1] || ci[tr[u][num^1]]==0) u=tr[u][num];
else u=tr[u][num^1],now_ans+=(1<<i);
}
ans+=now_ans;
}

inline void work(){
n=getint(); m=getint(); for(int i=1;i<=n;i++) a[i]=getint(),sum[i]=sum[i-1]^a[i]; cnt=1;
int nowl=1; while(nowl<m) insert(sum[nowl]),nowl++;
for(int i=1;i<=n;i++) {
if(nowl<=n) insert(sum[nowl]),nowl++;

query(sum[i-1]);
del(sum[i]);
}
LL MOD=(1LL<<31); ans%=MOD;
printf("%lld",ans);
}

int main()
{
freopen("2001.in","r",stdin);
freopen("2001.out","w",stdout);
work();
return 0;
}
```

LCF @ 2016-11-12 22:51:42

跪烂！

0

ljh2000 LV 8 @ 2016-11-03 22:50:47

在Trie上维护前缀异或和，每次删除和插入一个元素，查询操作就是能取反就取反
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int inf = (1<<30);
const int MAXN = 10000011;
int n,m,a[MAXN],sum[MAXN];
int tr[MAXN][2],ci[MAXN],cnt;
LL ans;

inline int getint()
{
int w=0,q=0; char c=getchar();
while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar();
while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
}
inline void insert(int x){
int u=1,num; ci[u]++;
for(int i=30;i>=0;i--) {
num=(x>>i)&1; if(!tr[u][num]) tr[u][num]=++cnt;
u=tr[u][num]; ci[u]++;
}
}
inline void del(int x){ int u=1,num; ci[u]--; for(int i=30;i>=0;i--) { num=(x>>i)&1; u=tr[u][num]; ci[u]--; } }
inline void query(int x){
int u=1,num; int now_ans=0;
for(int i=30;i>=0;i--) {
num=(x>>i)&1;
if(!tr[u][num^1] || ci[tr[u][num^1]]==0) u=tr[u][num];
else u=tr[u][num^1],now_ans+=(1<<i);
}
ans+=now_ans;
}

inline void work(){
n=getint(); m=getint(); for(int i=1;i<=n;i++) a[i]=getint(),sum[i]=sum[i-1]^a[i]; cnt=1;
int nowl=1; while(nowl<m) insert(sum[nowl]),nowl++;
for(int i=1;i<=n;i++) {
if(nowl<=n) insert(sum[nowl]),nowl++;

query(sum[i-1]);
del(sum[i]);
}
LL MOD=(1LL<<31); ans%=MOD;
printf("%lld",ans);
}

int main()
{
work();
return 0;
}

0

y20070316 LV 9 @ 2016-11-03 11:06:56

前缀亦或和+Trie

题解

5 条题解

xor-sigma

信息

状态

开发

支持

题解

5 条题解

xor-sigma

信息

状态

开发

支持

还没有账户？

登录