我的文章

    我的文章

    • CSP2021 游记

      希望能带来好运!

      2026.11.15 upd:优化了一下排版(但没有修改文章内容)。

    • splay 时间复杂度简要分析

    • 「日常训练」取数问题

      给出一个长度为 nn 的序列 aa,有 mm 次询问:

      1. 首先,在区间 [1,r−l+1][1, r - l + 1] 中随机选取一个数 KK。
      2. 然后,在区间 [l,r][l, r] 中随机选择一个大小为 KK 的下标集合,你需要求出选出的所有下标对应的 aia_i 都大于等于 xx 的概率。答案对 998244353998244353 取模。

      数据范围:1≤n,m≤1061 \leq n, m \leq 10^6,1≤ai,x≤1051 \leq a_i, x \leq 10^5。

      时空限制:11s / 512512MiB。

    • THUSC2021 简要题解

    • THUSC2021 游记

      希望能带来好运!

      2026.11.15 upd:优化了一下排版(但没有修改文章内容)。

    • 「LibreOJ Round #6」花团

      LOJ 534

      物品集合 SS 初始为空,按时间递增顺序依次给出 qq 次操作,操作如下:

      • 1 v w e:表示在 SS 中加入一个体积为 vv 价值为 ww 的物品,第 ee 次操作结束之后移除该物品。

      • 2 v:表示询问。你需要回答:

        1. 当前 SS 是否存在一个子集使得子集中物品体积和为 vv。
        2. 当前 SS 的所有物品体积和为 vv 的子集中,价值和最大是多少(空集的价值和为 00)。

      本题强制在线。

      数据范围:1≤q≤150001 \leq q \leq 15000,1≤vi≤150001 \leq v_i \leq 15000,0≤wi≤150000 \leq w_i \leq 15000。

      时空限制:33s / 256256MiB。

    • 「LOJ 6198」谢特

      LOJ 6198

      给出一个长度为 nn 仅包含小写字符的字符串 ss。

      定义后缀 ii 的权值为 wiw_i,定义两个不同后缀 i,j(i≠j)i, j(i \neq j) 的贡献为 LCP(i,j)+(wixor⁡wj)\mathrm{LCP}(i, j) + (w_i \operatorname{xor} w_j)。其中 LCP(i,j)\mathrm{LCP}(i, j) 表示后缀 ii 和后缀 jj 的最长公共前缀长度。

      你需要求出任意两个不同后缀 i,j(i≠j)i, j(i \neq j) 的贡献最大值。

      数据范围:1≤n≤1051 \leq n \leq 10^5,0≤wi<n0 \leq w_i < n。

      时空限制:11s / 512512MiB。

    • 「COCI 2015」Divljak

      BZOJ 3881

      有 nn 个字符串 S1,S2,⋯ ,SnS_1, S_2, \cdots, S_n。以及一个字典 TT,一开始字典 TT 为空。

      接下来有 qq 个操作,操作包含以下两种:

      • 1 P:向字典 TT 中插入一个字符串 PP。
      • 2 x:请你求出 SxS_x 是字典 TT 中多少个串的子串。

      数据范围:1≤n,q≤1051 \leq n, q \leq 10^5,字符集为小写字母集,字符串总长 ≤2×106\leq 2 \times 10^6。

      时空限制:44s / 500500MiB。

    • 「CF702F」T-Shirts

      CF702F

      有 nn 个 T 恤。每个 T 恤都有一个价格 cic_i 和品质 pip_i。

      有 mm 个人要购买 T 恤,第 ii 个人有 viv_i 元。

      每个人每次购买 T 恤都会在可以买得起的 T 恤中选一件品质最高的 T 恤,若有多个品质最高的 T 恤,则选择其中最便宜的那一件 T 恤。

      请你求出这 mm 个人各买了多少件 T 恤,注意每次询问都是独立的。

      数据范围:1≤n,m≤2×1051 \leq n, m \leq 2 \times 10^5,1≤ci,pi≤1091 \leq c_i, p_i \leq 10^9。

      时空限制:44s / 10241024MiB。

    • 积性函数的各种处理(等待重构!)