等价串
from fsf，题解 by wzj52501
算法一
我会为所欲为大暴力！
时间复杂度：$O(?)$
期望得分：20分。
算法二
我们可以将序列 $A$、$B$ 分别建立线段树式结构，即使用 $2n-1$ 个区间来描述一个序列。
设 $f(x,y)$ 表示以 $x$ 为根的线段树 $A$ 是否与以 $y$ 为根的线段树 $B$ 等价， $cmp(x,y)$ 表示 $x$ 对应的序列 $A$ 和 $y$ 对应的序列 $B$ 是否相等，就可以很容易得出转移了：
如果 $x$ 对应区间长度为奇数，$f(x,y) = cmp(x,y) $ 。
否则 $f(x,y) = (f(2x,2y) \land f(2x+1,2y+1)) \lor (f(2x,2y+1) \land f(2x+1,2y))$ 。
最终答案即为 $f(1,1)$。
时间复杂度：$O(n^2)$
期望得分：50分
算法三
不难发现问题的本质其实是每次选择某个线段树 $A$ 中的节点，交换其左右子树，问能否经过若干次操作后得到 $B$。
由于交换是可逆的，我们直接贪心计算出两棵线段树能够交换出的中序遍历字典序最小的线段树，然后检查是否相等即可。
时间复杂度：$O(nlogn)$
期望得分：100分
座位
from fsf，题解 by wzj52501
算法一
爆搜或状态压缩DP，可以打出 $n=12$ 至 $n=20$ 的表。
期望得分：10 - 30分
算法二
我们把小朋友的就座分成 $3$ 个阶段，第 $i$ 阶段中小朋友的就座方式符合第 $i$ 条规则。
经过一些分析可得，经过第 $1$ 个阶段后座位分布将变成这种样子（X表示已被占用）：
(.)X.X..X..X.X.X(.)即每个被占领的座位中间恰好隔了 $1$ 个或 $2$ 个座位，而开头和结尾最多有 $1$ 个空隙。
不妨假设第 $1$ 个和第 $n$ 个座位均被占用：
X.X..X..X.X.X设有 $a$ 个X之间空了 $1$ 个座位， $b$ 个X之间空了 $2$ 个座位。
那么X的数量为 $a+b+1$，需要满足 $2a+3b+1=n$。
第一轮的方案数为 $C(a+b,a)*(a+b+1)!$，第二轮的方案数为 $2^b*b!$，第三轮的方案数为 $(a+b)!$，根据乘法原理得 $ans=C(a+b,a)*(a+b+1)!*2^b*b!*(a+b)!$。
其他三种情况可以类似分析。
时间复杂度：$O(n)$
期望得分：100分
司机
from fsf，题解 by wzj52501
算法一
为了方便我们将序列扩展一倍，从而拆环成链。
对于每个询问，我们先预处理从每个位置 $x$ 出发在仅加一次油的情况下最多到达环上的哪个位置，设为 $p_x$。
枚举起始点 $x$，然后每次暴力将 $x$ 变成 $p_x+1$ ，直到已经绕了一圈。
时间复杂度：$O(k*n^2)$
期望得分：20分
算法二
我们将每个 $[x,p_x]$ 作为一个区间，然后去除所有被包含的区间。
找到这些区间中长度最小的区间 $[y,p_y]$，我们可以证明最优解中 $x$ 肯定在这个区间内的某个位置停留过至少一次。
反证法：如果最优解中 $x$ 未在区间内停留，那么说明某个时刻 $x < y$ 而下个时刻 $p_x +1 > p_y$，那么区间 $[y,p_y]$ 被区间 $[x,p_x]$ 完整包含，与题设相悖。
所以我们直接在 $[y,p_y]$ 中枚举起始点 $x$，然后同样每次暴力将 $x$ 变成 $p_x+1$ ，直到已经绕了一圈。
这个看上去好像只是优化了一下常数并没有什么卵用啊（
但是我们注意到区间 $[y,p_y]$ 是长度最小的区间，那么之后的每 $2$ 次移动至少会移动 $p_y-y+1$ 的距离，即至多 $2n / (p_y-y+1)$ 次暴力移动后就可以得到一个可行解。
所以单次询问复杂度就是 $O((p_y-y+1)* \frac {2n}{p_y-y+1})$ = $O(n)$，问题得解。
时间复杂度：$O(kn)$
期望得分：100分
