文章分类:题解

    文章分类:题解

    • 「CF2233E2」Permutation Transmission (Difficult Version)

      CF2233E2

      对于一个长度为 nn 的排列 pp,记 k=⌈log⁡2(n+1)⌉k = \lceil \log_2(n + 1) \rceil。

      系统原本会生成 kk 个长度为 nn 的 0101 串,对于第 jj (0≤j<k0 \leq j < k) 个二进制位,0101 串的第 ii 个字符表示 pip_i 的第 jj 个二进制位的值。

      现在,这 kk 个 0101 串被打乱,因此不知道每个 0101 串对应哪个二进制位。

      给定打乱后的 kk 个 0101 串,求有多少个不同的关于 nn 的排列 pp,使得至少存在一种 0101 串与二进制位的对应关系,能够还原出 pp。

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

      时空限制:22s / 512512MiB。

    • 「ARC217A」Min of Sum of XOR

      ARC217A

      给出一个正整数 nn。

      构造一个关于 nn 的排列,使得 ∑i=1n⨁j=1ipj\sum_{i = 1}^n \bigoplus_{j = 1}^i p_j 最小。

      其中 ⨁j=1ipj\bigoplus_{j = 1}^i p_j 表示 p1,…,pip_1, \dots, p_i 的异或和。

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

      时空限制:22s / 10241024MiB。

    • 「CF2222G」Statistics on Tree

      CF2222G

      给出一个大小为 nn 的树,定义点对 (u,v)(u, v) (1≤u≤v≤n1 \leq u \leq v \leq n) 的价值为:删除从 uu 到 vv 的路径上的所有边之后,最大连通块的大小。

      对于每个 ii (1≤i≤n1 \leq i \leq n),求出价值等于 ii 的点对 (u,v)(u, v) 的数量。

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

      时空限制:22s / 512512MiB。

    • 「CF2222F」Building Tree

      CF2222F

      给出一个包含 nn 个点 mm 条边的无向图,边带权。

      对于任意路径,设其边权集合为 SS,则该路径的长度为 mex(S)\mathrm{mex}(S)。记 dis(u,v)\mathrm{dis}(u, v) 表示所有从 uu 到 vv 的路径中的最小路径长度。

      现在有 qq 个关键点 c1,…,cqc_1, \dots, c_q,连接 cu,cvc_u, c_v 的代价是 dis(cu,cv)\mathrm{dis}(c_u, c_v),求让这 qq 个关键点连通的最小代价总和。

      数据范围:1≤n,m≤3×1051 \leq n, m \leq 3 \times 10^5,1≤q≤n1 \leq q \leq n,0≤w≤m0 \leq w \leq m。

      时空限制:2.52.5s / 512512MiB。

    • 「2022 ICPC 沈阳站」G. Meet in the Middle

      gym104160 G

      给出两棵大小均为 nn 的树,节点编号均为 1∼n1 \sim n,边带正权。

      有 QQ 次询问,每次询问给出两个正整数 a,ba, b (1≤a,b≤n1 \leq a, b \leq n),你需要找到一个节点 xx,使得 xx 在第一棵树上到 aa 的距离加上 xx 在第二棵树上到 bb 的距离之和最大,你只需要求出这个最大值即可。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤q≤5×1051 \leq q \leq 5 \times 10^5,1≤w≤1091 \leq w \leq 10^9。

      时空限制:55s / 512512MiB。

    • 「Luogu P11039」TECHNOPOLIS 2085

      Luogu P11039

      给出一棵包含 nn 个点的有根树 TT,根节点为 11。给出一个大小为 mm 的关键点集合 SS。

      你需要求出有多少个不同的有根树 T′T',满足对于任意 x,y∈Sx, y \in S,均有 LCAT(x,y)=LCAT′(x,y)\mathrm{LCA}_T(x, y) = \mathrm{LCA}_{T'}(x, y)。答案对 998244353998244353 取模。

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

      时空限制:11s / 512512MiB。

    • 「CF2190D」Prufer Vertex

      CF2190D

      对于一棵树 TT,定义 P(T)P(T) 表示对 TT 生成 Prufer 序列时,最后剩下的两个节点之中不是 nn 的那一个。

      给出一个包含 nn 个点 mm 条边的森林。对于每一个 vv (1≤v≤n1 \leq v \leq n),计算有多少种加边方式,使得原图变成一棵树 TT,且 P(T)=vP(T) = v。答案对 998244353998244353 取模。

      数据范围:2≤n≤2×1052 \leq n \leq 2 \times 10^5,0≤m≤n−10 \leq m \leq n - 1。

      时空限制:22s / 256256MiB。

    • 「CF2178H」Create or Duplicate

      CF2178H

      有三种类型的礼物,价值分别为 a,b,ca, b, c。初始时,恰好拥有每一种礼物各一份。

      给出两个整数 mm 与 kk。你可以进行若干次操作,每次操作形如以下的两种:

      • 创造:选择一种礼物类型,并额外制作一份该类型的礼物。消耗 xx 点法力值,其中 x∈{a,b,c}x \in \{ a, b, c \} 为所选礼物类型的价值。
      • 复制:选择一种礼物类型,并复制该类型的所有礼物。消耗 kk 点法力值。

      你需要求出,使得礼物价值总和是 mm 的倍数时,所需的最小法力值。

      数据范围:1≤a<b<c<m≤5×1051 \leq a < b < c < m \leq 5 \times 10^5,1≤k≤5×1051 \leq k \leq 5 \times 10^5,1≤∑m,∑k≤5×1051 \leq \sum m, \sum k \leq 5 \times 10^5。

      时空限制:66s / 10241024MiB。

    • 「CF2178G」deCH OR Dations

      CF2178G

      圆环上有 2n2n 个等间距的点,按顺时针顺序标记为 1,2,…,2n1, 2, \dots, 2n。有 nn 条具有不同端点的弦,其中第 ii 条弦连接 ai,bia_i, b_i。现在按照顺序依次连接这 nn 条弦。

      每当连接完前 ℓ\ell 条弦以后,考虑这 ℓ\ell 条弦的任意非空子集 SS。设 SS 中元素的索引分别为 c1,c2,…,cmc_1, c_2, \dots, c_m,若对于所有的 1≤i<m1 \leq i < m,都满足弦 cic_i 与弦 ci+1c_{i + 1} 相交,则称 SS 为一条链。

      当且仅当,每一条弦在前 ℓ\ell 条弦的所有子集链中出现偶数次时,称这些弦是紧密连接的。

      对于 11 到 nn 的每一个 ℓ\ell,你都需要判断前 ℓ\ell 条弦是否紧密连接。

      数据范围:2≤n≤5×1052 \leq n \leq 5 \times 10^5,1≤ai<bi≤2n1 \leq a_i < b_i \leq 2n。

      时空限制:33s / 512512MiB。

    • 「4th Ucup Stage 10」A. Automatized Mineral Classification

      QOJ 16000

      This is an interactive problem.

      对于 1,…,n1, \dots, n,有一个隐藏的序列 aia_i,其中 aia_i 表示数字 ii 的颜色。

      有一个队列(初始为空),可以进行以下两种操作:

      • + id:将元素 id\mathrm{id} 加入队列末尾。
      • -:将队列开头的元素弹出。

      每次操作之后,你都会得知当前队列中共有多少种不同的元素。

      你的目标是,将所有元素按照颜色分组,依次给出每个组中的元素。

      数据范围:1≤n≤5001 \leq n \leq 500,操作至多进行 3500035000 次。交互器不自适应。

      时空限制:11s / 256256MiB。