Description

维护一个二进制数 $x$，支持两种操作：

• $x\gets x + a \cdot 2 ^ b$
• 询问 $x$ 第 $k$ 位的值

共 $n$ 次操作。

$1\le n\le 10^6,|a|\le10^9,0\le b,k\le30n$

Read More

$+1$ 操作的贡献不好计算，但是由于操作数很少，我们完全可以记录下最低 $\log k$ 位的状态，这样总状态数是 $O(k^3)$ 的，转移 $O(1)$，故总复杂度 $O(k^3)$。

Read More

准备倒序的把这个月做过的有意思的题都写一写简要题解，当然也可能有些稍微古早一些的题目。

Read More

CF1784D Wooden Spoon

这类问题通常可以按两种顺序 dp，本题中我们需要限制每组中最小的数依次递减，一种显然的想法是从大到小 dp，对于每个数考虑该数是与之前的某些数构成一组还是不做任何操作，类似于 ARC093F，当然由于我们需要对第一个数的每种取值计算方案数，所以 dp 需要反向，转移过程中的组合系数可能会很反常。另一种是从后向前，从小到大 dp，在填数的过程中留下一些空位，在后期对每个数决策是去填上之前的空位还是新开一组。两种方法都是 $O(n2^n)$ 的。

Read More

Description

$n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子，颜色为 $c_i$。A 和 B 轮流行动，A 先手，每人有两种操作：

• 选择一堆石子并从中取出任意个石子。
• 选择一种颜色并从若干堆这种颜色的石子中取出不超过 $m$ 个石子。

不能不取。不能操作的人失败。

Read More