比赛链接

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 Potassium

找出第 $n$ 小的数 $k$，满足 $k$ 的 $10$ 进制表示是 $k$ 的二进制表示的后缀， $n\le 10000$。

$$(1)_2=1$$

$$p\times 10=(p<<3)+(p<<1)$$

数归， $(10^k)_2$ 后 $k$ 位都为 $0$ 。按位从低到高枚举填 $0$ 或者 $1$ ，填数不影响前 $k-1$ 个位置的二进制表示，仅需要判断填数后第 $k$ 位的十进制和二进制相等与否即可。需要用大数，复杂度$\mathcal{O}(nl)$。

upsolved by Potassium

给一个 $n$ 个点的多边形的三角剖分，边长均为 1 。 $q$ 次询问，每次询问两点间距离。 $n,q\le 10000$。

考虑离线（其实在线也行）处理询问。

分治，每次将多边形尽可能均匀地分成 $A,B$ 两部分，询问中两点分别在两边的直接 $BFS$ 处理出距离，在同一边的递归处理。

注意需要在保证复杂度的情况下，每次的修改不能影响孩子或右半部分。复杂度 $\mathcal{O}(n\log n)$。

solved by Potassium

给一个出题规则和题目难度，问怎么出题。

签到题，照题意模拟即可。

solved by Potassium

有个蛤蟆想要从左岸跳到右岸，其中有一些石头 $(n\le 1000)$ ，他还拿着一块石头可以放下来。每次只能跳到石头上，手里的石头只能用一次。问从左岸跳到右岸最长的一步最短需要多长。

设 $dis[0][i]$ 表示没用石头、 $dis[1][i]$ 表示用了石头的情况下，从左岸跳到 $i$ 最短的最长步，建图后类似最短路跑一遍即可。

solved by Potassium

给 $n$ 个生成器 $x_0^{(j)},a^{(j)},b^{(j)},c^{(j)}$ ，他们分别按照 $x_{i+1}=(ax_i+b)\bmod c$ 生成一些序列，找出正整数序列 $t_j\ge 0(1\le j\le n)$ ，使得 $s=\sum_{j=1}^{m}x_{t_j}^{(j)}$ 最大，且 $s\bmod k\ne 0$。

$0\le a^{(j)},b^{(j)},c^{(j)},x_0^{(j)}\le 1000,1\le n\le 10000,k\le 10^9$ 。

在看到数据范围之前这是个难题.jpg

循环节 $\le 1000$ ，找出每个序列的最大 $mx$ 和合法次大 $se((mx-se)\bmod k\ne 0)$ 即可。

solved by qxforever

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

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

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

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