mydcwfy's Blog

题意：给定 $n$ 个点的树，定义一个点是好的当且仅当它和它的所有祖先都是黑色的，从所有点都是白点开始，任选一个不好的点染成黑色，问期望染多少次使得所有都是黑色。$n\leq 2\times 10 ^ 5$，对 998244353 取模。

题意：给定两个长度为 $n$ 的字符串 $S, T$，定义 $f(S, i)$ 表示将前 $i$ 个字符放在最后得到的字符串，问有多少个 $(i, j)(0\leq i, j <n)$ 满足 $f(S, i)\leq f(T, j)$。$n\leq 2\times 10 ^ 5$，$S, T$ 仅由小写英文字符构成。

题意：有 $n$ 个计数器，每个计数器有一个上界 $a_i$，每次操作会将一个计数器清 0，然后将其他计数器 +1。问期望多少步每个计数器都达到上界。保证 $0 = a_1 \leq a_2 \leq \dots\leq a_n\leq 10 ^ {18}$，$a_n > 0$，$n\leq 2\times 10 ^ 5$，答案对 998244353 取模。

All Accepted。

题意：求

其中 $H(x)$ 表示 $x$ 所有质因子的乘积（去重后）。$n\leq 10 ^ 9$，$T(T\leq 5)$ 组数据，满足 $\sum n\leq 2\times 10 ^ 9$。20s。

已改 ABCD，E 太难写了 /tuu

已改 ABCDE。

题意：交互题。定义 $f(x)$ 为严格大于 $x$ 的最小完全平方数，$g(x)$ 为小于等于 $x$ 的最大完全平方数。你需要猜一个 $\in[1, 10 ^ {12}]$ 中的一个数 $a$，用少于 64 次的询问得到答案，单次你给出 $t(t\in [0, 10 ^ 9])$，会返回 $a + t$ 是否满足 $x - g(x) < f(x) - x$。$T(T\leq 2\times 10 ^ 3)$ 组数据，2s。

题意：给定一个长度为 $n$ 的序列，问有多少个重排序列的方案使得相邻两个数的和都 $\geq k$。$n\leq 2\times 10 ^ 5$，$a_i, k\leq 10 ^ 9$。

靠着 D 猜到结论好不容易上分了，第三次上黄（

赛后改题：All Accepted。

题意：给定一个长度为 $2n$ 的序列，其中 $[1, n]$ 各出现 2 次，对序列一直操作直到不再变化：从前向后操作每一个数，如果这个数不为 0 并且在其后面存在一个和其相等的数，则将这个数减 1。可以证明最后存在 $n$ 个数不为 0。先给出这 $n$ 个位置，求有多少个序列满足操作后剩这些位置。$n\leq 600$。

按序给出 $m$ 次操作或询问：

1. 新增元素 $(x, y, z)$，新给一个编号，获得他需要消耗 $a$ 点血量，获得他后可以获得 $b$ 点血量。
2. 编号为 $k$ 的元素被删除了。保证不会重复利用或重复删除编号。
3. 给定三元组 $(x, y, z)$，问要获得所有严格小于等于 $(x, y, z)$ 的元素需要开始时有多少血量才不会出现血量 $< 0$ 的情况。

元素和询问次数都不超过 $50000$，$x, y, z\leq 10000$，$a, b\leq 10 ^ 9$，2s。

题意：给定模数 $m$ 和 $T$ 次询问，每次询问给定 $x, y$，问是否 $z$ 满足存在 $x ^ z\equiv y\pmod m$。$m\leq 10 ^ {18}, T\leq 2\times 10 ^ 4$，保证 $m$ 是奇质数的次幂，$\gcd(x, m) = \gcd(y, m) = 1$，3s。

题意：给定一个长度为 $n$ 的序列，$q$ 次给出 $l, r$，问 $[l, r]$ 区间能否拆成两个集合使得第一个集合的 OR 是第二个集合的 AND。$n, q\leq 10 ^ 5$，$0\leq a_i < 2 ^ {30}$，3s，1GB。

题意：求 $x ^ a \equiv b\pmod p$ 的解数，$a, b, p$ 给定。$a, b, p\leq 10 ^ 9 + 1$，$p$ 是奇数，$T(T\leq 1000)$ 组数据。

题意：给定 $n$ 个数，要求把他们分成红蓝两组，要求都不为空，使得红组的 AND 和蓝组的 AND 相同，求划分方案。$n\leq 50, a < 2 ^ {20}$。

挂 18pts 送走 Au，rk65 Ag。

题意：给定一个序列 $a$，定义 $f(\{l, r\}) = \{\min(a_{l\dots r}), \max(a_{l\dots r}) \}$，$q$ 次给定 $l, r$，问 $\{l, r\}$ 经过多少次 $f$ 函数后会变为 $\{1, n\}$，或者报告不可能。$n, q\leq 10 ^ 5$，1.5s，1024 MB。

二维平面上有 $n$ 个红点和 $n$ 个蓝点，每个点有一个权值 $vr_i/vb_i$，$q$ 次询问，每次给定 $L, R$，求满足 $[xr_i R]$ 并且 $[yr_i < yb_j]$ 的 $(i, j)$ 中 $vr_i + vb_j$ 的最大值。$n\leq 10 ^ 5$，$q\leq 5\times 10 ^ 5$。

题意：令 $f(n) = \displaystyle \sum_{i = 1} ^ n \sum_{j = 1} ^ n [\text{lcm}(i, j) + \gcd(i, j)\geq n]$，求 $f(n)$ 的前缀和。$T(T\leq 10 ^ 5)$ 组数据，$n\leq 10 ^ 5$。