I - Vitya and Strange Lesson CodeForces - 842D
2022/4/2 23:23:51
本文主要是介绍I - Vitya and Strange Lesson CodeForces - 842D,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【题目意思】:
找出修改后的序列中,没出现的最小正整数。
修改操作是 将x与序列中所有数异或。(每次异或之后替代原序列的值)。
【解题思路】:
题目要求是找出不在序列里的的最小值。而字典树正好是解决异或最值问题的,所以我们将不在序列里的所有数放进字典树里面,进行异或操作,求出其中的最小值。
字典树求最小值 是 从最高位开始,判断每一位(2进制)上的值是否与自身在这一位上的值相等(异或是相等为0,不相等为1),如果相等,则走下去,如果不相等,只能走那一条路。
如何存储异或后的序列:
根据异或的性质。 a⊕b = c => a = b⊕c => b = a ⊕ c ;
所以记录异或后的序列,只要将每次的x异或起来,在与序列异或。
【代码】:
#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <vector> #include <stack> #include <bitset> #include <cstdlib> #include <cmath> #include <set> #define ms(a, b) memset(a,b,sizeof(a)) #define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ll long long #define ull unsigned long long #define rep(i, a, b) for(ll i=a;i<=b;i++) #define lep(i, a, b) for(ll i=a;i>=b;i--) #define endl '\n' #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<ll> #define vpi vector<pii> #define vpl vector<pll> #define mi map<ll,ll> #define all(a) (a).begin(),(a).end() #define gcd __gcd #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define ff first #define ss second #define test4(x, y, z, a) cout<<"x is "<<x<<" y is "<<y<<" z is "<<z<<" a is "<<a<<endl; #define test3(x, y, z) cout<<"x is "<<x<<" y is "<<y<<" z is "<<z<<endl; #define test2(x, y) cout<<"x is "<<x<<" y is "<<y<<endl; #define test1(x) cout<<"x is "<<x<<endl; using namespace std; const int N = 3e5 + 10; const int maxx = 0x3f3f3f; const int mod = 1e9 + 7; const int minn = -0x3f3f3f; const int M = 2 * N; ll T, n, m; ll a[N]; ll son[N*32][2],idx,cnt[N*32]; ll vis[N*2 ]; void insert(ll n ){ int p=0; for ( int i=32;i>=0;i--){ int u = (n>>i)&1 ; if ( !son[p][u] ) son[p][u] = ++idx; p = son[p][u]; } cnt[p] = n; } ll query(ll n){ int p = 0; for ( int i=32;i>=0;i--){ int u = (n>>i)&1; if ( son[p][u] ){ p = son[p][u]; }else{ p = son[p][u^1]; } } return n^cnt[p]; } void solve() { cin>>n>>m; rep(i,1,n) {cin>>a[i]; vis[a[i]]=1 ;} rep(i,0,2*N){ if ( !vis[i] ) { insert(i); } } ll h = 0; ll x; rep(i,1,m){ cin>>x; h = h^x; cout<<query(h)<<endl; } } int main() { fast; solve(); return 0; }View Code
这篇关于I - Vitya and Strange Lesson CodeForces - 842D的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka