文章分类:题解

    文章分类:题解

    • 「CF1572B」Xor of 3

      CF1572B

      给出一个长度为 nn 的序列 aa,仅由 00 或 11 构成。

      你需要对序列进行至多 nn 次操作(或者说明这是不可能的),每次操作你可以选择一个下标 ii (1≤i≤n−21 \leq i \leq n - 2),然后将 ai,ai+1,ai+2a_i, a_{i + 1}, a_{i + 2} 均改成 ai⊕ai+1⊕ai+2a_i \oplus a_{i + 1} \oplus a_{i + 2}。

      数据范围:3≤n≤2×1053 \leq n \leq 2 \times 10^5,0≤ai≤10 \leq a_i \leq 1。

      时空限制:11s / 256256MiB。

    • 「CF1096E」The Top Scorer

      CF1096E

      有 pp 个人玩一个游戏,第 ii 个人的得分为 aia_i。

      已知 ∑ai=s\sum a_i = s 且 a1≥ra_1 \geq r,得分最高的人可以获胜,若多个人得分最高,则等概率随机其中一个人获胜。

      求第一个人获胜的概率,答案对 998244353998244353 取模。

      数据范围:1≤p≤1001 \leq p \leq 100,0≤r≤s≤50000 \leq r \leq s \leq 5000。

      时空限制:33s / 250250MiB。

    • 「CF1111E」Tree

      CF1111E

      给出一棵包含 nn 个点的树。

      有 QQ 次询问,每次询问给出三个整数 k,m,rk, m, r,随后给出 kk 个树上的节点 a1,a2,…,aka_1, a_2, \dots, a_k。假设树的根为 rr,我们需要将这 kk 个节点划分成至多 mm 组,并且:

      • 每个节点必须恰好属于一个组,每个组至少包含一个节点。
      • 在任意组内,不能存在两个不同的节点,使得其中一个点是另一个点的祖先。

      你需要求出分组的方案数,答案对 109+710^9 + 7 取模。

      数据范围:1≤n,Q≤1051 \leq n, Q \leq 10^5,1≤k,r≤n1 \leq k, r \leq n,1≤m≤min⁡(300,k)1 \leq m \leq \min(300, k),1≤∑k≤1051 \leq \sum k \leq 10^5。

      时空限制:1.51.5s / 256256MiB。

    • 「CF1097F」Alex and a TV Show

      CF1097F

      维护 nn 个初始为空的可重集。有 QQ 次操作,每次操作形如以下四种之一:

      • 1 x v:令集合 xx 等于 {v}\{v\}。
      • 2 x y z:令集合 xx 等于集合 yy 与 zz 的并。
      • 3 x y z:令集合 xx 等于集合 yy 与 zz 的积,A×B={gcd⁡(a,b)∣a∈A,b∈B}A \times B = \{\gcd(a, b) \mid a \in A, b \in B\}。
      • 4 x v:询问 vv 在集合 xx 中出现次数模 22 的结果。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤q≤1061 \leq q \leq 10^6,1≤v≤70001 \leq v \leq 7000。

      时空限制:33s / 250250MiB。

    • 「CF992E」Nastya and King-Shamans

      CF992E

      给出一个长度为 nn 的数组 aa,记 si=∑j=1iajs_i = \sum_{j = 1}^i a_j。

      有 QQ 次操作,每次操作给出两个整数 p,xp, x,表示将 apa_p 赋成 xx。每次操作后,你都需要判断是否存在一个位置 ii 满足 ai=si−1a_i = s_{i - 1}。若存在,输出任意一个满足条件的 ii。

      数据范围:1≤n,Q≤2×1051 \leq n, Q \leq 2\times 10^5,0≤ai≤1090 \leq a_i \leq 10^9,1≤p≤n1 \leq p \leq n,0≤x≤1090 \leq x \leq 10^9。

      时空限制:33s / 256256MiB。

    • 「CF1174E」Ehab and the Expected GCD Problem

      CF1174E

      对于一个长度为 nn 的排列 pp,定义 f(p)f(p) 表示:令 gig_i 表示 p1,…,pip_1, \dots, p_i 的最大公约数,则 f(p)f(p) 表示 g1,g2,…,gng_1, g_2, \dots, g_n 中不同元素的个数。

      令 fmax⁡(n)f_{\max}(n) 表示所有关于 nn 的排列 pp 中的 f(p)f(p) 最大值,求有多少个关于 nn 的排列 pp 满足 f(p)=fmax⁡(n)f(p) = f_{\max}(n)。答案对 109+710^9 + 7 取模。

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

      时空限制:22s / 256256MiB。

    • 「2022 上海市赛」F. Forest of Magic

      gym103931 F

      给出一棵包含 nn 个点的树,编号 1∼n1 \sim n。根节点为 11。

      有 QQ 次操作,每次操作形如以下的三种之一:

      • 1 u:设本次操作之前共有 n′n' 个点,则新加入一个编号为 n′+1n' + 1 的点,并且新点有一条连向 uu 的无向边。
      • 2 u v c k:对于在从 uu 到 vv 的简单路径上的所有点,都会增加 kk 个类型 cc 的物品。
      • 3 u c:查询点 uu 的子树内,有多少个物品的类型 ≤c\leq c。

      本题强制在线。

      数据范围:1≤n≤3×1041 \leq n \leq 3 \times 10^4,0≤Q≤1050 \leq Q \leq 10^5,节点总数不超过 5×1045 \times 10^4,1≤k≤1071 \leq k \leq 10^7,1≤c≤1091 \leq c \leq 10^9。

      时空限制:88s / 10241024MiB。

    • 「CF825G」Tree Queries

      CF825G

      给出一棵包含 nn 个点的树,初始时所有点均为白色。

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

      • 1 x:将点 xx 改成黑色。
      • 2 x:对于点 xx,找出编号最小的点 yy,使得 yy 位于 xx 到某个黑色顶点的简单路径上。

      本题强制在线。保证第一次操作的类型为操作 1。

      数据范围:3≤n,Q≤1063 \leq n, Q \leq 10^6。

      时空限制:33s / 256256MiB。

    • 「CF704B」Ant Man

      CF704B

      有 nn 个元素,第 ii 个元素有五个参数 xi,ai,bi,ci,dix_i, a_i, b_i, c_i, d_i。

      你需要求出一个 1∼n1 \sim n 的排列 pp,满足 p1=s,pn=ep_1 = s, p_n = e,同时最小化这个排列的权值。一个排列的权值定义为 ∑i=1n−1f(pi,pi+1)\sum_{i = 1}^{n - 1} f(p_i, p_{i + 1}),其中

      • 若 i>ji > j,则 f(i,j)=xi−xj+ci+bjf(i, j) = x_i - x_j + c_i + b_j。
      • 若 i<ji < j,则 f(i,j)=xj−xi+di+ajf(i, j) = x_j - x_i + d_i + a_j。

      你只需要求出排列的最小权值即可。

      数据范围:1≤n≤5×1031 \leq n \leq 5 \times 10^3,s≠es \neq e,1≤x1<x2<⋯<xn≤1091 \leq x_1 < x_2 < \dots < x_n \leq 10^9,1≤ai,bi,ci,di≤1091 \leq a_i, b_i, c_i, d_i \leq 10^9。

      时空限制:44s / 250250MiB。

    • 「CF594D」REQ

      CF594D

      给出一个长度为 nn 的数组 aa。

      有 QQ 次查询,每次查询给出两个正整数 l,rl, r (1≤l≤r≤n1 \leq l \leq r \leq n),你需要求出

      φ(∏i=lrai)\varphi \left( \prod_{i = l}^{r} a_i \right)

      答案对 109+710^9 + 7 取模。

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

      时空限制:33s / 256256MiB。