我的文章

    我的文章

    • 博客落地啦✨置顶

    • 2026 CCPC 长春站游记

      希望能带来好运!

    • 「2026 杭电多校 4」1005. TREE

      https://acm.hdu.edu.cn/contest/problem?cid=1232&pid=1005

      给出一个长度为 nn 的排列 a1,…,ana_1, \dots, a_n。

      有 QQ 次询问,每次询问给出两个整数 l,rl, r (1≤l≤r≤n1 \leq l \leq r \leq n),求区间 al,…,ara_l, \dots, a_r 的小根笛卡尔树的树高,定义树根的深度为 11。

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

      时空限制:22s / 512512MiB。

    • 「2026 杭电多校 5」1011. 树形广播

      https://acm.hdu.edu.cn/contest/problem?cid=1233&pid=1011

      给出一棵包含 nn 个节点的树。每个节点都有一个显示值(初始均为 00)。定义 dist(u,v)dist(u, v) 表示节点 u,vu, v 之间的边数。

      有 QQ 次操作,每次操作形如以下的两种:

      • 1 v l r k w0 w1 … wkw_0 \ w_1 \ \dots \ w_k:表示从节点 vv 发起广播,对于所有满足 l≤dist(u,v)≤rl \leq dist(u, v) \leq r 的节点 uu,记 d=dist(u,v)d = dist(u, v),将节点 uu 的显示值修改为
      (∑i=0kwidi) mod 998244353\left(\sum_{i = 0}^k w_id^i\right) \bmod 998244353
      • 2 x:查询节点 xx 当前的显示值。

      数据范围:1≤n,Q≤1051 \leq n, Q \leq 10^5,0≤k≤100 \leq k \leq 10,0≤wi<9982443530 \leq w_i < 998244353。

      时空限制:1010s / 512512MiB。

    • 「2026 杭电多校 3」1007. rains

      https://acm.hdu.edu.cn/contest/problem?cid=1231&pid=1007

      有一排相连的 nn 块石头,第 ii 块石头的高度为 hih_i。每当下雨时的水位高度 HH 大于 hih_i 时,第 ii 块石头就会被淹没。所有露出的石头会形成若干个连续段。

      有 QQ 次询问,每次询问给出 l,rl, r,你需要求出:只考虑区间 [l,r][l, r] 内的石头,当使得露出的石头形成至少 kk 个连续段时,下雨的水位 HH 最高是多少。

      数据范围:1≤n,Q,k≤1061 \leq n, Q, k \leq 10^6,1≤hi≤1061 \leq h_i \leq 10^6,1≤l≤r≤n1 \leq l \leq r \leq n。

      时空限制:55s / 512512MiB。

    • 「CF2199H」Sum of MEX

      CF2199H

      给出一个数组 a1,…,ana_1, \dots, a_n,其中 −1≤ai≤n-1 \leq a_i \leq n。

      对于每个 ii (1≤i≤n1 \leq i \leq n),求出 f([a1,…,ai])f([a_1, \dots, a_i]),其中 f(s)f(s) 对于数组 ss 定义如下:

      • 对于所有将 ss 中的 −1-1 替换成 [0,n][0, n] 之间整数的不同方案,f(s)f(s) 为这些方案对应数组的 MEX 之和。

      保证 −1-1 的数量不超过 300300。

      数据范围:1≤n≤2×1051 \leq n \leq 2\times 10^5,−1≤ai≤n-1 \leq a_i \leq n。

      时空限制:55s / 512512MiB。

    • 「CF2234E」Vlad, Misha and Two Arrays

      CF2234E

      对于一个长度为 nn 的排列 pp,记 aia_i 表示有多少个区间 [l,r][l, r] (1≤l≤r≤n1 \leq l \leq r \leq n) 满足 pl,…,prp_l, \dots, p_r 中的最小值为 pip_i。

      现给出 a1,…,ana_1, \dots, a_n,求出有多少个可能的排列 pp。

      数据范围:1≤n≤5×1051 \leq n \leq 5\times 10^5,1≤ai≤10121 \leq a_i \leq 10^{12}。

      时空限制:22s / 256256MiB。

    • 「2026 牛客多校 3」B. 再买一瓶

      https://ac.nowcoder.com/acm/contest/133878/B

      一瓶饮料售价 11 元。

      每次小明喝完一瓶饮料,他会以 p=abp = \frac{a}{b} 的概率获奖。如果获奖,他将得到 cc 元;否则,他什么也得不到。

      他得到的钱可以用来购买更多饮料。每瓶饮料的获奖事件相互独立。小明一开始有 nn 元。求他恰好喝完 mm 瓶饮料后花光所有钱的概率。答案对 998244353998244353 取模。

      数据范围:1≤T≤2×1051 \leq T \leq 2\times 10^5,1≤n,m,c≤2×1061 \leq n, m, c \leq 2 \times 10^6,0≤a<b≤9982443530 \leq a < b \leq 998244353。

      时空限制:22s / 10241024MiB。

    • 「2026 牛客多校 1」L. 子串的子串

      https://ac.nowcoder.com/acm/contest/133876/L

      给出一个长度为 nn 的字符串 SS 和一个长度为 nn 的序列 a1,…,ana_1, \dots, a_n。有 QQ 次询问。每次询问给出一个字符串 tt:

      如果一个区间 [l,r][l, r] (1≤l≤r≤n1 \leq l \leq r \leq n) 满足 tt 是 S[l:r]S[l : r] 的子串,那么称这个区间为好区间。

      求所有好区间的区间和的最大值,以及所有好区间的区间和之和(对 998244353998244353 取模)。保证至少存在一个好区间。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤q≤3×1051 \leq q \leq 3\times 10^5,−109≤ai≤109-10^9 \leq a_i\leq 10^9,1≤∑∣t∣≤3×1051 \leq \sum |t| \leq 3\times 10^5。

      时空限制:55s / 10241024MiB。

    • 「CF1930F」Maximize the Difference

      CF1930F

      对于一个长度为 mm 的非负数组 bb,定义 f(b)f(b) 等于

      max⁡x≥0{max⁡i=1m(bi∣⁡x)−min⁡i=1m(bi∣⁡x)}\max_{x\geq 0}\left\{ \max_{i = 1}^m(b_i \operatorname{|} x) - \min_{i = 1}^m(b_i \operatorname{|} x) \right\}

      给出值域上限 nn 以及操作次数 QQ,初始时数组 aa 为空,有 QQ 次强制在线的操作:每次操作在数组 aa 的末尾加入一个数 vv (0≤v<n0 \leq v < n),你需要求出此时的 f(a)f(a)。

      数据范围:1≤n≤2221 \leq n \leq 2^{22},1≤Q≤1061 \leq Q \leq 10^6。

      时空限制:33s / 256256MiB。