文章分类:题解

    文章分类:题解

    • 「2025 ICPC 网络赛 2」L. Xor Mirror

      QOJ 14325

      给出一个长度为 nn 的序列 a0,a1,…,an−1a_0, a_1, \dots, a_{n - 1},保证 nn 是 22 的若干次幂。

      有 QQ 次操作,每次操作都形如以下操作中的一种:

      • 1 l r k:对于所有 i∈[l,r)i \in [l, r),令 bi=ai⊕kb_i = a_{i \oplus k}。然后对于所有 i∈[l,r)i \in [l, r),令 ai=bia_i = b_i。
      • 2 l r:求 ∑i=lr−1ai\sum_{i = l}^{r - 1} a_i 的值。

      其中 ⊕\oplus 表示按位异或。

      数据范围:1≤n≤2181 \leq n \leq 2^{18},保证 nn 是 22 的若干次幂,1≤Q≤2×1051 \leq Q \leq 2 \times 10^5,1≤ai≤10485761 \leq a_i \leq 1048576,0≤l<r≤n0 \leq l < r \leq n,0≤k<n0 \leq k < n。

      时空限制:22s / 6464MiB。

    • 「2025 ICPC 网络赛 2」K. The Only Heart

      QOJ 14324

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

      你可以进行若干次操作,每次你可以删除这棵树的一个叶子(即保证剩下部分仍然是连通的)。

      你需要求出有多少种删除叶子的方案,使得剩下部分的重心唯一(这里的重心定义与平常相同,即最大子树最小的节点)。

      答案对 998244353998244353 取模,两个方案不同当且仅当删除叶子节点构成的集合不同。

      数据范围:1≤n≤3×1031 \leq n \leq 3 \times 10^3。

      时空限制:33s / 10241024MiB。

    • 「2025 ICPC 网络赛 2」I. DAG Query

      QOJ 14322

      This is an interactive problem.

      给出一个 nn 个点 mm 条边的有向无环图(DAG)。你会得到该 DAG 的结构,但不会知道 DAG 中每条边的边权。

      在任意一对顶点 ss 与 tt 之间可能存在多条路径,我们将一条路径的权值定义为该路径上所有边权的乘积。记 f(s,t,c)f(s, t, c) 表示从 ss 到 tt 的所有不同路径,在所有边权都乘以 cc 情况下的权值之和,对 998244353998244353 取模。

      你可以进行至多 999999 次询问,每次询问你需要给出参数 s,t,cs, t, c,交互器会返回 f(s,t,c)f(s, t, c) 的值。

      最后,交互器会给出一个参数 kk,你需要确定 f(1,n,k)f(1, n, k) 的值。

      数据范围:1≤n≤1031 \leq n \leq 10^3,1≤m≤5×1031 \leq m \leq 5 \times 10^3。

      时空限制:33s / 10241024MiB。

    • 「2025 杭电多校 1」1001. 博弈

      HDU 7979

      Alice 和 Bob 正在玩取石子游戏。

      有 nn 个房间,第 ii 个房间中有 kik_i (ki≥1k_i \geq 1) 堆石子。Alice 和 Bob 轮流操作,Alice 先手。

      每次操作时,玩家必须在当前房间中,选择任意一个非空的堆,然后在该堆中取出任意一个石子。只有在当前房间中将所有石子取完,Alice 和 Bob 才可以到下一个房间继续进行游戏。若某位玩家无法进行操作(即到了最后一个房间并且房间为空),则该玩家输掉游戏。

      在游戏开始前,Alice 可以决定房间的访问顺序,访问顺序可以用一个排列 pp 描述,表示依次经过房间 p1,p2,…,pnp_1, p_2, \dots, p_n,只有房间 pip_i 没有石子的情况下,才可以去房间 pi+1p_{i + 1}。

      假设 Alice 和 Bob 进行的都是最优决策,Alice 想知道他有多少种排列 pp 可以获胜。答案对 109+710^9 + 7 取模。

      数据范围:1≤n≤1061 \leq n \leq 10^6,1≤∑ki≤1061 \leq \sum k_i \leq 10^6,石子数量 ∈[1,109]\in [1, 10^9]。

      时空限制:11s / 512512MiB。

    • 「2025 杭电多校 1」1002. 夜世界

      HDU 7980

      有 nn 座金矿排成一行,每座金矿有一个属性 aia_i,表示该金矿一天产出的金币数量。每座金矿都潜伏着一只有属性 bib_i 的哥布林,代表该哥布林的贪婪值。

      每天夜晚都会发生以下的事件:你将从第 11 座金矿走到第 nn 座金矿,初始金币为 00,每走过一座金矿 ii,以下两件事情依次发生:

      • 你将获得 aia_i 金币。
      • 哥布林向你索要 bib_i 金币,若你没有 bib_i 金币则需要将所有金币交给哥布林。

      你需要在这里 mm 天,每天都会进行以下操作中的一种:

      • 1 x y:令 ax=ya_x = y,修改是持久的。
      • 2 x y:令 bx=yb_x = y,修改是持久的。
      • 3 x:版本回到第 xx 天。
      • 4 k p1 p2 ... pk:有 kk 个位于金矿 p1,p2,…,pkp_1, p_2, \dots, p_k 的哥布林向你索要金币的方式变为“若你目前拥有 ss 金币,它们将要向你索要 ⌈s2⌉\left\lceil \frac{s}{2} \right\rceil 金币”,变化是临时的。你需要求出当晚要交给哥布林多少金币。

      数据范围:1≤n,m≤2×1051\leq n, m \leq 2\times 10^5,0≤k≤2×1050 \leq k \leq 2\times 10^5,0≤ai,bi≤1090 \leq a_i, b_i \leq 10^9。

      时空限制:33s / 256256MiB。

    • 「2024 ICPC 昆明站」I. Items

      QOJ 9870

      有 nn 种物品,其中第 ii 种物品的重量为 wiw_i,每一种物品的数量都是无限的。

      是否能恰好选 nn 个物品,使得所选物品的重量之和为 mm。

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

      时空限制:88s / 10241024MiB。

    • 「2025 ICPC 网络赛 1」F. Robot

      QOJ 14306

      This is an interactive problem.

      一个机器人在一个无限大的二维平面的第一象限内移动。最初机器人位于坐标 (sx,sy)(s_x, s_y)。最初所有单元格都是白色的。

      游戏包含了若干次操作,最多 T=1000T = 1000 次操作。每次操作都会按照以下顺序发生事件:

      1. 你的操作:你可以选择一个整点坐标 (x,y)(x, y),其中 1≤x,y≤T1 \leq x, y \leq T,你会将该单元格标记成黑色。
      2. 机器人的操作:机器人可以移动到与其所在单元格八连通的单元格(由交互器决策)。
      3. 结果检查:机器人移动到下一个单元格之后,系统会检查该单元格是否是黑色。
      • 如果是黑色,机器人爆炸。
      • 如果是白色,则进行下一次操作。

      你的目标是在 TT 次操作之内使机器人爆炸。

      数据范围:1≤sx,sy≤201 \leq s_x, s_y \leq 20。

      时空限制:22s / 10241024MiB。

    • 「CF2131H」Sea, You & copriMe

      CF2131H

      给出一个长度为 nn 的数组 aa,其中数组中的元素均为 1∼m1 \sim m 中的正整数。

      你需要找到四个不同的索引 p,q,r,sp, q, r, s,使得 gcd⁡(ap,aq)=1\gcd(a_p, a_q) = 1 且 gcd⁡(ar,as)=1\gcd(a_r, a_s) = 1。

      数据范围:4≤n≤2×1054 \leq n \leq 2 \times 10^5,1≤m≤1061 \leq m \leq 10^6,1≤ai≤m1 \leq a_i \leq m。

      时空限制:33s / 256256MiB。

    • 「2025 ICPC 网络赛 1」J. Moving on the Plane

      QOJ 14310

      有 nn 个点,第 ii 个点的初始坐标为整点 (xi,yi)(x_i, y_i)。

      接下来有 mm 轮移动,每一轮中的所有 nn 个点 (x,y)(x, y) 都需要移动到 (x+1,y),(x−1,y),(x,y+1),(x,y−1)(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) 四个位置的其中一个。

      你需要求出有多少种不同的移动点的方式,使得最终 nn 个点两两曼哈顿距离小于等于 kk。其中 (x1,y1),(x2,y2)(x_1, y_1), (x_2, y_2) 的曼哈顿距离为 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|。

      数据范围:1≤n≤501 \leq n \leq 50,1≤m≤1051 \leq m \leq 10^5,0≤k≤100 \leq k \leq 10,0≤∣xi∣,∣yi∣≤1050 \leq |x_i|, |y_i| \leq 10^5。

      时空限制:22s / 10241024MiB。

    • 「Ynoi2011」成都七中

      Luogu P5311

      给出一棵包含 nn 个点的树,每个节点有一种颜色 cic_i。

      有 mm 次查询,每次查询给出三个参数 l,r,xl, r, x,表示询问只保留编号在 [l,r][l, r] 范围内的点时,xx 所在连通块的颜色种类数。

      数据范围:1≤n,m≤1051 \leq n, m \leq 10^5,1≤ci≤n1 \leq c_i \leq n,1≤l≤x≤r≤n1 \leq l \leq x \leq r \leq n。

      时空限制:11s / 250250MiB。