T1

100%

记 $A_i$ 的最大值为 $V = \max\{A_i\}$。

答案的初始值赋为 $-1$。

先循环第一遍，统计数字 $x$ 在 $A$ 中的出现次数 $cnta[x]$。

再循环第二遍，从小到大枚举 $1\sim V$ 中的偶数 $x$，如果 $cnta[x]$ 为奇数，那么更新答案为 $x$。

时间复杂度 $O(n+V)$。

T2

100%

先循环第一遍，找出 $A$ 中最小的数字 $mn_1$。

再循环第二遍，找出 $A$ 中大于 $mn_1$ 的最小的数字 $mn_2$。

再循环第三遍，找出 $A$ 中大于 $mn_2$ 的最小的数字 $mn_3$。

最后循环第四遍，按顺序输出 $A$ 中小于等于 $mn_3$ 的数字。

时间复杂度 $O(n)$。

T3

100%

为了方便计算，可以将 $v_0,a,v_1,t$ 当作 $\text{double}$ 类型进行输入。

先计算出速度达到 $v_1$ 的时间 $t_1=\frac{(v_1-v_0)}{a}$。

如果 $t_1\geq t$，说明全程都是匀加速运动，位移为 $ans=v_0\times t+0.5\times a\times t^2$。

否则，$0\sim t_1$ 时刻做匀加速运动，此阶段的位移为 $ans_1=v_0\times t_1+0.5\times a\times {t_1}^2$；$t_1\sim t$ 时刻做速度为 $v_1$ 的匀速运动，此阶段的位移为 $ans_2=v_1\times (t-t_1)$。总位移为 $ans=ans_1+ans_2$。

时间复杂度 $O(1)$。

T4

40%

记 $R_i$ 的最大值 $V=\max\{R_i\}$。

预处理数组 $s[i]$ 表示 $1\sim i$ 中山谷数的数量：枚举 $i=1\sim V$，判断 $i$ 是否是山谷数，如果 $i$ 是山谷数那么 $s[i]=s[i-1]+1$，否则 $s[i]=s[i-1]$。

答案即为 $s[R]-s[L-1]$。

时间复杂度 $O(V\log(V)+q)$。

60%

定义 $ask(X)$ 表示 $1\sim X$ 中有多少个山谷数。

对于测试点#5~6，因为 $L=1$，所以答案就是 $ask(R_i)$。

记 $1\sim 10^{18}$ 中的山谷数数量为 $m$，用 $\text{DFS}$ 将这 $m=116504$ 个山谷数枚举出来，保存到数组 $P$ 中。

对 $P$ 进行排序后，$ask(R_i)$ 可以用二分法来求。

时间复杂度 $O((m+q)\log(m))$。

结合第一部分可以拿到 $60\%$ 的分数。

100%

在第二部分的基础上，运用差分的技巧，答案即为 $ask(R_i)−ask(L_i−1)$。

时间复杂度 $O((m+q)\log(m))$。

T5

30%

记 $R_i$ 的最大值 $V=\max\{R_i\}$。

预处理数组 $s[i]$ 表示 $1\sim i$ 中波浪数的数量：枚举 $i=1\sim V$，判断 $i$ 是否是波浪数，如果 $i$ 是波浪数那么 $s[i]=s[i-1]+1$，否则 $s[i]=s[i-1]$。

称满足第一条条件的波浪数为第一类波浪数，满足第二条条件的波浪数为第二类波浪数，两类波浪数分别判断，$i$ 只需符合其中一种情况即为波浪数。

答案即为 $s[R]-s[L-1]$。

时间复杂度 $O(V\log(V)+q)$。

60%

定义 $ask(X)$ 表示 $1 \sim X$ 中有多少个波浪数。

对于测试点#4~6，因为 $L=1$，所以答案就是 $ask(R_i)$。

先单独判断 $X$ 是不是波浪数，接下来考虑 $0\sim X-1$。

定义 $f[i][j][k]$ 为满足 $len(x)=i$ 的最高位数字为 $j$ 的第 $i$ 类波浪数 $x$ 的数量，其中 $j$ 的取值范围为 $0\sim 9$，$k$ 的取值范围为 $1\sim 2$。初始值为 $f[1][j][1]=f[1][j][2]=1$。

考虑 $i>1$ 时如何转移：

• 两重循环枚举 $X_i=Y$ 且 $X_{i-1}=Z$；
• 如果 $X_i$ 和 $X_{i-1}$ 满足第一条条件则 $f[i][Y][1]+=f[i-1][Z][1]$；
• 如果 $X_i$ 和 $X_{i-1}$ 满足第二条条件则 $f[i][Y][2]+=f[i-1][Z][2]$。

定义 $g[i]$ 为满足 $len(X)\leq i$ 的波浪数 $X$ 的数量。初始值为 $g[0]=0$ 和 $g[1]=10$。

$i>1$ 时，有 $g[i]=g[i-1]+\sum_{j=0}^9 (f[i][j][1]+f[i][j][2])$。

处理出 $f$ 数组和 $g$ 数组后，对于每个询问：

• 先单独判断 $R_i$ 是不是波浪数，如果 $R_i$ 是波浪数则答案增加 $1$；
• 对于 $len(X)<len(R_i)$ 的部分，答案增加 $g[len(R_i-1)]$；
• 然后考虑 $X<R_i$ 且 $len(X)=R_i$ 的部分：
  • 如果 $len(R_i)=1$，那么 $0\sim R_i-1$ 都是波浪数，答案增加 $R_i$；
  • 否则两重循环，第一重循环从 $len(R_i)$ 到 $1$ 枚举 $L$，第二重循环枚举 $X_L=Y$，要求 $Y$ 小于 $R_i$ 从低到高的第 $L$ 位，考虑 $X$ 高于 $L$ 位的部分都和 $R_i$ 相同，如果此时 $X$ 的 $L\sim len(R_i)$ 位满足第一条条件则答案增加 $f[L][Y][1]$，如果此时 $X$ 的 $L\sim len(R_i)$ 位满足第二条条件则答案增加 $f[L][Y][2]$。

时间复杂度 $O(100\log(V)+10q\log(V))$。

结合第一部分可以拿到 $60\%$ 的分数。

100%

在第二部分的基础上，运用差分的技巧，答案即为 $ask(R_i)−ask(L_i−1)$。

时间复杂度 $O(100\log(V)+10q\log(V))$。

T6

30%

两重循环分别枚举 $i=1\sim N$ 和 $j=1\sim N$，答案增加 $\gcd(i,j)$。

注意取模。

时间复杂度 $O(N^2\log(N))$。

60%

定义 $s[x]$ 为同时满足以下条件的二元组 $(i,j)$ 的数量：

• $1\leq i\leq x$ 且 $1\leq j\leq x$；
• $\gcd(i,j)=1$。

其中 $\gcd(i,j)=1$ 也叫 $i$ 和 $j$ 互质。

枚举 $x=1\sim N$，如果二元组 $(i,j)$ 满足 $\gcd(i,j)=x$，等价于 $\gcd(\frac{i}{x},\frac{j}{x})=1$，因此满足 $\gcd(i,j)=x$ 的二元组 $(i,j)$ 的数量也就是 $s[\lfloor\frac{N}{x}\rfloor]$，答案增加 $x\times s[\lfloor\frac{N}{x}\rfloor]$。如果提前处理出 $s$ 数组，这个部分的复杂度为 $O(N)$。

接下来考虑如何计算 $s$ 数组。除 $(1,1)$ 外，其余满足 $\gcd(i,j)=1$ 的二元组 $(i,j)$ 可以分为 $i<j$ 和 $i>j$ 两种情况。

定义欧拉函数 $phi[i]$ 表示 $1\sim i$ 中与 $i$ 互质的数的数量，如果 $i<j$ 那么对于 $j$ 有 $phi[j]$ 个 $i$ 满足条件，如果 $i>j$ 那么对于 $i$ 有 $phi[i]$ 个 $j$ 满足条件，再加上 $(1,1)$，可得 $s[x]=1+\sum_{y=2}^x (phi[y]*2)$。如果提前处理出 $phi$ 数组，这个部分的复杂度为 $O(N)$。

$phi$ 是积性函数，关于积性函数请同学们自行查阅资料。设 $x$ 的最小质因数为 $minp[x]$，且 $x$ 的因式分解中 $minp[x]$ 的指数为 $k[x]$，则 $phi[x]=(minp[x]-1)\times minp[x]^{k[x]-1}\times phi[\frac{x}{minp[x]^{k[x]}}]$。

其中 $minp[x]$ 可以在埃氏筛求 $1\sim N$ 中质数的过程中顺便维护，$k[x]$ 则可以通过不断将 $x$ 除以 $minp[x]$ 直到不是 $minp[x]$ 的倍数来求。

算法的时间复杂度瓶颈在于预处理欧拉函数。

时间复杂度 $O(N\log(N))$。

100%

在第二部分的基础上，改用欧氏筛来预处理欧拉函数：

• 设第 $i$ 个质数为 $p_i$；

• 如果 $p_i<minp[x]$，那么 $minp[x\times p_i]=p_i$，$k[x\times p_i]=1$，此时 $phi[x\times p_i]=(p_i-1)\times phi[x]$；

• 如果 $p_i=minp[x]$，那么 $minp[x\times p_i]=p_i$，$k[x\times p_i]=k[x]+1$，此时 $phi[x\times p_i]=p_i\times phi[x]$。

时间复杂度 $O(N)$。