我的文章

    我的文章

    • 「CF917D」Stranger Trees

      CF917D

      给出一棵大小为 nn 的树。

      对于每个 kk (0≤k≤n−10 \leq k \leq n - 1),你需要求出有多少个大小为 nn 的带标号树与原树有恰好 kk 条重合的边。答案对 109+710^9 + 7 取模。

      数据范围:1≤n≤1001 \leq n \leq 100。

      时空限制:11s / 250250MiB。

    • 「CF1830D」Mex Tree

      CF1830D

      给出一棵包含 nn 个节点的树。你需要给每个节点染上数字 00 或 11。

      路径 (u,v)(u, v) 的权值,等于从 uu 到 vv 的最短路径上所有节点数字的 MEX。一种染色方案的权值等于所有 1≤u≤v≤n1 \leq u \leq v \leq n 的路径 (u,v)(u, v) 的权值之和。

      请求出所有的染色方案中,可能的最大权值。

      数据范围:1≤n≤2×1051 \leq n \leq 2 \times 10^5。

      时空限制:33s / 256256MiB。

    • 「CF1444C」Team-Building

      CF1444C

      给出一张包含 nn 个点 mm 条边的无向图,每个点有一个颜色 cic_i (1≤ci≤k1 \leq c_i \leq k),求有多少组颜色对 a,ba, b (a<ba < b) 满足保留颜色为 aa 或 bb 的节点的导出子图是二分图。

      数据范围:1≤n≤5×1051 \leq n \leq 5 \times 10^5,0≤m≤5×1050 \leq m \leq 5 \times 10^5,2≤k≤5×1052 \leq k \leq 5 \times 10^5。

      时空限制:33s / 500500MiB。

    • 「CF2077D」Maximum Polygon

      CF2077D

      给出一个长度为 nn 的数组 aa,你需要找出字典序最大的子序列 ss,使得 ss 可以作为多边形的边长。

      当且仅当 ∣s∣≥3|s| \geq 3 且满足以下条件时,ss 可以作为多边形的边长

      2⋅max⁡(s1,…,s∣s∣)<s1+⋯+s∣s∣2 \cdot \max(s_1, \dots, s_{|s|}) < s_1 + \dots + s_{|s|}

      数据范围:3≤n≤2×1053 \leq n \leq 2 \times 10^5,1≤ai≤1091 \leq a_i \leq 10^9。

      时空限制:33s / 250250MiB。

    • 「CF1637F」Towers

      CF1637F

      给出一棵包含 nn 个点的树,编号 1∼n1 \sim n。第 ii 个点的高度为 hih_i。

      你可以在任意点放置任意数量的塔,对于每个塔,你可以选择放在哪个点,并且可以选择它的效率。设置一个效率为 ee 的塔需要花费 ee 金币,其中 e>0e > 0。

      如果存在一对分别位于 u,vu, v (u≠vu \neq v) 的信号塔,它们的效率分别为 eu,eve_u, e_v,且满足 min⁡(eu,ev)≥hx\min(e_u, e_v) \geq h_x,且点 xx 位于从 uu 到 vv 的路径上,则我们认为 xx 能够收到信号。

      请你求出使得所有顶点都接收到信号,所需的最小金币数。

      数据范围:2≤n≤2×1052 \leq n \leq 2 \times 10^5,1≤hi≤1091 \leq h_i \leq 10^9。

      时空限制:22s / 256256MiB。

    • 「CF1572B」Xor of 3

      CF1572B

      给出一个长度为 nn 的序列 aa,仅由 00 或 11 构成。

      你需要对序列进行至多 nn 次操作(或者说明这是不可能的),每次操作你可以选择一个下标 ii (1≤i≤n−21 \leq i \leq n - 2),然后将 ai,ai+1,ai+2a_i, a_{i + 1}, a_{i + 2} 均改成 ai⊕ai+1⊕ai+2a_i \oplus a_{i + 1} \oplus a_{i + 2}。

      数据范围:3≤n≤2×1053 \leq n \leq 2 \times 10^5,0≤ai≤10 \leq a_i \leq 1。

      时空限制:11s / 256256MiB。

    • 「CF1096E」The Top Scorer

      CF1096E

      有 pp 个人玩一个游戏,第 ii 个人的得分为 aia_i。

      已知 ∑ai=s\sum a_i = s 且 a1≥ra_1 \geq r,得分最高的人可以获胜,若多个人得分最高,则等概率随机其中一个人获胜。

      求第一个人获胜的概率,答案对 998244353998244353 取模。

      数据范围:1≤p≤1001 \leq p \leq 100,0≤r≤s≤50000 \leq r \leq s \leq 5000。

      时空限制:33s / 250250MiB。

    • 「CF1111E」Tree

      CF1111E

      给出一棵包含 nn 个点的树。

      有 QQ 次询问,每次询问给出三个整数 k,m,rk, m, r,随后给出 kk 个树上的节点 a1,a2,…,aka_1, a_2, \dots, a_k。假设树的根为 rr,我们需要将这 kk 个节点划分成至多 mm 组,并且:

      • 每个节点必须恰好属于一个组,每个组至少包含一个节点。
      • 在任意组内,不能存在两个不同的节点,使得其中一个点是另一个点的祖先。

      你需要求出分组的方案数,答案对 109+710^9 + 7 取模。

      数据范围:1≤n,Q≤1051 \leq n, Q \leq 10^5,1≤k,r≤n1 \leq k, r \leq n,1≤m≤min⁡(300,k)1 \leq m \leq \min(300, k),1≤∑k≤1051 \leq \sum k \leq 10^5。

      时空限制:1.51.5s / 256256MiB。

    • 「CF1097F」Alex and a TV Show

      CF1097F

      维护 nn 个初始为空的可重集。有 QQ 次操作,每次操作形如以下四种之一:

      • 1 x v:令集合 xx 等于 {v}\{v\}。
      • 2 x y z:令集合 xx 等于集合 yy 与 zz 的并。
      • 3 x y z:令集合 xx 等于集合 yy 与 zz 的积,A×B={gcd⁡(a,b)∣a∈A,b∈B}A \times B = \{\gcd(a, b) \mid a \in A, b \in B\}。
      • 4 x v:询问 vv 在集合 xx 中出现次数模 22 的结果。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤q≤1061 \leq q \leq 10^6,1≤v≤70001 \leq v \leq 7000。

      时空限制:33s / 250250MiB。

    • 「CF992E」Nastya and King-Shamans

      CF992E

      给出一个长度为 nn 的数组 aa,记 si=∑j=1iajs_i = \sum_{j = 1}^i a_j。

      有 QQ 次操作,每次操作给出两个整数 p,xp, x,表示将 apa_p 赋成 xx。每次操作后,你都需要判断是否存在一个位置 ii 满足 ai=si−1a_i = s_{i - 1}。若存在,输出任意一个满足条件的 ii。

      数据范围:1≤n,Q≤2×1051 \leq n, Q \leq 2\times 10^5,0≤ai≤1090 \leq a_i \leq 10^9,1≤p≤n1 \leq p \leq n,0≤x≤1090 \leq x \leq 10^9。

      时空限制:33s / 256256MiB。