2022.8.9 Mock Competition

T0

  小清新签到题,直接暴力 $bfs$ 就过掉了,But have you ever been walked to record each letter in the middle,Don't go through.Or if the picture is all the same letter time complexity just blew up Here is the hang up 9 分.

T1 Jacob arithmetic of

  Allows you to quickly determine the score $\frac{p}{q}$ 在 $b$ Whether in base for infinite decimals.

  According to some common sense,我们知道 $\frac{p}{q}$ Whether the cycle with $p$ 没啥关系,So let's give them a reduction of a fraction and then focus on $q$（Here are special for $p=0$）.

  Then we found that give a number $\frac{1}{q}$ 乘上一个 $b$ 就相当于在 $b$ Base the decimal point moves to the right a.So if the decimal is limited,那么就存在一个 $k\in N^{\ast }$ 使得 $q\mid b^k$.

  So we will consider has been to $q$ 除上 $\gcd (q,b)$,Until the two thing co-prime.此时如果 $q=1$ 那么就说明 $q$ 的质因子 $b$ 都有.So that is there $k$ 使得 $q\mid b^k$,时间复杂度是 $O(T{\log }^{2}q)$ 的.

T2 Jacob paint the walls

20pts

  有 $20pts$ Is a rectangular case,According to the computer room bosses $cmy$ The law of the said this part is better looking for,答案就是：

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

  就直接 $O(\log n)$ Finished it quickly power.

T3 Jacob data structure

10pts

  Simulated according to the problem face directly,复杂度 $O(m{n}^2)$.

40 pts

  Maintaining a line segment tree support single point change,区间查询,我们发现一个性质,对于一个左端点 $i$ 来说,After her extension to the right of $or$ Value is strictly monotone increasing,So we can consider to get a binary point $pos$,This is the first greater than or equal to $x$ 的右端点,那么这个点 $i$ 的贡献就是 $v-pos+1$.

  Binary every time $check(mid)$ To segment tree range check,所以复杂度是 $O(mn\log n)$ 的.

50 pts

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

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

70pts