1. 首页
  2. 题解列表
  3. 2665题题解

动态规划，中规中矩。

2364 阅读 5 评论
原题链接：蓝桥杯2022年第十三届省赛真题-选数异或

解题思路:dp[i]表示下标在[dp[i]，i]的元素集合符合条件，并且在[dp[i]+1，i]的元素集合不符合条件。也就是dp[i]是i作为右下标对应的最大左下标。

所以只需判断l是否<=dp[r]即可。
注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 100010

#define maxm 100010

#define maxval 1050000

#define pii pair<int,int>

#define fir first

#define sec second

typedef long long ll;

int n,m,x;

int a[maxn];

int dp[maxn];

int pos[maxval];//pos[val]表示val在a中的最大下标 

int main(){

scanf("%d%d%d",&n,&m,&x);

for(int i=1;i<=n;i++){

scanf("%d",&a[i]);

}

for(int i=1;i<=n;i++){

pos[a[i]]=i;

dp[i]=max(dp[i-1],pos[a[i]^x]);

} 

int l,r;

for(int i=1;i<=m;i++){

scanf("%d%d",&l,&r);

if(l<=dp[r])printf("yes\n");

else printf("no\n");

}

}


点赞(0)
　

0.0分

20 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
点进来你会后悔的
点进来你会后悔的
简简单单的循环
简简单单的循环
简单的回文数
简单的回文数

评论列表 共有 5 条评论

zky 10月前 回复TA 
好难啊，这种东西怎么想到怎么做的
摘希 1年前 回复TA 
厉害
jiumi 1年前 回复TA 
@ccccccyan pos数组是a[i]数组对应的下标，dp表示的是a[i]这个数左区间满足条件的最靠近的左边那个数。比如0 < c < a < b < d < n, a^x = b, d^x = c, 此时dp[d] = dp[b] = pos[a]，a所在的是最佳答案。要是a[i]^x后得到的数在右边的话是不会更新的，因为pos数组只更新了1到i
jiumi 1年前 回复TA 
pos数组是a[i]数组对应的下标，dp表示的是a[i]这个数左区间满足条件的最靠近的左边那个数。比如0 < c < a < b < d < n, a^x = b, d^x = c, 此时dp[d] = dp[b] = pos[a]，a所在的是最佳答案。要是a[i]^x后得到的数在右边的话是不会更新的，因为pos数组只更新了1到i
ccccccyan 2年前 回复TA 
for(int i=1;i<=n;i++){

pos[a[i]]=i;

dp[i]=max(dp[i-1],pos[a[i]^x]);

} 
这一步看不懂，求解qwq