2022.8.9 模拟赛

T0

  小清新签到题，直接暴力 $bfs$ 就过掉了，但是中间要记录每个字母有没有被走过，走过就不走了。不然如果整张图全都是同一个字母的话时间复杂度就炸掉了 就在这里挂掉 9 分。

T1 杰哥的数论

  让你很快的判断分数 $\frac{p}{q}$ 在 $b$ 进制下是否为无限循环小数。

  根据一些常识，我们知道 $\frac{p}{q}$ 是否循环跟 $p$ 没啥关系，所以我们先给她们约分一下然后只关注 $q$（这里要特判 $p=0$）。

  然后我们发现给一个数 $\frac{1}{q}$ 乘上一个 $b$ 就相当于在 $b$ 进制下把小数点右移一位。所以如果这个小数是有限的的，那么就存在一个 $k\in N^{\ast }$ 使得 $q\mid b^k$。

  于是我们就考虑一直给 $q$ 除上 $\gcd (q,b)$，直到这俩玩意儿互质。此时如果 $q=1$ 那么就说明 $q$ 的质因子 $b$ 都有。那么也就是说存在 $k$ 使得 $q\mid b^k$，时间复杂度是 $O(T{\log }^{2}q)$ 的。

T2 杰哥刷墙

20pts

  有 $20pts$ 是矩形的情况，据机房大佬 $cmy$ 说这一部分的规律比较好找，答案就是：

$$ans=2^n+2^h-2$$

  就直接 $O(\log n)$ 快速幂就做完了。

T3 杰哥的数据结构

10pts

  直接按照题面模拟，复杂度 $O(m{n}^2)$。

40 pts

  维护一个线段树支持单点修改，区间查询，我们发现一个性质，对于一个左端点 $i$ 来说，她向右扩展之后的 $or$ 值是非严格单调递增的，所以我们可以考虑二分得到一个点 $pos$，这个点是第一个大于等于 $x$ 的右端点，那么这个点 $i$ 的贡献就是 $v-pos+1$。

  二分每次 $check(mid)$ 都要线段树区间查，所以复杂度是 $O(mn\log n)$ 的。

50 pts

  因为 $x=0$，所以答案就是：

$$ans=\frac{1}{2}(r-l+1)(r-l+2)$$

100pts

  这里我们在上面已经发现了，对于一个左端点 $i$ 来说，她向右扩展之后的 $or$ 值是非严格单调递增的。是因为二进制上的每一位变成 $1$ 之后就不可能再变成 $0$。正因为如此每次向外扩展的时候产生的不同的 $or$ 值只可能有 l o g 2 max ⁡ { a i } log_2 \max \{a_i\} log2​max{ai​} 个。

  知道这个性质之后，就会有一个很巧妙的做法。我们还是考虑线段树，但是这里的线段树的每个节点上维护的东西不一样了。对于一个节点 $(t[p].l,t[p].r)$，维护一个 $ans$ 表示这个区间的答案（也就是把题目中的那个式子的 $u,v$ 换成 $t[p].l,t[p].r$）。再维护一个从左端点向右扩展时每一次得到新的 $or$ 值时下标和从右端点向左扩展时得到新的 $or$ 值时的下标。

  因为 $or$ 值最多只有 $\log$ 个，所以 $pushup$ 可以在很快的时间内做完，然后题目给出一个区间询问的时候就线段树区间查询就好了。