我的文章

    我的文章

    • 「2022 ICPC 沈阳站」G. Meet in the Middle

      gym104160 G

      给出两棵大小均为 nn 的树,节点编号均为 1∼n1 \sim n,边带正权。

      有 QQ 次询问,每次询问给出两个正整数 a,ba, b (1≤a,b≤n1 \leq a, b \leq n),你需要找到一个节点 xx,使得 xx 在第一棵树上到 aa 的距离加上 xx 在第二棵树上到 bb 的距离之和最大,你只需要求出这个最大值即可。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤q≤5×1051 \leq q \leq 5 \times 10^5,1≤w≤1091 \leq w \leq 10^9。

      时空限制:55s / 512512MiB。

    • 2025 ICPC EC-Final 游记

      天下英雄如过江之鲫。

    • 「Luogu P11039」TECHNOPOLIS 2085

      Luogu P11039

      给出一棵包含 nn 个点的有根树 TT,根节点为 11。给出一个大小为 mm 的关键点集合 SS。

      你需要求出有多少个不同的有根树 T′T',满足对于任意 x,y∈Sx, y \in S,均有 LCAT(x,y)=LCAT′(x,y)\mathrm{LCA}_T(x, y) = \mathrm{LCA}_{T'}(x, y)。答案对 998244353998244353 取模。

      数据范围:2≤m≤n≤1062 \leq m \leq n \leq 10^6。

      时空限制:11s / 512512MiB。

    • 「CF2190D」Prufer Vertex

      CF2190D

      对于一棵树 TT,定义 P(T)P(T) 表示对 TT 生成 Prufer 序列时,最后剩下的两个节点之中不是 nn 的那一个。

      给出一个包含 nn 个点 mm 条边的森林。对于每一个 vv (1≤v≤n1 \leq v \leq n),计算有多少种加边方式,使得原图变成一棵树 TT,且 P(T)=vP(T) = v。答案对 998244353998244353 取模。

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

      时空限制:22s / 256256MiB。

    • 「CF2178H」Create or Duplicate

      CF2178H

      有三种类型的礼物,价值分别为 a,b,ca, b, c。初始时,恰好拥有每一种礼物各一份。

      给出两个整数 mm 与 kk。你可以进行若干次操作,每次操作形如以下的两种:

      • 创造:选择一种礼物类型,并额外制作一份该类型的礼物。消耗 xx 点法力值,其中 x∈{a,b,c}x \in \{ a, b, c \} 为所选礼物类型的价值。
      • 复制:选择一种礼物类型,并复制该类型的所有礼物。消耗 kk 点法力值。

      你需要求出,使得礼物价值总和是 mm 的倍数时,所需的最小法力值。

      数据范围:1≤a<b<c<m≤5×1051 \leq a < b < c < m \leq 5 \times 10^5,1≤k≤5×1051 \leq k \leq 5 \times 10^5,1≤∑m,∑k≤5×1051 \leq \sum m, \sum k \leq 5 \times 10^5。

      时空限制:66s / 10241024MiB。

    • 「CF2178G」deCH OR Dations

      CF2178G

      圆环上有 2n2n 个等间距的点,按顺时针顺序标记为 1,2,…,2n1, 2, \dots, 2n。有 nn 条具有不同端点的弦,其中第 ii 条弦连接 ai,bia_i, b_i。现在按照顺序依次连接这 nn 条弦。

      每当连接完前 ℓ\ell 条弦以后,考虑这 ℓ\ell 条弦的任意非空子集 SS。设 SS 中元素的索引分别为 c1,c2,…,cmc_1, c_2, \dots, c_m,若对于所有的 1≤i<m1 \leq i < m,都满足弦 cic_i 与弦 ci+1c_{i + 1} 相交,则称 SS 为一条链。

      当且仅当,每一条弦在前 ℓ\ell 条弦的所有子集链中出现偶数次时,称这些弦是紧密连接的。

      对于 11 到 nn 的每一个 ℓ\ell,你都需要判断前 ℓ\ell 条弦是否紧密连接。

      数据范围:2≤n≤5×1052 \leq n \leq 5 \times 10^5,1≤ai<bi≤2n1 \leq a_i < b_i \leq 2n。

      时空限制:33s / 512512MiB。

    • 「4th Ucup Stage 10」A. Automatized Mineral Classification

      QOJ 16000

      This is an interactive problem.

      对于 1,…,n1, \dots, n,有一个隐藏的序列 aia_i,其中 aia_i 表示数字 ii 的颜色。

      有一个队列(初始为空),可以进行以下两种操作:

      • + id:将元素 id\mathrm{id} 加入队列末尾。
      • -:将队列开头的元素弹出。

      每次操作之后,你都会得知当前队列中共有多少种不同的元素。

      你的目标是,将所有元素按照颜色分组,依次给出每个组中的元素。

      数据范围:1≤n≤5001 \leq n \leq 500,操作至多进行 3500035000 次。交互器不自适应。

      时空限制:11s / 256256MiB。

    • 「4th Ucup Stage 10」F. Foxes

      QOJ 16005

      给出一个长度为 nn 的序列 a1,a2,…,ana_1, a_2, \dots, a_n。有一个指针 pp(初始时 p=1p = 1)。

      有 QQ 次操作,每次操作为以下三种之一:

      • <:令 p←p−1p \gets p - 1。
      • >:令 p←p+1p \gets p + 1。
      • ! v:令 ap←va_p \gets v,求出整个序列的严格最长上升子序列(LIS)。

      数据范围:2≤n≤2×1052 \leq n \leq 2\times 10^5,1≤Q≤5×1051 \leq Q \leq 5 \times 10^5,1≤ai,v≤1061\leq a_i, v \leq 10^6。

      时空限制:22s / 256256MiB。

    • 「CF2174C2」Beautiful Patterns (Hard Version)

      CF2174C2

      已知一个字符串 SS 的长度为 nn,字符集大小为 mm。现在均匀随机地生成该字符串 SS。

      记随机变量 XX 表示该字符串 SS 中回文子串的数量,求 E(X2)E(X^2)。答案对给定质数 pp 取模。

      数据范围:1≤n≤2×1051 \leq n \leq 2 \times 10^5,1≤m≤1071 \leq m \leq 10^7,m<p<109m < p < 10^9。

      时空限制:22s / 512512MiB。

    • 「CF2174D」Secret Message

      CF2174D

      给出一个包含 nn 个点 mm 条边的带权无向图。

      你需要找出 n−1n - 1 条边,使得这些边的权值之和最小,且不构成一棵树。

      数据范围:2≤n≤2×1052 \leq n \leq 2 \times 10^5,n−1≤m≤2×105n - 1 \leq m \leq 2 \times 10^5,1≤wi≤1091 \leq w_i \leq 10^9。

      时空限制:22s / 256256MiB。