比赛

好了，又是爆零的一天，恭喜我自己 $\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：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 ...

D - Anticube说实话质因数分解的题都挺有意思的 首先对于每个数，显然里面存在的质数三次方的因子都是无贡献的，那么将其的每个质因数化简，即对于质因子 $p^k$，将其变为 $p^{k ~ mod ~ 3}$ 那么两个数若乘积为完全立方数，则必须满足它们的每一个相同质因子都是“互补的”（即次数相加为 $0$ 或 $3$），同时显然一定不存在大于一个 $> \sqrt[3]n$ 的质因数 $p$，那么解法就很显然了 就是筛出 $[2, \sqrt[3]n]$ 的质数，然后对每一个数进行化简，然后将化简后的数的计数器加一，最后在所有两两“互补”的数中取 $max$ 求和即可 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 ...

D - Stamp Rally整体二分 + 并查集常规操作 不过记得每次仅将当前递归时使用的并查集删去即可，之前的保留，所以对于那些被忽略的答案的位置，也需要递归到然后加入并查集 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154#include <iostream>#include <cstdio>#include ...