ARC159

回归信息学做的第一场比赛啊。

A

看完第一眼就觉得应该是可以$\%n$ 做的，不难。

因为边的起点终点都是可以 $+n$ 的，但是比较麻烦的是自己到自己的 $+n$ 。

也就是说需要在 $nn$ 的图中找环，可以写，但是有更加简单的做法，直接在 $2n2n$ 的图上跑 Floyd 即可。

需要记住，在显示赛上，运行时间短并不是第一目的。

第一目的是最快的找到一个能做的做法，然后赛后再去想最优解。

$O(n^3+q)$

Submission #42207812 - AtCoder Regular Contest 159

B

比较巧妙的一道题目，可以发现，减时差不变。

因此，最大公约数一定是差的因子。

因此我们可以每次把 $A,B$ 除掉当前的最大公因数，然后找下一个最早出现的因子是哪个，这样不断下去，每次至少 $/2$ 。

时间复杂度：$O(\log^2{max(A,B)}+\sqrt{|A-B|})$

Submission #42208144 - AtCoder Regular Contest 159

C

好题。

显然，每次加 $\frac{n(n+1)}{2}$ 。

不妨考虑 $\%n$ 意义下，所以不能得到奇数的必要条件是 $\%n=0$ ，偶数的必要条件是 $\%{\frac{n}{2}}=0$ 。

但是是充分吗？

不妨考虑这么一组构造：

$1,2,…,n$

$n-1,n,n-2,n-3,…,1$

这样，一号位置相对 $-1$ ，二号位置相对$+1$ 。

显然奇数可以用这样的构造完成。

偶数且 $\%{n}=\frac{n}{2}$ 时就构造：$-\frac{n}{2}+1,…0,…\frac{n}{2}$ 。（这一串的和显然是 $\frac{n}{2}$ ）

然后一个$n,n-1,n-2,…,1$ 带走。

但是呢？

这样可能会有点慢。

考虑加速，我们可以不相对 $-1+1$ ，而是相对 $-k+k$ ，思考一下，类似的。

时间复杂度：$O(n^2)$

Submission #42209134 - AtCoder Regular Contest 159

D

比 $C$ 题简单。

直接离散化，然后段前段中用线段树处理一下就行了，搞两个 $key$ 值。

时间复杂度：$O(n\log{n})$

Submission #42209585 - AtCoder Regular Contest 159

但是呢，既然是复健训练，看看luogu题解。

woc，set+二分，对哦。

好打飞。

学之。

Submission #42212817 - AtCoder Regular Contest 159

E

不会做，看题解。

几个引理：

  1. x,x+1 在树上一定为祖先儿子关系。-》转化为树上距离。
  2. 加上dis(c,d)。-》由树上距离转为求虚树点的个数。
  3. 非[c,d]的点在虚树上都在c->d路径上。-》所有要求的量全部转化为了求出 $c->d$ 的路径。

至此，又由于题目保证了 $max(\frac{a_i}{b_i},\frac{b_i}{a_i})≤2$ ，所以时间复杂度为 $\log{}$ 。

做完。

真的退化成原始人了，一点思路都没有了，悲QAQ。

Submission #42213921 - AtCoder Regular Contest 159

F