思维

初来乍到，4h20min的题我打了2h，成功垫底，恭喜我自己 $\text{score：20 + 0 + 0 = 20 rk：26/27}$ Problen A题目描述 题解看他们都会写。。这种比较复杂的容斥我几乎都没写过。。 前置知识：高维前缀和举个例子，对比如现在要求解 $\sum\limits_{s = 0}^{2^n - 1}\sum\limits_{j \in s} a_j$（此处 $\in$ 是二进制表示下的意义），直接枚举子集是 $O (3^n)$ 的，那么高维前缀和可以优化到 $O (n2^n)$ 考虑低位前缀和，比如三位，我们是不是可以这么写 123456789101112for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) for (int k = 1; k <= n; k ++) a[i][j][k] += a[i - 1][j][k]for (int i = 1; i <= n; i ++) for (int j = 1; ...

成功由垫底转至中下水平。。 恭喜。。我？ $\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：NULL rk：NULL}$ Problem A：Sasha And CirclesProblem B：Choosing Ads题目描述给定一个长度为 $n$ 的序列和一个整数 $p$。 有 $m$ 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 $p\%$ 的数。 输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 $\lfloor \frac{100}p \rfloor$ 数据范围对 $100\%$ 的数据，$n, m \le 1.5 \times 10^5, ~ 20 \le p \le 100$ 题解先考虑 $p = 51$ 的情况，很明显就是求区间众数 有一个经典区间众数套路，给数字 $i$ 一个数组 $c_i$，设当前众数 $p$，每次加一个数字 $t$，若该数字等于 $p$，则 $c_p ++$，反之则 $c_p –$，若删前 $c_p = 0$，则 $p = t$，同时 $c_p = 1$ 这样子虽然没有计算每种数 ...

晚了几天写，暴力场 $\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 ...

题目描述有 $N$ 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 $T$ 秒。每个烟花只能被点燃一次。$1$ 号站在原点，$i$ 号 $(1 \le i \le N)$ 到 $1$ 号的距离为 $X_i$。保证 $X_1 = 0$，$X_1, X_2, …, X_N$ 单调递增（可能有人位置重叠）开始时，$K$ 号的烟花刚开始燃烧，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数 数据范围对 $100\%$ 的数据，$1 \le K, N \le 10^5, ~ 1 \le T \le 10^9, ~ 0 \le X_i \le 10^9, ~ X_1 = 0$ 题解很显然所有人一定会不断向拿烟花的人靠近 可以发现，一个拿烟花棒的人和另一个人相遇时，让另一个人跟着拿烟花的人走直至烟花在灭掉的瞬间将烟花传递的情况和在相遇时传递时一样的（注意相对位置， ...

题意在一棵树上选出 $k$ 条可相交的链使得被覆盖的点数最多，求该最大值 题解说实话这个解法是真的厉害 显然题目可以看作选出 $k \times 2$ 个叶子节点，然后将它们互相连接最终覆盖的点的最大值 再考虑删去选中的 $k \times 2$ 个叶子节点后，向内一层的点最多只会有 $k \times 2$ 个点有贡献 同理继续内推 于是上述过程即由叶子节点开始拓扑，对于拓扑的每一层，令点 $i$ 拓扑深度为 $depth_i$，$total_i$ 表示拓扑深度为 $i$ 的点的个数，即，将每一个拓扑层重新看作叶子节点，再在当前拓扑层中选出至多 $k \times 2$ 个“叶子节点”，故$$\min (k \times 2, total_i)$$即为拓扑深度为 $i$ 的层的答案贡献 将它们累加起来即可 复杂度 $O (n)$ 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768 ...

首先显然要先把原数组重新映射一下，令映射过后的数组为 $a_i$ 因为题目要求 $|a_j - a_i| >= K$ 的可以置换，那么反之，则有 $|a_j - a_i| < K$ 的 $i, j$ 相对位置不变 故最简单的方法就是对于每个 $i$，将其与所有满足 $|a_j - a_i| < K$ 的 $j$ 连边，然后跑一边拓扑，复杂度 $O (n^2)$ 然后考虑在 $a_i$ 连的这么多边中，若是存在边 $(i, j), (j, k), (i, k)$，其中 $i < j < k$，那么显然 $(i, k)$ 的存在性是无关紧要的 又 $a_i$ 可连边的权值范围是 $(a_i - K, a_i) \cup (a_i, a_i + K)$，那么只需要分别向两个区间中标号最小的那个点连边就好了（单向边，并且一定向标号比自己大的点连），这样就相当于是将原来的乱七八糟连接的图变成了一条条单向的链，并且这些链可以覆盖原来的所有情况 代码1234567891011121314151617181920212223242526272829303132333435 ...