您的位置:首页 > 文旅 > 旅游 > 东莞网站建设网站建设多少钱_专业建设的基本要素_杭州优化seo公司_国际购物网站平台有哪些

东莞网站建设网站建设多少钱_专业建设的基本要素_杭州优化seo公司_国际购物网站平台有哪些

2024/12/23 12:34:10 来源:https://blog.csdn.net/2301_76605150/article/details/144583291  浏览:    关键词:东莞网站建设网站建设多少钱_专业建设的基本要素_杭州优化seo公司_国际购物网站平台有哪些
东莞网站建设网站建设多少钱_专业建设的基本要素_杭州优化seo公司_国际购物网站平台有哪些

选数异或

蓝桥杯每日一题 2024-12-16 选数异或 线段树 DP 思维

题目大意

给定一个长度为 n n n 的数组 A 1 , A 2 , ⋯ , A n A_1, A_2, \cdots, A_n A1,A2,,An 和一个非负整数 x x x,给定 m m m 次查询,每次询问能否从某个区间 [ l , r ] [l, r] [l,r] 中选择两个数使得它们的异或等于 x x x

解题思路

本题分三种解题方式:

1、小白暴力解法:直接在[l,r]区间内进行双重循环即可到手40分。

先了解下前提知识:a^b=x <==> a^x=b

2、思维大佬DP法: f(i) 表示 0 ~ i 之间的与 i 相距最近的那个满足 异或x后的值的下标;然后如果 f(i-1)满足条件,那么f(i)一定也满足件,那么状态转移方程就是: f ( i ) = m a x ( f ( i − 1 ) , l a s t ( a [ i ] ∗ x ) ) f(i) = max(f(i-1),last(a[i]*x)) f(i)=max(f(i1),last(a[i]x));最后判断的时候 f® 一定是0~r之前最大的满足条件的下标,那么只需要判断 其值是否大于L 即可。
为什么执着要判断 0~R 之间的,而不是LR之间的?因为在LR之间如果满足条件那么0~R一定会满足条件,那么这时候我们所要维护判断的边界只有左边界。

3、编程大佬线段树法:线段树的方法只是将DP法中的状态转移过程绕了一圈又回过来了。
也是先预处理每个位置的值所对应异或之后值的位置(都是左边的),然后线段树处理的是,每个区间的一个对应的最大值。要知道,这个最大值是一定小于它所在的下标的,所以说只需要处理找出最大值与左边界比较的结果即可。

40分暴力保分
#include <iostream>using namespace std;
typedef long long ll;
const int N = 100010;
int a[N];
int n,m;
int x;void sovle() {int l,r;cin>>l>>r;for(int i = l; i <= r;i++) {for(int j = i+1 ;j <= r;j++) {
//                cout<<"---> "<<a[i]<<" "<<a[j]<<" = "<<(a[i]^a[j])<<" "<<x<<endl;if((a[i]^a[j]) == x) {cout<<"yes"<<endl;return ;}}}cout<<"no"<<endl;
}int main()
{cin>>n>>m>>x;for(int i = 1;i <= n;i++) {cin>>a[i];}while(m--) {sovle();}return 0;
}
AC DP法
#include <bits/stdc++.h>using namespace std;const int N = 100010,M = 1 << 20;
int last[M],a[N];int main() {int n,m,x;cin>>n>>m>>x;for(int i = 1;i <= n;i++) {int t;cin>>t;// 一直递进更新,而且每次都是取得最大值a[i] = max(a[i-1],last[t^x]);last[t] = i;}while(m--) {int l,r;cin>>l>>r;// 这是a[r] 就代表着 r 前面所能够匹配的那些值的最大值if(a[r] >= l) puts("yes");else puts("no");}return 0;
}
AC 线段树
#include <iostream>using namespace std;const int N = 100010,M = (1 << 20)+10;
int a[N<<2],last[M],Left[N]; // a数组长度一定要扩大四倍
int n,m,x;void build(int u,int l,int r) {// 递归到叶子结点将所处理的位置更新到线段树上if(l == r) {a[u] = Left[l];return ;}int mid = l + r >> 1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);// 向上更新线段树 pushUp 操作a[u] = max(a[u<<1],a[u<<1|1]);
}int query(int u,int l,int r,int x,int y) {// 如果分后的区间被全包含,直接返回即可if(l >= x && r <= y) {return a[u];}int mid = l + r >> 1;// 第一种情况:找原始区间的左节点if(y <= mid) {return query(u<<1,l,mid,x,y);} else {/*** 第三种情况:*  l[________m_______]r*      x[____m_________]y * 这时候要将目标区间也分开来算,然后取他们的最大值即可**/if(x <= mid) return max(query(u<<1,l,mid,x,mid),query(u<<1|1,mid+1,r,mid+1,y));else return query(u<<1|1,mid+1,r,x,y);  // 第二种情况:找原始区间的右节点}
}int main() {cin>>n>>m>>x;for(int i = 1;i <= n;i++) {int t;cin>>t;// 预处理当前值所对应异或后的值的位置Left[i] = last[t ^ x];// 存储之前有的值,并存储索引last[t] = i;}// 建线段树build(1,1,n);while(m--) {int l,r;cin>>l>>r;// 在初始区间[1,n]中查找[l,r]中的所处理到的最大下标int k = query(1,1,n,l,r);// 判断这个最大下标是否在规定区间中if(k >= l) puts("yes");else puts("no");}return 0;
}
思考

这个题是比上一题好写一些的,但是思维难度是一点不减啊!!!

备注

想要一起备赛的同学可以评论区留言!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com