模拟赛 20 题解

数论+dp+模拟+主席树+哈希

A.方程的解

首先特判掉是 $0$ 的情况。

我们可以通过 $exgcd$ 求出方程的一组特解 $x_0,y_0$。

那么可以得到方程的特解就是 $x=x_0+p,y=y_0-q$。

每次 $x+p$，就让 $y-q$ ，来调整 $x,y$ 的大小。

可以先把 $x$ 调整为最小正整数，再看 $y$ 调整了多少 $q$ ，$+1$ 就是解的数量。

注意特判和细节。

B.染色

枚举子树内选了几个黑点，考虑每条边的贡献。

C.光

恶心模拟题。

首先，我们发现光是沿对角线走的，并且黑白染色后只会处于同种颜色（类似于国际象棋的教士）。

所以对于每个坏点，我们可以在两条对角线的方向保存它们。

我们可以表示为 $(x+y,x)$ 和 $(x-y,x)$，这样可以二分查找来加速撞到坏点的过程。

一开始可以先让它撞到坏点，再循环。

细节比较多。

D.无向图问题

给定字典序大小关系 $\{p_i\}$，我们可以统计出每个节点的贡献，看它贡献在了 $p$ 的第几位。

朴素做法就是直接跑 $dij$，松弛时直接 $O(n)$ 比较两条路径的权值。

那么我们可以按照字典序从高到低位哈希，这样就可以 $O(1)$ 比较。

但是我们每新加入一个点，路径的哈希值会改变，考虑可以使用权值线段树维护到每个 $[1,n]$ 的出现次数，在 pushup 的时候哈希起来判等。

由于在更新时，要继承上一次的状态，所以可以采用主席树。

记住在开堆的时候重载小于号是反的。