分块

成功由垫底转至中下水平。。 恭喜。。我？ $\text{score：55 + 0 + 0 = 55 rk：21/33}$ Problem A：猜想题目描述 数据范围对于所有测试数据，记 $l$ 表示 $n$ 的长度，则 $1 \le l \le 2 \times 10^5$，保证 $n$ 的最高位为 $1$，且除此之外的 $l - 1$ 位使用 $\text{std::mt19937}$ 随机生成 题解考场上敲了个 $55$ 分的暴力，本来想说看能不能枚举每一位然后直接算它的状态，然后不行 出题人提供的题解没看懂，就看了看其他 $A$ 掉的人的思路 首先考虑分块，使分出的块尽量大，取块大小 $L = 24$，对每一块分别处理 处理当前块时先不考虑右移删 $0$ 的情况，先只考虑乘三加一的情况，最后只要在答案上加上二进制位总数即可 设第 $i$ 块储存的数为 $a_i$ 类似线段树处理乘法时的操作，记两个变量 $mul, add$ 记录总共乘了多少，总共进位多少，那么转移到 $a_j$ 时则有 $a_j = mul * a_j + add$，以此类推 细节就看代码吧 12345678 ...

晚了几天写，暴力场 $\text{score：40 + 40 + 45 = 125 rk：17/30}$ Problem A：Tree题目描述 数据范围对 $100\%$ 的数据，$1 \le n \le 10^8, ~ 1000 \le k \le 10^8$ 题解很容易发现，满足条件等价于要求树中没有任意一条从根出发的路径经过超过 $k - 1$ 个左儿子 然后就是一个很妙的转换，将树按如下规则变为括号序列： 子树 $u$ 括号序 = ‘(‘ + ‘$u$ 左子树括号序’ + ‘)’ + ‘$u$ 右子树括号序 给个题解的图例 实际上可以不用考虑叶节点，那么现在将 $n$ 变为 $n - 1$，$k$ 变为 $k - 2$ 那么现在的任务就变为在坐标系中将左括号看作往右上角走，右括号看作往右下角走，从 $(0, 0)$ 最终走到 $(2n, 0)$ 的方案数，并需要满足过程中纵坐标始终在 $[0, k]$ 中的方案数（注意此时 $n, k$ 已变化） 这就是类似卡特兰数，但是有两条限制，即不能碰到 $y = - 1$ 也不能碰到 $y = k + 1$ 又从 $(x1, y1 ...

树上莫队首先有一道题 王室联邦题目大意给定一棵树，将树分为大小范围为 $[B, 3B]$ 的连通块集，求方案 树上分块方法之一类似贪心，用栈维护还没有在连通块中的子节点，对于递归到的当前的点 $p$ ，扫描它的子树，能拼凑就拼凑 但是注意最后可能还会有一些点（一定包括根）剩下，那么将这些点并到最后一个连通块即可 显然每个连通块都满足大小为 $[B, 3B]$ 核心代码123456789101112131415void DFS (int root, int father) { int bot = top; for (int i = Head[root]; i; i = Link[i].next) { int v = Link[i].to; if (v == father) continue; DFS (v, root); if (top - bot >= B) { capt[++ bind] = root; while ...