比赛链接

solved by qxforever

给一个 $n\times n$ 的矩阵。初始 $a_{ij}=i+j$ 。

有 $q$ 次操作，每次操作求矩阵的一行或一列的和，并将该行/列置为 $0$ 。

$n\leq 10^6,q\leq10^5$

对第 $i$ 行的操作会对之后第 $j$ 列产生 $-(i+j)$ 的贡献。记录即可。

solved by qxforever

给一个 $n$ 个点 $m$ 条边的有向图，求图的一条哈密顿回路。

$n\leq 10^5,m\leq n+20$

注意到 $m\leq n+20$ ，若存在哈密顿回路，则最多有 $20$ 条边的出度大于 $1$ ，且出度为 $1$ 的点相连是链状的。

将出度为 $1$ 的点用并查集缩点，记录链的起点。在缩完点的新图中，只保留与链的起点相连的边。DFS 搜一搜即可。