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

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

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/01
          last[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 字符串，来储存比较！！！