比赛链接

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$ 位的十进制和二进制相等与否即可。需要用大数，复杂度$O(nl)$。

upsolved by nikkukun

给一个仙人掌，现在要你选一条原图中的边 $A$ 和一条原图中不存在的边 $B$，使得删掉 $A$ 再加入 $B$ 后的图还是个仙人掌，求方案数。

$n \leq 50,000$

若删掉的边是桥，则仙人掌变成两个仙人掌，在它们之间任意连边都是合法的新仙人掌。假装把仙人掌当做是树 DP 可以得到子树大小。

若删掉的边在环上，则删掉之后这个环变成了一条链，且与原来和它连接的桥成了一大堆桥，我们暂时称之为桥连通块。推一推可以发现新添加的边只能在某一个桥连通块内自己连接（否则不是仙人掌），那么这个连通块的贡献是块内任意两点连接的个数减去已有的边数，即 $\binom s2 - (s - 1)$，其中 $s$ 为连通块内点的个数。

实现时，可以用并查集维护桥的连通块，再对每个环考虑将它上面的每个边拆掉之后，变成的新连通块点数 $s$ 即可。

upsolved by Potassium

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

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

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

注意需要在保证复杂度的情况下，每次的修改不能影响孩子或右半部分。复杂度 $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)$ 即可。

unsolved

unsolved

idea from nikkukun, qxforever, potassium, implemented by nikkukun

给一个 $n$ 位 $01$ 串，你可以猜 $n + 500$ 次这个串是什么。如果你全猜对，那就告诉你 $n$；如果你有恰好有 $\dfrac n2$ 个位置猜对，告诉你 $\dfrac n2$；否则告诉你 $0$。

$n \in [1, 1,000]$

假设已经找到了一个串使得恰好有 $\dfrac n2$ 个位置猜对，那么我们只要用 $n-1$ 次询问反转串中二元组 $(i, i+1)$ 后的结果，就能知道整个串任意两位之间的答案正确性：

1. 为 $0$，则 $(i, i+1)$ 要么都猜对，要么都猜错
2. 为 $\dfrac n2$，则 $(i, i+1)$ 一对一错

现在考虑怎么在 $500$ 次里找到这个恰好有 $\dfrac n2$ 个位置猜对的串。可以随机去找：一次随机中命中该串的概率是 $\binom {1000}{500} \times 0.5^{1000} = 2.52\%$，$500$ 次能找到这个串的概率是 $99.99\%$。

solved by qxforever

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

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

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

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

solved by nikkukun

长度为 $n$ 的水平线上有一些方块堆叠的地形，位置 $i$ 处地形高度为 $h_i$。你可以在已有的地形上加一些方块，但是要保证每一块方块添加时，它的左下、正下、右下不能是空的。

现在你可以添加最多 $m$ 次，求能搭出的最高高度。

$n \leq 10^5$，$h_i \in [1, 10^9]$，$m \in [0, 10^{18}]$

贪心的情况下搭出的最高点是个金字塔形状的，因此可以二分答案后以每个点作为最高点所需要的方块总数判断。

假设当前最高高度为 $x$，位置在第 $i$ 个，则需要加方块的左端点 $l$ 应当满足 $h_l \geq x - (i - l)$，即 $h_l - l \geq x - i$，在单调栈上二分可以找到最近的左端点；右端点同理可求。

注意到能额外添加的高度不会超过 $n$，因此二分的上界与 $\max \{h_i\}$ 同级，总时间复杂度 $O(n \log n \log \max \{h_i\})$。