集训

好了，又是爆零的一天，恭喜我自己 $\text{score：0 + 0 + 0 = 0 rk：27/27}$ Problem A：小卖部题目描述ysgh 是一名数数大师。 现在小卖部有 $n$ 种商品，第 $i$ 种有 $a_i$ 个，价格为 $b_i$。 ysgh 总共去了 $Q$ 天小卖部，第 $i$ 天他只会购买编号在 $l_i \sim r_i$ 的商品。他的卡里有 $c_i$ 元，因此他只能购买价值和不超过 $c_i$ 元的物品。 ysgh 想要知道有多少种购买物品的方案。由于答案很大，你只需要输出答案对 $1000000007$ 取模后的结果。两种方案被认为是不同的当且仅当存在一种物品，其购买数量不同。 当然，ysgh玩了个小花招，你需要通过上一个询问的答案来推导下一个询问的参数。 数据范围对于所有测试数据，满足 $1 \le n \le 10000, ~ 1 \le Q \le 50000, ~ 1 \le a_i, b_i, c_i \le 1000, 1 \le l’_i, r’_i \le n$ 题解令 $C = 1000$ 首先看得出来可以用生成函数搞，显然答 ...

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

中下 $\text{score：24 + 40 + 0 = 64 rk：23/34}$ Problem A：Mythological V题目描述小S打算送给小M一棵 $n$ 个点的圣诞树，点从 $1$ 到 $n$ 标号，他打算给树上挂上 $m$ 个礼物，每个礼物在树上的某个点上，礼物可以重叠。 小M给了小S $q$ 个限制，其中第 $i$ 个形如“第 $a_i$ 个礼物和第 $b_i$ 个礼物在树上的最短路径经过了点 $c_i$”。 小S想要构造出符合小M条件的挂礼物方案。可怜的小S当然不会啦，所以他向你求助。 数据范围对 $100\%$ 的数据，$n, m \le 250, ~ q \le 5 \times 10^4$ 题解好久没写过 $2-SAT$ 了 虽然我的暴力虽然 $\text{WA}$ 了但竟然没有 $\text{T}$？说不定改对了能过呢 考虑两个礼物 $a, b$ 放置位置经过 $c$ 代表着什么，说明 $a, b$ 放置的位置在以 $c$ 为根的树上位于不同的 $c$ 儿子的子树上 那么现在以 $1$ 为根，设 $g_{i, j, 0}$ 表示第 $j$ 个礼 ...

没交 $\text{score：NULL rk：NULL}$ Problem A：区间第k小题面 题解先考虑离线，整体二分，二分答案 $mid$，处理所有 $\le mid$ 的数，那么此时问题就转化为在区间出现次数不超过 $w$ 的数有多少个 不妨关注每个数对询问区间 $[L, R]$ 的贡献，对某个数 $a$，若它是从左往右后 $w$ 个出现为 $a$ 的数，则它的贡献为 $1$，若为倒数第 $w + 1$ 个则贡献为 $- w$，剩下的贡献都为 $0$，那么我们就可以开一个队列，首先总大小（即不删去超过 $w$ 的）算出来，此时计算需要删去的，队列大小未到 $w$ 时没有需要删的，若大于 $w$ 时每次就让队首点贡献减去 $w + 1$，当然之前多减的还要加回来 那么现在就可以考虑从离线转成在线，在整体二分的过程中每一层（即每一次二分的 $[l, r]$）都会建一些可持久化线段树，而它又最多会修改 $O (n \log n)$ 次，开 $O (n \log^2 n)$ 个节点，所以把每一层的可持久化线段树都存下来，在线二分时即可直接查找，总时间复杂度 $O ...