首页 > 其他分享 >D2. Xor-Subsequence (hard version)

D2. Xor-Subsequence (hard version)

时间:2023-03-19 15:22:50浏览次数:47  
标签:ch Xor int max hard else Subsequence mx

D2. Xor-Subsequence (hard version)

/*

进行转换,可以要存储i^a[i]的值

首先确保前面都是相同的
然后假设下一位是不相同的,那么会在这里进行更新,都枚举一下就可以了

字典树+dp
也就是看跳到某一位后进行更新就可以了
复杂度是可以接受的

*/

#include <bits/stdc++.h>
using namespace std;
const int M=3e5+5;

int ch[M*32][2],f[M*32][2],tot;
int a[M];

void insert(int x,int y,int mx) {//更新
    int p=0;
    for(int i=30;i>=0;i--) {
        int u=x>>i&1,v=y>>i&1;
        if(!ch[p][u^v])ch[p][u^v]=++tot;
        p=ch[p][u^v];
        f[p][u]=max(f[p][u],mx);//在这个点的时候,我是取u的
    }
}

int query(int x,int y) {//查找
    int p=0,mx=0;
    for(int i=30;i>=0;i--) {
        int u=x>>i&1,v=y>>i&1;
        //假设这里是转折点,也就是下一位开始就不相同了,那么要怎么进行更新
        //枚举所有的情况,一共四种
        if(u!=v) {
            if(ch[p][0]) {
                if(u==1)mx=max(mx,f[ch[p][0]][1]);
                else mx=max(mx,f[ch[p][0]][0]);
            }
        }
        else {
            if(ch[p][1]) {
                if(u==1)mx=max(mx,f[ch[p][1]][0]);
                else mx=max(mx,f[ch[p][1]][1]);
            }
        }
        p=ch[p][u^v];
        if(!p)break;
    }
    return mx+1;
}

void solve() {
    int n;cin>>n;
    int ans=0;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        int mx=query(i,a[i]);
        ans=max(ans,mx);
        insert(i,a[i],mx);
    }
    cout<<ans<<endl;
    for(int i=0;i<=tot;i++)ch[i][0]=ch[i][1]=f[i][0]=f[i][1]=0;
    tot=0;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int TT;cin>>TT;
    while(TT--)solve();
    return 0;
}

标签:ch,Xor,int,max,hard,else,Subsequence,mx
From: https://www.cnblogs.com/basicecho/p/17233308.html

相关文章

  • D2. Hot Start Up (hard version)
    D2.HotStartUp(hardversion)思路有两种方法:1.求最小不相交的区间的和,但是需要偏移一下,这样才能保证区间一定不相交2.根据D1中dp的式子中可以看出,只有1个点是进行......
  • MongoDB 分片集群-Sharded Cluster【转】
    1、分片概念分片(sharding)是一种跨多台机器分布数据的方法,MongoDB使用分片来支持具有非常大的数据集和高吞吐量操作的部署。换句话说:分片(sharding)是指将数据拆分,将其分......
  • D. XOR Permutations
    D.XORPermutations注意多次输入输出不要忘了初始化注意分析代码点击查看代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#inc......
  • [CF1788F] XOR, Tree, and Queries
    题目描述Youaregivenatreeof$n$vertices.Theverticesarenumberedfrom$1$to$n$.Youwillneedtoassignaweighttoeachedge.Lettheweight......
  • 407. 接雨水 II (Hard)
    问题描述407.接雨水II(Hard)给你一个mxn的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。示例1:输入:heigh......
  • git reset --soft 和 --hard
    --soft下图是第五次commit的内容:现在,gitreset--soft<hash>回退版本:--soft保留了第五次commit的内容(所有的更改都在暂存区),当前已经退到了第四次commit。在我......
  • [ARC066E] Addition and Subtraction Hard
    h3>ProblemStatementJoisinoisabouttocompeteinthefinalroundofacertainprogrammingcompetition.Inthiscontest,thereare\(N\)problems,numbered\(......
  • 容斥定理 AtCoder——FizzBuzz Sum Hard
    题目传送门ProblemStatementFindthesumofintegersbetween 1 and N(inclusive)thatarenotmultiplesof Aor B.Constraints1≤N,A,B≤109 Allvalue......
  • hard-coded strings are a bad idea.
    Hard-Codingisaterriblybadpractice. Lookatthecodebellow. Theprogrammerhardcodedthestringsintheprogram. Stringlike "huiQiTransPaymentSer......
  • “External hard disk media”和“Removable media”的区别
    "Externalharddiskmedia"(外置硬盘)和"Removablemedia"(可移动媒体)是两个不同的概念。"Externalharddiskmedia"指的是一种具有大容量、高速度、可重复写入并且需要外......