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