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