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

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

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

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;
  }
  

  在自己代码实现过程中，str 下标可把我整晕了，建议纸上写一写

• 反思

  多看题解，学习佬们的代码，拓展思路

  • 数字可以使用 string 字符串，来储存比较！！！