文章分类:题解

    文章分类:题解

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

    • 「CF2173F」Isla's Memory Thresholds

      CF2173F

      给出一个长度为 nn 的非递增序列 a1,a2,…,ana_1, a_2, \dots, a_n(满足 a1≥a2≥⋯≥ana_1 \geq a_2 \geq \dots \geq a_n)。

      有 QQ 次查询,每次查询给出 l,r,xl, r, x,你会依次遍历 al,al+1,…,ara_l, a_{l + 1}, \dots, a_r,你有一个计数器 ss(初始 s=0s = 0),每次将当前遍历到的数累加进 ss,若任意时刻 s≥xs \geq x,你就会将 ss 清零。你需要求出遍历结束时,将 ss 清零的次数以及最后 ss 的值。

      数据范围:1≤n,Q≤1.5×1051 \leq n, Q \leq 1.5 \times 10^5,1≤ai,x≤1091 \leq a_i, x \leq 10^9,1≤l≤r≤n1 \leq l \leq r \leq n。

      时空限制:66s / 10241024MiB。

    • 「2025 ICPC 武汉站」A. Planting Trees

      QOJ 14719

      有 TT 组数据,每组数据给出 f,x,g,y,n,mf, x, g, y, n, m,你需要求出

      ∑i=0n−1[(fi+x) mod m<(gi+y) mod m]\sum_{i = 0}^{n - 1} \left[ (fi + x) \bmod m < (gi + y) \bmod m \right]

      数据范围:1≤T≤1041 \leq T \leq 10^4,1≤f,x,g,y,n,m≤1061 \leq f, x, g, y, n, m \leq 10^6。

      时空限制:11s / 10241024MiB。

    • 「代码源挑战赛 R33F」最大边权

      daimayuan 203

      给出一棵包含 nn 个节点的树,边带权。

      有 QQ 次询问,每次询问给出 kk 个区间 [l1,r1],…,[lk,rk][l_1, r_1], \dots, [l_k, r_k],定义点集 VV 表示至少被一个区间包含的点构成的集合。

      考虑 VV 的所有无序点对 (u,v)(u, v),将树上 u,vu, v 之间的简单路径上所有边进行染色。你需要求出所有被染色边的最大边权。

      数据范围:1≤n,Q≤2×1051 \leq n, Q\leq 2 \times 10^5,1≤∑k≤2×1051 \leq \sum k \leq 2 \times 10^5,1≤li≤ri≤n1 \leq l_i \leq r_i \leq n。

      时空限制:22s / 512512MiB。

    • 「CF2159E」Super-Short-Polynomial-San

      CF2159E

      已知三个整数 a,b,ca, b, c。定义 Fn(x)=(ax2+bx+c)nF_n(x) = (ax^2 + bx + c)^n。

      有 QQ 次询问,每次询问给出两个参数 n,kn, k,你需要求出 ∑i=0k[xi]Fn(x)\sum_{i = 0}^k[x^i]F_n(x)。答案对 109+710^9 + 7 取模。

      本题强制在线。

      数据范围:1≤a,b,c≤109+61 \leq a, b, c \leq 10^9 + 6,1≤Q≤3×1051 \leq Q \leq 3\times 10^5,0≤n≤3×1050 \leq n \leq 3\times 10^5,0≤k≤2n0 \leq k \leq 2n。

      时空限制:77s / 10241024MiB。

    • 「CF2159C」Twin Polynomials

      CF2159C

      对于一个多项式 f(x)=a0+a1x+a2x2+⋯+anxnf(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n,当 aia_i (0≤i≤n0 \leq i \leq n) 均为非负整数且 an≠0a_n \neq 0 时,多项式 f(x)f(x) 被称为 nn 阶有效多项式。

      对于一个 nn 阶有效多项式 f(x)=a0+a1x+a2x2+⋯+anxnf(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n,其孪生多项式 g(x)g(x) 定义为

      g(x)=∑i=0ni⋅xaig(x) = \sum_{i = 0}^n i \cdot x^{a_i}

      当且仅当 f(x)=g(x)f(x) = g(x) 时,f(x)f(x) 被称为酷多项式。

      给出一个不完整的 nn 阶有效多项式 f(x)=a0+a1x+a2x2+⋯+anxnf(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n,aia_i 的一部分已经确定,剩余部分暂未确定。保证 a0a_0 与 ana_n 未确定。

      请求出确定了未确定的部分以后,能得到多少个 nn 阶有效酷多项式。答案对 109+710^9 + 7 取模。

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

      时空限制:22s / 256256MiB。

    • 「CF2153E」Zero Trailing Factorial

      CF2153E

      设 vp(x!)v_p(x!) 表示 x!x! 可以分解出多少个 pp 的乘积。

      勒让德定理:

      • 当 pp 为质数时
      vp(x!)=∑j=1⌊log⁡kx⌋⌊xpj⌋v_p(x!) = \sum_{j = 1}^{\lfloor \log_k x \rfloor} \left\lfloor \frac{x}{p^j} \right\rfloor
      • 当 pp 为合数时,记 p=∑i=1mpicip = \sum_{i = 1}^m p_i^{c_i}
      vp(x!)=min⁡i=1m⌊vpi(x!)ci⌋v_p(x!) = \min_{i = 1}^m \left\lfloor \frac{v_{p_i}(x!)}{c_i} \right\rfloor

      设

      wk(a,b)={min⁡(vk(a!),vk(b!))if vk(a!)≠vk(b!);10100otherwise.w_k(a, b) = \begin{cases} \min(v_k(a!), v_k(b!)) & \text{if }v_k(a!) \neq v_k(b!) \text{;}\\ 10^{100} & \text{otherwise.} \end{cases}

      设

      fm(a,b)=min⁡2≤k≤mwk(a,b)f_m(a, b) = \min_{2 \leq k \leq m} w_k(a, b)

      给出两个整数 n,mn, m,你需要计算 ∑1≤x<nfm(x,n)\sum\limits_{1 \leq x < n}f_m(x, n)。

      数据范围:2≤n≤m≤1072 \leq n \leq m \leq 10^7。可以证明给定条件下答案严格小于 1010010^{100}。

      时空限制:33s / 512512MiB。

    • 「CF2153F」Odd Queries on Odd Array

      CF2153F

      给出一个长度为 nn 的序列 a1,a2,…,ana_1, a_2, \dots, a_n,满足不存在 1≤i<j<k<l≤n1 \leq i < j < k < l \leq n 使得 ai≠aja_i \neq a_j,ai=aka_i = a_k,aj=ala_j = a_l。

      有 QQ 次询问,每次询问给出两个整数 l,rl, r (1≤l≤r≤n1 \leq l \leq r \leq n),你需要求出区间 [l,r][l, r] 中所有出现了奇数次的数之和。

      本题强制在线。

      数据范围:1≤n,Q≤5×1051 \leq n, Q \leq 5\times 10^5,1≤ai≤n1 \leq a_i \leq n,1≤l≤r≤n1 \leq l \leq r \leq n。

      时空限制:1010s / 10241024MiB。