训练记录

------------恢复内容开始------------

D2. Burenka and Traditions (hard version)

很漂亮的一道题吧 我们可以知道我们1 2花费是一样的 你花费1的时候也可以用2来搞一搞 但是搞的代价就是你下一个只有异或上一个的值
那么对于我们每一个值 要是想要和前面的数异或全变成0 这样才能让结果-1 那么就肯定是一个后缀异或和 但是我们每次check后缀异或复杂度是n2的
这里就有个很漂亮的写法 我们维护前面所有的异或和 因为当且仅当我们当前ai+1也是一个后缀时才能变成0 那么我们用一个set把每一个异或装进来
记得一定要把0也装进来 因为ai+1可能是前面所有异或和

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 998244353;
const int mod = 135799;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);

void solve() {
    int n;
    cin >> n;
    int res = 0;
    set<int> s;
    int tag = 0;
    s.insert(0);
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if (x == 0 || s.count(x ^ tag)) s.clear(), s.insert(0), tag = 0;
        else s.insert(tag), tag ^= x, res++;
    }
    cout << res << '\n';
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

D2. Xor-Subsequence (hard version)

个人认为这道题还挺难的
首先我们观察式子 我们希望他不是一个小于符号 要是一个等号就可以通过再ⁱj变成： ai ^ i = aj ^ j
那我们考虑一颗01字典树 这样岂不是就有一部分重合的相等了吗 状态表示就很清楚了 f[u][0/1]表示我们在u节点且他爹是0/1的max 为什么要记录他爹是啥 马上我就会说明
那我们设前k位是一样的（这样我们就可以插入aj*j 然后查找每个的分叉即可） k+1位不一样的话并且合法的话只有ai ^ j < aj ^ i
那我们只有可能ai^j=0 aj^i=1
我们不妨把这个表写出来就会发现 aj^j=ai ^ i ^ 1 , j=ai ^ 1
有了这个我们就可以有了这个我们就可以沿着ai^i去查找 哪一位有分叉 并且还满足 aj^j=ai ^ i ^ 1（对儿子的限制） j=ai^1（对爹的限制） 更新即可 要是ai^i走不下去了 break即可

#include <bits/stdc++.h>
using namespace std;
const int N =3e5+10;
const int M = 998244353;
const int mod = 135799;
//#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int f[N*32][2],tr[N*32][2],dp[N],a[N],n,cnt;
void insert(int n,int id){
    int u = 0;
    for (int i = 30; i >= 0; i--) {
        int bit = (n >> i) & 1;
        if (!tr[u][bit])tr[u][bit] = ++cnt;
        u = tr[u][bit];
        f[u][(id >> i) & 1] = max(f[u][(id >> i) & 1], dp[id]);
    }
}
int query(int n,int k){
    int res=1,u=0;
    for(int i=30;i>=0;i--){
        int bit=n>>i&1;
        int rev=tr[u][bit^1];
        res=max(res,f[rev][k>>i&1^1]+1);
        if(!tr[u][bit])break;
        u=tr[u][bit];
    }
    return res;
}
void solve() {
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i],dp[i]=1;
    for(int i=0;i<=cnt;i++)tr[i][0]=tr[i][1]=f[i][1]=f[i][0]=0;
    cnt=0;
    for(int i=0;i<n;i++){
        dp[i]=query(a[i]^i,a[i]);
        insert(a[i]^i,i);
    }
    cout<<*max_element(dp,dp+n)<<endl;
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

------------恢复内容结束------------