【HDU - 5845】Best Division(xor-trie、01字典树、dp)

发布时间:2017-7-9 7:10:34编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【HDU - 5845】Best Division(xor-trie、01字典树、dp) ",主要涉及到【HDU - 5845】Best Division(xor-trie、01字典树、dp) 方面的内容,对于【HDU - 5845】Best Division(xor-trie、01字典树、dp) 感兴趣的同学可以参考一下。

BUPT2017 wintertraining(15) #7E

题意

把数组A划分为k个区间,每个区间不超过L长度,每一个区间异或和之和为S。现在求:S不超过X,区间个数的最大值。
且A是这样给你的:A1, P, Q。A[i]=(A[i-1]*p+q)%M。M为\(2^{28}\)

题解

容易想到dp, dp[i] :前 i 个数最多划分多少个区间。s[i]为前缀异或和。
dp[i]=max(dp[j]+1),i-L<j<i,且\(s[j]^s[i]\le x\)
dp[n]就是答案。
但是这样是\(O(n^2)\)
异或字典树 优化为\(O(nlogA)\)

字典树来维护s[i],总共N个数,最多28位,所以28*N个节点。

为了找s[j]不超过X的最大f[j],我们沿着字典树一位位找,如果x这一位是0,那么s[j]这一位肯定是和s[i]相同,异或起来才不超过x。如果x这一位是1,那么s[j]这一位可以和s[i]相同,直接取这个节点的最大值;也可以是与s[i]不同,然后继续走。

因为长度不超过L,所以每次处理到第i个,要删去第i-L-1个。

因为一个异或值可能出现多次,所以记录出现次数,删去时减少一次出现次数,次数为0时将对应的值设为-1。

代码

#include <cstdio>#include <algorithm>#include <cstring>#define M 268435456#define N 100005using namespace std;int dp[N], a[N];struct Trie{    int ch[N*28][2];    int val[N*28];//val[i]该节点下代价不超过X的最多段数    int cnt[N*28];//出现次数    int size;    void init(){        size=0;        memset(ch,0,sizeof ch);    }    void Insert(int node, int pos, int id, int num){        cnt[node]++;        if(pos<0){            val[node]=dp[id];            return;        }        int bit=(num>>pos)&1;        if(ch[node][bit]==0){            ch[node][bit]=++size;            val[size]=-1;            cnt[size]=0;        }        Insert(ch[node][bit], pos-1, id, num);        val[node]=max(val[node], val[ch[node][bit]]);    }    int Query(int node, int pos, int x, int num){        if(pos<0)            return val[node];        int xbit=(x>>pos)&1, nbit=(num>>pos)&1;        int ans=-1;        if(xbit){            if(ch[node][nbit])                ans = val[ch[node][nbit]];            if(ch[node][!nbit])                ans = max(ans, Query(ch[node][!nbit], pos-1, x, num));        }        else if(ch[node][nbit])            ans = Query(ch[node][nbit], pos-1, x, num);        return ans;    }    void Delete(int node, int pos, int num){        if(!--cnt[node])            val[node]=-1;        if(pos<0)            return;        int bit=(num>>pos)&1;        Delete(ch[node][bit], pos-1, num);        val[node]=val[ch[node][bit]];        if(ch[node][!bit])            val[node]=max(val[node],val[ch[node][!bit]]);    }}trie;int main(){    int t;    scanf("%d", &t);    while(t--){        int n,x,l;        scanf("%d%d%d", &n,&x,&l);        int p,q;        scanf("%d%d%d", &a[1],&p,&q);        for(int i=2;i<=n;++i)            a[i]=(a[i-1]*p+q)%M;        for(int i=2;i<=n;++i)a[i]^=a[i-1];        trie.init();trie.Insert(0,27,0,0);        for(int i=1;i<=n;++i){            if(i>l+1&&dp[i-l-1]!=-1)trie.Delete(0, 27, a[i-l-1]);            dp[i]=trie.Query(0, 27, x, a[i]);            if(dp[i]!=-1){                dp[i]++;                trie.Insert(0, 27, i, a[i]);            }        }        printf("%d\n", dp[n]==-1?0:dp[n]);    }


上一篇:VS2015 +Qt5 串口工具
下一篇:Azure MySQL PaaS (3) 创建MySQL异地只读数据库 (Master-Slave)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款