我的文章

    我的文章

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

    • 「CF1313D」Happy New Year

      CF1313D

      有 mm 个孩子,编号为 1∼m1 \sim m。

      圣诞老人会 nn 种魔法,第 ii 种魔法可以给所有编号在区间 [Li,Ri][L_i, R_i] 内的孩子各发一个糖果。每种魔法最多使用一次,并且已知如果所有魔法都使用,每个孩子至多收到 kk 个糖果。

      你可以控制这 nn 种魔法的使用情况,请你求出最多有多少个孩子收到奇数个糖果。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤m≤1091 \leq m \leq 10^9,1≤k≤81 \leq k \leq 8。

      时空限制:22s / 500500MiB。

    • 「CF875F」Royal Questions

      CF875F

      有 nn 个王子与 mm 个公主。每个公主有喜欢的两个王子,编号分别为 ai,bia_i, b_i,但一个王子只能娶一个公主,一个公主也只能嫁给一个王子。每个公主有一个嫁妆价值 wiw_i。

      求国王能够得到的嫁妆最大值(允许有王子或公主无伴侣)。

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

      时空限制:1.51.5s / 500500MiB。

    • 「CF1559D2」Mocha and Diana (Hard Version)

      CF1559D2

      给出两个森林,节点数均为 nn,节点编号均为 1∼n1 \sim n。

      你可以进行加边操作。每次操作,你需要选择两个不同的正整数 x,yx, y,然后在两个森林中都加上 (x,y)(x, y)。你需要保证两个森林在加边后仍然是森林。

      求最多可以加几条边。并给出加边方案。

      数据范围:1≤n≤1051 \leq n \leq 10^5,0≤m1,m2<n0 \leq m_1, m_2 < n。

      时空限制:22s / 250250MiB。

    • C.L. 大一下周常训练报告

      本文曾经为 C.L. 大一下周常训练报告,后来觉得自己难以保持每天每道题都写总结的节奏,遂搁置。

    • 「CF2077C」Binary Subsequence Value Sum

      CF2077C

      对于一个二进制字符串 vv,定义其分数为

      max⁡0≤i≤∣v∣{F(v,1,i)×F(v,i+1,∣v∣)}\max_{0 \leq i \leq |v|} \{ F(v, 1, i) \times F(v, i + 1, |v|) \}

      其中 F(v,l,r)=r−l+1−2×zero(v,l,r)F(v, l, r) = r - l + 1 - 2 \times \mathrm{zero}(v, l, r),这里 zero(v,l,r)\mathrm{zero}(v, l, r) 表示子串 v[l:r]v[l : r] 中 0 的数量。

      给出一个长度为 nn 的二进制字符串 ss。

      有 QQ 次操作,每次操作都会给出一个 ii (1≤i≤n1 \leq i \leq n),你需要将 sis_i 取反。每次操作结束后,你都需要求出 ss 的所有非空子序列的得分之和。答案对 998244353998244353 取模。

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

      时空限制:33s / 256256MiB。