当前位置：首页 > news >正文

蓝桥杯刷题冲刺 | 倒计时22天

news 2025/8/17 9:49:47

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

文章目录

1.选数异或
2.特殊年份

1.选数异或

题目

链接：选数异或 - 蓝桥云课 (lanqiao.cn)
给定一个长度为 n 的数列 A*1,A2,⋯,A n 和一个非负整数 x, 给定 m 次查询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。

输入格式

输入的第一行包含三个整数 n,m,x 。

第二行包含 n个整数 A1,A2,⋯,A n 。

接下来 m 行，每行包含两个整数 l i,r i 表示询问区间 [l i*,*r i] 。

输出格式

对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。

样例输入
```
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
```
样例输出
```
yes
no
yes
no
```
样例说明

显然整个数列中只有 2, 3 的异或为 1。

评测用例规模与约定

对于 20% 的评测用例,1≤n,m≤100;

对于 40% 的评测用例, 1≤n,m≤1000;

对于所有评测用例, 1≤n,m≤100000,0≤x<220,1≤li≤ri≤n, 0≤A i<220 。

第一次

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;int a[N];int main()
{int n,m,x;scanf("%d%d%d",&n,&m,&x);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int l,r;while(m--){scanf("%d%d",&l,&r);int flag=0;for(int i=l;i<r;i++){for(int j=i+1;j<=r;j++){if(a[i]^a[j]==x)   //这里是个坑 ，符号优先级问题{flag=1;puts("yes");break;}}if(flag) break;}if(!flag) puts("no");}return 0;
}

暴力枚举，样例过不了

输出的结果里面：前面的都是 yes ，最后一个都是 no

通过调式发现 a[i]^a[j]!=x , 也会进入 if 语句，是符号优先级的问题

第二次 AC 40%

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;int a[N];int main()
{int n,m,x;scanf("%d%d%d",&n,&m,&x);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int l,r;while(m--){scanf("%d%d",&l,&r);int flag=0;for(int i=l;i<r;i++){for(int j=i+1;j<=r;j++){if((a[i]^a[j])==x)  //加上 （）即可{flag=1;puts("yes");break;}}if(flag) break;}if(!flag) puts("no");}return 0;
}

正确题解

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dp[N], n, m, x;int main() {cin >> n >> m >> x;unordered_map<int, int> last;for(int i=1; i<=n; i++) {int a; cin >> a;dp[i] = max(dp[i-1], last[x ^ a]);//这句应该放到后面， 否则当x=0时会不正确(当x等于0时dp[i] = i, 但是要选两个不同位置的数)//更正于2023/01/01last[a] = i;}while (m -- ) {int l, r; cin >> l >> r;cout << (dp[r] >= l ? "yes" : "no") << endl;}return 0;
}

反思

通过看题解，发现运用到动态规划，emmm，还没有学到，劝退了哈

但是通过这个题，复习符号优先级，而且 AC 40% ，暴力杯爱了爱了
符号优先级

2.特殊年份

题目

链接：特殊年份 - 蓝桥云课 (lanqiao.cn)
今年是 2021 年, 2021 这个数字非常特殊, 它的千位和十位相等, 个位比百位大 1 ，我们称满足这样条件的年份为特殊年份。

输入 5 个年份, 请计算这里面有多少个特殊年份。

输入格式

输入 5 行, 每行一个 4 位十进制数 (数值范围为 1000 至 9999), 表示一个年份。

输出格式

输出一个整数, 表示输入的 5 个年份中有多少个特殊年份。

样例输入
```
2019
2021
1920
2120
9899
```
样例输出
```
2
```
样例说明

2021 和 9899 是特殊年份, 其它不是特殊年份。

我的题解

#include<bits/stdc++.h>
using namespace std;bool check(int x)
{int s[4];int i=0;while(x>0){s[i++]=x%10;x/=10;}if(s[1]==s[3]&&s[0]==s[2]+1) return true;return false;
}int main()
{int a[5];int res=0;for(int i=0;i<5;i++){scanf("%d",&a[i]);if(check(a[i])) res++;}printf("%d",res);return 0;
}

另一种思路——用字符串

#include<bits/stdc++.h>
using namespace std;int main()
{string str;int m=5，res=0;while(m--){cin>>str;if(str[0]==str[2]&&str[3]==str[1]+1) res++;  }printf("%d",res);return 0;
}