前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【HDU - 5845】Best Division(xor-trie、01字典树、dp)

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

作者头像
饶文津
发布2020-06-02 14:59:33
3530
发布2020-06-02 14:59:33
举报
文章被收录于专栏:饶文津的专栏

BUPT2017 wintertraining(15) #7E

题意

题解

代码

代码语言:javascript
复制
#include <cstdio>
#include <algorithm>
#include <cstring>
#define M 268435456
#define N 100005

using namespace std;
int dp[N], a[N];

struct Trie{
    int ch[N*28][2];
    int val[N*28];//异或到当前位置不超过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]);
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-07-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • 题解
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档