August 08, 2020

你有 nn 个队列,每个队列有 aia_i 的容量。

QQ 次操作,每次给定队列的区间 [l,r][l,r],push 一个 xx。如果第 ii 个队列的元素个数 >ai>a_i,会自动 pop。

要求每次操作后求出所有序列中本质不同的元素个数。

n,m,ai,x105n,m,a_i,x \leq 10^5

June 26, 2020

给数组 AAnn 个节点的树,每个点有一个 11xx 颜色。

mm 次查询,每次查询树上只保留 [l,r][l,r] 内的所有节点,设一个极大连通块中出现奇数次数的颜色个数为 tt,则其对答案的贡献为 AtA_t ,即答案是所有连通块贡献的和,询问相互独立。

1n,m1051\leq n,m\leq 10^51x,Ai1041\leq x,A_i \leq 10^4

May 14, 2020

定义一个排列 pp 是好的当且仅当对于每个 k<max{p}k < \max\{p\},存在 1i<jn1 \leq i < j \leq n 使得 ai=k1a_i = k-1aj=ka_j = k

定义 fa(k)f_a(k) 为序列 aa 中数值 kk 的出现次数,假设所有合法序列集合为 SS,对于每个 k[1;n]k \in [1;n],求

(aSfa(k))mod998244353\left( \sum_{a \in S} f_a(k) \right) \bmod 998244353

n105n \leq 10^5

May 06, 2020

给定一个 nn 个点 mm 条边的无向图,其中每个点的点权是 [0;1][0;1] 范围内生成的连续型随机变量,求:

max{maxiVxi+max(u,v)E(xu+xv)}\max \{ \max_{i \in V} x_i + \max_{(u,v) \in E} (x_u + x_v) \}

的期望,答案对 998244353998244353 取模。

n25n \leq 25。(实际上可以跑 n30n \leq 30。。。