蓝桥杯历年省赛真题做题记录（A组）（2022年第十三届）

D题：选数异或

　　考虑到异或的一个很好的性质，$A^B=x$等价于$A^x=B$。用$flag$数组记录一下数字$A[i]$是否出现过，出现过则$flag[A[i]]不等于0$。

　　类似DP中分配任务模型的思想，这样我们只需要对每次$L,R$询问，判断之中有没有这样一对$(l,r)$数对使得$A[l]^A[r]==x$。因此设$d[i]$为位置$i$之前起始位置$l$最大的数对的起始位置。预处理先遍历一遍$A$数组，$O(n)$处理掉$d$数组。最终整个复杂度是$O(n+m)$。

#include <cstdio>
#define max(a,b) (((a)>(b))?(a):(b)) 
using namespace std;
const int maxn=1e5;

int n,m,x;
int A[maxn+5];
int d[maxn+5];
int flag[(1<<20)];

int main(){
    scanf("%d%d%d",&n,&m,&x);
    for (int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        if (flag[A[i]^x])
            d[i]=max(d[i-1],flag[A[i]^x]);
        else
            d[i]=d[i-1];
        flag[A[i]]=i;
    }
    int L,R;
    while (m--){
        scanf("%d%d",&L,&R);
        if (L<=d[R])
            puts("yes");
        else
            puts("no");
    }
    return 0;
} 

E题：青蛙过河

　　很容易想到二分，这样只需要解决对于给定的一个步长$step$，如何判断能否用$step$的跳跃能力过河：即$step$的合法性问题。

　　想到因为步长最多是$step$，因此对于单次过河，任意的一个$[i,i+step)$的区间，青蛙都至少会跳$1$次（不可能一步跨过这个区间）；那么对于$2x$次过河，青蛙对于这个区间都至少会跳$2x$次。因此易证 $step$合法的条件是对于任意的一个$[i,i+step)$的区间，有$2x$个石头。

#include <cstdio>
using namespace std;
const int maxn=1e5;

int n,x;
int sum[maxn+5];

bool check(int step){
    for (int i=step;i<n;i++)
        if (sum[i]-sum[i-step]<x)
            return false;
    return true;
}

int main(){
    scanf("%d%d",&n,&x);
    x*=2;
    for (int i=1,x;i<n;i++){
        scanf("%d",&x);
        sum[i]=sum[i-1]+x;
    }
    int l=0,r=n,mid;
    while (true){
        mid=(l+r)>>1;
        if (check(mid))
            r=mid;
        else
            l=mid;
        if (r-l<=1){
            printf("%d",r);
            return 0; 
        } 
    }
}