------------恢复内容开始------------
很漂亮的一道题吧 我们可以知道我们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); }
个人认为这道题还挺难的
首先我们观察式子 我们希望他不是一个小于符号 要是一个等号就可以通过再ij变成: 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); }
------------恢复内容结束------------