文章分类:题解

    文章分类:题解

    • 「CF1622F」Quadratic Set

      CF1622F

      给出一个集合 A={1,2,…,n}={x∈Z∣1≤x≤n}A = \{1, 2, \dots, n\} = \{x \in \mathbb{Z} \mid 1 \leq x \leq n\}。

      你需要寻找一个非空集合 A′⊆AA' \subseteq A,使得 ∏k∈A′k!\prod_{k \in A'} k! 是一个完全平方数。 在此基础上,你需要最大化 ∣A′∣|A'|,并以任意顺序给出集合 A′A' 中的所有数。

      数据范围:1≤n≤1061 \leq n \leq 10^6。

      时空限制:44s / 256256MiB。

    • 「CF700E」Cool Slogans

      CF700E

      给出一个长度为 nn 的字符串 str\mathrm{str}。你需要构造一个尽量字符串序列 s1,s2,⋯ ,sks_1, s_2, \cdots, s_k,满足:

      • 对于任意 1≤i≤n1 \leq i \leq n,sis_i 为 str\mathrm{str} 的子串。
      • 对于任意 1<i≤n1 < i \leq n,si−1s_{i - 1} 在 sis_i 中至少出现了两次(可重叠)。

      只需求出 kk 的最大值即可。

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

      时空限制:44s / 500500MiB。

    • 「CSP-S 2019」括号树plus

      CLYZ 学长学姐们留下来的题,感谢+膜拜。

      给出一棵有 nn 个节点的数,根节点为 11。每个节点上恰有一个括号,要么为左括号 ( 要么为右括号 )。

      记 sis_i 表示从根到 ii 的路径上,依次将各个节点的括号拼接而成的字符串。设 kik_i 表示 sis_i 中本质不同的合法括号子串的数量。求

      (1×k1)xor(2×k2)xor⋯xor(n×kn).(1 \times k_1) \mathbin{\mathrm{xor}} (2 \times k_2) \mathbin{\mathrm{xor}} \dots \mathbin{\mathrm{xor}} (n \times k_n).

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

      时空限制:55s / 512512MiB。

    • NOIP2021 题解

    • CSP2021-S 题解

    • 「日常训练」取数问题

      给出一个长度为 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 简要题解

    • 「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。