训练记录
2022/8/23 6:23:58
本文主要是介绍训练记录,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
------------恢复内容开始------------
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)
个人认为这道题还挺难的
首先我们观察式子 我们希望他不是一个小于符号 要是一个等号就可以通过再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); }
------------恢复内容结束------------
这篇关于训练记录的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?