VP: AtCoder Regular Contest 125 (ARC125)

tony102

2021 年 10 月 30 日

2354 次浏览

暂无评论

1203字数

总结比赛记录

其实也不是 VP 是吧，就是连续做完一场 ARC

决定从以后开始，VP 总结里面题目的题解单独写，总结里面只写自己的思路和收获的地方。

## A

开始还写假了。

有一个很 naive 的想法就是，假如现在的 $a_1$ 跟 $b_{cur}$  是一样的，就操作一次弹顶。否则就分别从前和从后面开始找第一个一样的，然后就在这两者之间不停地反复横跳。非常容易 hack 掉，比如说 `1 1 0 0 1 1 `， 这样的话当前的 $a_1$ 假如要变成 $0$ 它就会找 $a_3$ ，再要变成 $1$  的时候明显 $a_2$ 就行了，但是直接算成了 $a_1$。但是这样居然还是过了 12 个点！

所以就只需要改进一下这一种情况就可以了，也就是跳过去的时候有没有更加接近的不同数字。

## B

草，傻逼了。瞄了一眼题解才发现方向错了。

最开始想的是，题目就是要求 $x^2 \equiv y \mod z^2$ ，然后 $x^2 = kz^2$。发现这样的转化=没转化。

看到 $N \leq 10^{12}$ 的话，应该还是很好想到最后解法肯定是 $O(\sqrt{n})$ 的。发现同余没有前途就要折回去看看别的性质。最后 Coding 的时候要注意范围。

[Solution for B](https://tony102.com/archives/164/)

## C

这个构造....一言难尽

但是我觉得 $P_1 = a_1$ 这个事情还是很好想的。但是 $P_2$  一定 $=1$ 确实需要多发现几组才可以大概发现。

多玩几组其实就出来了...没什么好总结的，题解就写在这里算了。

$P_1 = a_1, P_2 = 1$，从 $P_3$ 开始就填 $a$ 中还没有出现过的数字即可。复杂度 $O(N)$

[Submission](https://atcoder.jp/contests/arc125/submissions/26872580)