eJOI 题目选做

元素周期表

$n\times m$个网格，事先标记$q$个位置。

操作：如果$(x_1,y_1),(x_1,y_2),(x_2,y_1)$都被标记了（$x_1\ne x_2,y_1\ne y_2$），那么就可以标记$(x_2,y_2)$。

你需要在这个$q$个标记的基础上再加尽量少的标记，使得执行上述操作若干次可以标记所有格子。

$n,m,q\le 2\times 10^5$。

并查集 二分图

把$(x,y)$当成二分图的一条边。那么上文中的$(x_1,y_1),(x_1,y_2),(x_2,y_1)$显然是在一个连通块内的。

一次操作不会改变连通块数量。

操作可以让连通块变满。

因此我们需要最少的标记把所有连通块连在一起。

统计连通块数量即可。

代码

塔

一个序列，初始时只有一个$1$。每次可以选择一个区间，把它们的和加到序列的末尾。问最少多少次操作可以构造出数字$s$。

多组询问。

$s\le 10^{18}$。

一开始序列的和是$1$。注意到你可以一次操作

• 让序列的和乘 2
• 让序列的和乘 2 减 1

因此我们想办法让序列总和为$s$，再操作一次就可以得到$s$了。

容易证明这是答案的下界。

时间复杂度$O(t\log_2s)$。

代码