A(2s/512M):定义一个序列是好的,当且仅当没有一个分界点使得前缀最大值等于后缀最小值。求长度为 n 值域为 [1,k] 的好的序列个数。n\le400,k\le10^8。
B(2s/512M):给定一棵深度为 m 的完全二叉树,点有点权。同时给定一个长为 n 的移动序列,一个人初始时位于根,根据移动序列进行移动:U/L/R 分别对应父亲/左儿子/右儿子,到达一个节点时令答案加上其点权,答案初始为 0。q 次询问每次将区间 [l,r] 中的 LR 取反,问此时的移动序列对应的答案,操作互相独立。n\le10^5,m\le18,q\le10^6。
0314
A(2s/1024M):有一排 n 棵树,每棵树上有一个果子,果子被摘下后 a 天后才能恢复。m 天每次把编号 [l,r] 的树上的果子摘下,没有果子就不摘,查询每天被摘下的果子数。n,m,a\le5\times10^5。
B(5s/1024M):给定一棵树,q 次询问给定 u,a,表示从 u 开始,每次只能走到距离当前点距离为 a 的点,求 u 到所有点的单源最短路或报告无法到达。有 T 组数据。n,a\le10^5,T,q\le10。
B(10s/1024M):在 k 维空间内有 n^k 个点,令点 (a_1,\dots,a_k) 的点权为 2^{\sum a_i\cdot \inf}。给定 m 个限制条件 x,y 表示某维为 x 的点和该维为 y 的点不能同时选择,求使得选点权值和最大的方案。n\le10^5,m\le5\times10^5,k\le10^{50000}。
0317
A(1s/1024M):给定 n,要求在 [1,2n] 中选出 n 个整数,使得其中不存在一个数是另一个数的倍数,且使得它们的和最小,求这个最小和。n\le5\times 10^5。
B(3s/256M):一个 n\times n 的格点正方形中有 m 个人在格点上,可能重合。有两种操作:标记一个格点,代价为 c;标记一个底边在正方形边上的等腰直角三角形,代价为被覆盖的格点的个数。求最小的代价使得所有有人的格点都被覆盖。n,m\le5\times10^4,c\le5。
C(3s/1024M):给定一个长为 n 的字符串 s,每个字符有颜色 c_i\in\{0,1,2\}。定义好的字符串满足:不包含颜色为 0 的字符且包含颜色为 1 的字符。q 次询问每次给出 l,r,k,表示对 s 的长度在 [l,r] 中的所有子串,求其中字典序第 k 小的好的字符串。n\le1.5\times10^5,q\le3\times10^5。
0319
A(2s/512M):给定一个 n 点 m 边的有向图,边有边权 w_i 和时间 t_i。再给定一个常数 k,设经过一条边的出发时刻为 t,则经过这条边的代价为 w_i+k|t|,消耗 t_i 的时间。可以选择任何整数(可负)作为从 1 点出发的时刻,求从 1 到 n 的最小代价。n\le5\times10^3,m\le10^4。
B(7s/1024M):定义一个序列的权值为其众数的出现次数。给定 n,m,求所有值域在 [1,n] 且长度为 m 的序列的权值和。n\le20,m\le5\times10^5。
C(3s/1024M):在一个长为 L 的环上有 n 群人和 m 栋房子。第 i 个人群位于 a_i 有 b_i 个人,第 j 栋房子位于 c_i 可以供给 d_i 个人住。一个人的代价为他到他房子的距离,要求每个人都有房子住,求最小代价。n,m,L\le10^5。
0323
A(1s/512M):对于一个长为 n 的,值域为 [1,n] 的正整数序列 a,有 m 个限制,分为 \forall i\in[l_i,r_i],a_i\le v_i 和 \forall i\in[l_i,r_i],a_i\ge v_i 两种。定义一个序列的权值为所有元素出现次数的平方的和,求符合条件的序列的权值最小值。n\le50,m\le100。
B(1.5s/512M):定义三元组 (a,b,c) 合法当且仅当 a^2+b^2=c^2。求当 1\le a\le n 时有多少合法三元组。n\le10^{10}。
C(3s/512M):给定一个 n 点 m 边无向图,其中 m\le n+40。由此构造一个新的有向图,每个点 u 向原图上距离它不超过 f_i 的点有连边,边权为 w_u+Tx_u,其中 T 为一个由你决定的整数参数。现在对于所有点,求 T\in[1,T_0] 时 1 到该点的最短路长度最小值。保证图连通。f_i\le n\le2\times10^5,x_u,w_u\le10^9,T_0\le100。
0324
A(1.5s/128M):给定一个长为 n 序列 a,有 m 次操作,操作分两种:在序列最前端加入一个数 x;询问如果进行 k 轮冒泡(从后往前扫,如果相邻两个位置前大于后就交换)会有多少次交换操作。操作二不会改变序列本身。n,m,a_i,x\le10^6。
B(6s/1024M):给定一棵有向树,点有点权,保证 1 为根。从一个点 i 可以跳到其祖先 j,代价为 a_i+\operatorname{dis}(i,j)^{1.5}。对所有点 i 求从 i 出发跳到点 1 的最小代价。n\le10^6。
A(3s/512M):对于值域为 [l,r] 且每个值恰好出现一次的序列 a,有 b_i\gets a_i-l+1,令 c_{b_i}=i,再令 d_i\gets c_i+l-1,则 d 称为 a 的逆。给定长为 n 排列 a,q 次操作分三类:单点查值;交换两个位置的值;将一个区间(保证符合上述 a 的条件)修改为它的逆。需要输出最终序列。n,q\le3\times10^5。
B(1s/1024M):有 n+2 个柱子排成一列,编号相邻的柱子紧紧相邻。柱子有高度 h_i,其中 h_0=h_{n+1}=\inf,且除了它们以外柱子高度各不相同。q 次询问如果在柱子 i 上倒 x 单位的水,最终会有多少根柱子上的积水深度大于 0。水往低处流,如果当前柱子比两边都高,则平均地往两边流,且为了方便水量为偶数。n,q\le2\times10^5,h_i,x_i\le10^9。
C(2.5s/1024M):定义 f(x,y) 为同时满足以下两个条件的大小为 x\times y 的 01 矩阵数量:把每行看作二进制数则单调不降;把每列看作二进制数则单调不降。给定 n,m,对所有 1\le x\le n,1\le y\le m 求 f(x,y),模数不保证为质数。n,m\le50。
B(5s/512M):给定字符集大小为 w 的字符串 s,求在 s 中出现次数至少为 2 的本质不同子序列 t 个数。q 次修改,每次形如令 s_x\gets c,求修改前及每次完成修改后的答案。|s|,q\le5\times10^4,w\le6。
C(4s/1024M):有 n 个人,每个人有属性 a_i。总共有 m 个金币,这些人按编号 1\sim n 逐个尝试对其分配给剩余的人。对于一次分配,如果第 i 个人的收益大于等于其拒绝此方案的收益加上 a_i,则其同意,反之拒绝。如果达到半数同意则结束,反之当前分配的人出局,由下一个人继续分配。每个人都知道属性值,会尽量不出局,尽量多分配给自己,尽量多分配给编号大的。求最终的分配方案,可以证明其唯一。n\le5\times10^4,m\le5\times10^6,1\le a_i\le64。
0401
A(2s/1024M):给定随机生成的排列 p,用 p 通过以下操作生成序列 a:在 a 的末尾添加上 p 的最小值,然后删除 p 的开头或末尾。求可能生成的 a 的个数。n\le2\times10^5。
C(2s/1024M):给定字符集大小为 3 的两个字符串 s,t,要求通过以下两种操作把 s 变为 t:将两个相邻相同字符修改为另外两个字符各一;将两个相邻不同字符都修改为另外那个字符。|s|\le5\times10^5。
0403
A(2s/1024M):给定 n 个长为 1 或 2 的序列。答案序列初始为空,每次可以进行三个操作之一:选择一个没有添加过的序列,拼接到答案序列前面;选择一个序列(没选过的)拼接到答案序列后面;令答案序列前后翻转。要求所有序列都需要被添加恰好一次且答案序列为回文的,构造方案。n,|\sum|\le5\times10^5。
B(1s/1024M):初始可重集 S 内有一个数 n。每次操作选择集合内一个数 x 取出,再任意选择一个数 y 将 y,x-y 加入集合。要求每次操作后集合内最大值小于最小值的两倍,求最多操作次数。全过程中只涉及整数。n\le10^9。
C(1s/1024M):有长为 n 的 01 序列 s,其中前 k 位已经给定。给定 m 求使得 s 不存在长为 m 的子串 t 满足其中 01 的个数相等的方案数。n,m,k\le114。
0406
A(0.5s/256M):有一个 n 点的环,初始时所有点为白色。每个时刻执行以下操作:把和黑点相邻的白点染成黑色,然后随机选择一个点染黑,可能选择到黑点。求把所用点染成黑色的期望耗时。n\le5000。
B(6s/1024M):对于一棵 n 个点的根为 1 的树,点有颜色,其中有 p_i 的概率为白色,否则为黑色。定义一次变换为,按深度从大到小把每个点的颜色变为它和它儿子的颜色的众数。q 次询问修改某个 p_i,求修改并进行一次变换后根的颜色为白色的概率。其中修改操作会继承,但是变换不会继承。n,q\le1.6\times10^5。
C(1.5s/1024M):给定若干字符串,保证对它们建出的字典树大小小于 K。定义 f(s) 表示 s 的回文子串的出现位置集合,由此定义 g(s,t) 表示 s 的所有子串 s_{l,r} 中满足 f(s_{l,r})=f(t) 的子串的个数。q 次询问每次给定 i,j 求 g(s_i,s_j) 的值。n,q,K\le5\times10^5。
0408
A(1s/512M):给定一个 n 点 m 边的 DAG,再给定起点 s_1,s_2 和终点 t_1,t_2,求两条 s_1\to t_1,s_2\to t_2 的点不相交路径使得边权和最小。n\le1000,m\le5000。
B(3s/256M):定义一个序列是好的当且仅当存在 i<j<k 使得 a_i<a_j<a_k。给定长为 n 的初始序列 a,q 次询问每次给出 l,r,k 表示对区间 [l,r] 向右循环移位 k 次,求每次操作后序列是否是好的。n,q\le10^5。
C(1s/256M):定义两个字符串是本质不同的,当且仅当不存在双射 \sum\to\sum 使得二者相等。给定长为 n 的串 s,求它的本质不同子串个数。n\le2\times10^5。
0410
A(2s/512M):给定长为 n 序列 a。定义一个序列是好的当且仅当其值域连续且值 x 出现了 x 次。求 a 的连续子序列中好的序列的个数。n\le10^6。
B(1s/512M):初始时有 n 个白点,对于一次操作,随机选择一个不全为黑的点对,将它们都染黑。求恰好 m 次操作后全为黑点的期望。对质数 p 取模。m\le n\le10^7。
C(2s/1024M):给定一个有 n 列的表格,每列有 h_i 个格子,且下端对齐。要求在表格中选择三个矩形,不包含表格外的格子,求最多能覆盖的格子数。n\le5\times10^5,V\le10^9。
0413
A(1s/1024M):给定一张 n 点 m 边的有向图,边有颜色,有重边自环,一个点的出边颜色均不同。初始时每个点上都有一个人,每次操作选择一个颜色,如果一个点有对应颜色的出边,则上面的所有人都会沿着边移动一次。要求构造长度不超过 n^3 的操作序列使得所有人恰好都在点 n 上。n\le100,m\le10^4。
B(3s/1024M):对于一个串 s,可以进行三种操作:删头;删尾;选择两个等长的前缀和后缀满足它们互为反串,将 s 改为这个前缀,并将得分加一。定义 f(s) 为在始终保证 s 非空的情况下能得到的最大得分。给定母串 t,q 次询问每次询问 f(t_{l,r}) 的值。|t|,q\le10^5
A(2s/1024M):给定 n 个不同的数 a_i,再给定 m 个数 b_i,求在 a 中选择 m 个数组成序列 c 使得 b_i|c_i 的方案数。n\le10^6,m\le17。
B(5s/1024M):给定长为 n 的序列 a,q 次询问每次给出 x,l,r,k,求进行 x 轮从前向后的顺序冒泡(把较大值往后放)后区间 [l,r] 内的前 k 小值和。n,q\le5\times10^5。
C(3s/1024M):给定一棵 n 个点的树,点有点权。q 次操作分为两种类型:给定 u,查询从 u 开始只经过点权为正的点能够到达的点数;给定 u,v,x,对链 (u,v) 的所有点(含端点)的点权加上 x。n\le2\times10^5。
0416
A(3s/1024M):给定 n 点 m 边的无向图,q 次操作每次加入一条边 u,v,问从 1 到 n 在当前状态下有几条边是必须经过的。n,m,q\le\times10^6。
B(1s/1024M):给定一棵 n 个点的树,以 1 为根。定义一个内向基环树森林的权值为 w^c,其中 w 为定值,c 为森林中基环树的个数,特别的,如果存在点 i 使得森林中包含了边 i\to fa_i,则其权值为 0。对所有点数个数为 n 的基环树森林求权值和。n\le5\times10^3,w>1。
C(1s/1024M):通过依次执行以下操作生成一个随机的值:随机生成一个长为 n 排列;对位置为 x_1,x_2\dots x_m 的 m 个数从小到大排序后依次填回这些位置;将序列随机划分成 k 段,其中每段的长度不小于 2;对划分出的每段求其逆序对数,再将它们求积得到结果。求所有的 k<n/2 求这个值的期望。n\le10^3。
0418
A(1s/512M):给定 n,m 和操作序列 p。初始时有序列 a_i=i,p 中的操作形如交换 a_x,a_y。等概率随机选择一个 p 的子区间 [L,R] 并依次执行操作,求最终序列 a 各个位置的值的期望。n,m\le5\times10^5。
B(5s/512M):给定长为 n 的序列 a,b。给定 k,要求选择至多 k 个位置令 a_i\gets a_i-b_i,使得序列 a 的最大子段和最小。n\le10^5,0\le|a_i|,b_i\le10^9。
C(3s/512M):给定一张 n 点 m 边的 DAG,其中点分两类,编号在 [1,k] 的点是 A 类点,其余为 B 类点。定义两个不重的等长点序列 a,b 是匹配的,当且仅当存在不相交路径组 a_i\to b_i。进一步定义 f(l,r) 表示最大的 |b| 满足存在 a_i\in[1,k],b_i\in[l,r] 且使得 a,b 匹配。要求对所有 0\le i\le k 求使得 f(l,r)=i 的 l,r 的对数。n\le10^5,m\le10^6,k\le50。
B(2s/512M):给定 n 个点的树,边有长度。q 次操作每次给定 u,k,a,b,表示对于 d_{u,v}\le k 的所有点 v,加上 f_1=a,f_2=b 的斐波那契数列的第 d_{u,v} 项。要求在线查单点的值。n,q\le2\times10^5。
C(2s/512M):给定长为 n 的序列 a,对于所有序列 b 满足 b_i|a_i,求把 b 划分成两个集合 S,T 使得任意 S_i|T_i 的方案数之和。n\le10^5,V\le2\times10^5。
0428
A(1s/512M):给定平面上 n 个矩形,m 次平移操作给定方向(上下左右)和距离 d。特别地,定义一次距离为 d 的平移操作如下:对当前矩形覆盖的范围进行矩形加一,然后该矩形向对应方向移动 1 距离,重复此操作 d 次。所有操作完成后对所有矩形当前位置进行矩形加一。q 次询问给定 x,y 查询点 (x,y) 的值。n,m,q\le2\times10^5。
B(1s/512M):给定 n+m 个物品及其重量 w_i。初始时所有物品都在集合内,每次随机取出一个物品,取出物品 i 的概率为 w_i/W,其中 W 为集合内所有物品重量之和。求取出前 n 个物品的期望次数。n,m\le500,w_{1\sim n}\le500。
C(3s/512M):给定环上的 n 个弧 l_i\to r_i,由此构造无向图满足每个点对应一个弧且有交点的弧间有连边。求这个无向图的最大团。n\le2\times10^3。
0430
A(2s/512M):给定一棵 n 个点的树,边有长度。定义一个点集 S 合法,当且仅当存在一个点 u 使得 \forall v\in S 有 \operatorname{dis}(u,v)\le k,其中 k 为定值。给定 m,k,求大小为 m 的合法点集个数。多组数据。n\le10^5,\sum n\le3\times10^5。
B(1s/256M):给定一棵 n 个点的以 1 为根的有根树,特别的,其深度不大于 100。定义一次操作为:选择一个点 u,删除 u 子树内所有叶子,并将 u 与父亲的边断开。求删光整棵树的最少操作次数以及使得操作次数最少的操作方案数。n\le2\times10^5。
C(4s/1024M):给定一个长为 n 的小写字符串 s。定义 s 的子串 t 的权值为 t 在 s 的本质不同子串中的字典序排名。给定 k 要求将 s 分割成 k 段,求这 k 段的最大权值和。k\le n\le2\times10^5。
0507
A(1s/1024M):给定长为 n 的序列 a。每次可以操作 a 中的一个数使其加一或减一,要求使得 a 最终值域连续且最小值为 1。求最少操作数。n,a_i\le10^6。
B(2s/1024M):给定 n,m,求有 nm 个点的有标号无向图中不包含 m 元环的图的个数。特别的,需要对 m 取模。n\le10^9,m\le5000。
A(2s/1024M):给定长为 n 的非负序列 a,其每个位置有颜色 c_i。定义一个区间是好的当且仅当它包含的每个位置颜色都不同。q 次操作,每次修改一个位置的颜色,或者给出 l,r 查询 a_{l,r} 的好的子区间中,包含的数的权值和最大是多少。n,q\le200000。
B(1s/1024M):有 n 个区分的球和一个无限长的序列。从序列的一段开始操作,有以下操作:把下一个位置染黑,取出 m 个球;把下一个位置染白,取出 m-1 个球;把序列剩下的部分截断,只保留染色部分,结束操作。必须不断操作直到选择操作三,如果球不够则不能取出。求结束操作后可能得到的状态数,两个状态不同当且仅当最终的序列或者剩下的球的集合不同。n\le10^{14},m\le2000。
C(1s/1024M):给定长为 n 的序列 a,b。一次操作 (l,r,v) 的作用是令 a_{l,r} 对 v 取 \min。定义一个操作序列合法,当且仅当依次执行恰好整个操作序列后 a=b。求长度不超过 m 的操作序列数。n\le100,m\le10^9。
B(1s/512M):给定长为 n 的 01 串,对于所有 l\in[1,n],求将原串分为 k 段并重排后的可能的最长不降子序列长度。n\le3\times10^5。
C(3s/512M):给定平面上 n 个点。定义一个大小为 k 的点集是好的,当且仅当它们能组成一个凸 k 边形。求所有好的点集形成的多边形的面积的平均值和方差。n\le400。
0511
A(5s/512M):给定一棵 n 个点的树,点有颜色 c_i 或者无色。总共有 m 种颜色,且保证每种颜色出现至少一次。定义一种把树划分成 m 个连通块的方式合法,当且仅当一个连通块内所有有色点的颜色都相同。求合法的划分方案数,保证存在合法方案。nm\le3\times10^5。
B(2s/512M):有一棵 2^n-1 个点的满二叉树,其中点 u 的左右儿子分别为 2u,2u+1,点有点权 a_u=u。初始时有两个机器人在点 x,y 上,可以进行任意次操作,每次操作它们可以同时向父亲/左子树/右子树走一步,或者交换它们所在节点的值。求所有能得到的最终序列中字典序第 k 小的序列,特别地,k 以二进制形式给出。n\le18,k\ge1。
C(1s/1024M):给定 n 个盒子,有范围 l_i,r_i 和容量 w_i,其中 l,r 不降。有 m 个小球,每个小球 i 要放到一个范围包含它的盒子里,可以一个盒子里的小球可以超出容量。要求使得超出容量的盒子个数最少,同时求满足此条件时,可能的没有超出容量的盒子集合的个数。n,m\le2\times10^5。
0513
A(3s/512M):纯水不想记了。
B(2s/512M):给定 n,m。定义长为 L 非负整数序列二元组 (a,b) 是好的,当且仅当 \sum a_ib_i=n,a_i=k_ia_{i-1},k_i\in[2,m] 且 a_1=1,b_L>0。求好的二元组个数。n\le3\times10^{10},m\le20。
C(2s/512M):给定长为 n 的环,并在环内加 m 条边,保证形成的图是平面图,边有边权。对于所有点对 (i,j),求它们的最短路长度之和。n,m\le2\times10^5。
0514
A(1s/1024M):有一个点从原点开始向正方向运动,有 n 个限制形如 (x_i,l_i,r_i) 表示要求这个点经过 x_i 的时刻在 [l_i,r_i] 中。点的加速度最多为定值 a,减速则可以瞬间完成,求到达 L 的最短时间(实数)。n\le5000,a\le1000,0\le x_i,l_i,r_i\le10^9。
B(1s/512M):给定 n 个字符串。初始有空序列 s,每次随机向 s 中加入一个小写字母,直到 n 个字符串都在 s 中出现。求 s 的期望长度。n\le15,\sum|S|\le10^5。
C(0.5s/1024M):交互题。有一棵隐藏的 n 个点树,要求还原它。具体的,给出一个点 u 和一个点集 S,交互库会返回 \sum dis(u,v),v\in S。要求询问次数不超过 A,所有点集 S 大小之和不超过 V。n\le1000,A=8500,V=3\times10^5。
0522
A(1s/512M):给定 n 点 m 边的图 G,无重边自环。求在 G 上添加若干条边使得它成为一棵基环树的方案数,边不区分。要求添加边之后依然无重边自环。n,m\le5000。
B(2s/512M):有初始全为空的 n 个可重集。q 次操作分为三类:给定 l,r,x,向编号 [l,r] 的集合中加入数 x;给定 l,r,对编号 [l,r] 的集合删除最后一个加入它的元素;查询集合 i 中的数的权值和。n,q\le3\times10^5。
C(4s/512M):给定一棵 n 个点的树。定义一种对它的染色方案是好的,当且仅当对于所有长度为 k 的链,都有恰好一个黑色点在链上。求好的染色方案数。n\le2\times10^6。
0524
A(1s/256M):定义一个可重集 S 的代价为 \sum S_i,其权值为 \sum S_i!。q 次询问每次给定 n,求所有代价不超过 n 的可重集 S 的权值的 \mathrm{mex}。结果对质数取模。q\le10^5,n\le10^{15}。
B(3s/512M):给定一张 n 个点的无向完全图,点有高度 h_i,边有边权。从点 u 一步走到点 v 的代价为 C|h_u-h_v|+w_{i,j},修改一个点 u 的高度为 x 的代价为 d_u|x-h_u|,其中 C,d_i 均给定。对于每对 (i,j),求修改若干个点的高度后从 i 走到 j 的最小代价。不同 (i,j) 互不影响。n\le500。
C(3s/2G):对于一个 01 串有以下操作:每次把串分割为若干极长相等连续段,把每个连续段删去一个字符后按原顺序拼接起来,如果一个连续段被删光了就直接把两侧接起来。定义一个 01 串的权值为把它删光的操作次数的 k 次方和。对所有长度为 n 的 01 串求权值和。结果对质数取模。n,k\le2.5\times10^7。
B(4s/1024M):对集合 A 定义 f(A) 表示:定义一次操作为把 a 中所有元素分为三个集合 S_0,S_1,T,其中 S_0,S_1 非空,对于 S_0 所有元素 A_i,如果它们的和不大于 S_1 中所有元素的和,则 A_i\gets A_i-1,对于 S_1 类似。则 f(A) 即为使得 A 中元素始终非零的最多操作数。给定长为 n 序列 a,q 次询问每次给定 l,r,求 \sum_l^r\sum_{i+1}^r f(a_{i,j})。n,q\le2\times10^5。
C(2s/1024M):给定 n 点 m 边的 DAG,点有点权 a_i,属性 t_i。定义一次行动为从某个 t_i=1 的点开始沿着边走到任意点结束。一次行动开始时,有空序列 c,走到点 u 时,将 c 加入序列集合 S_{u} 中(不可重),然后将 u 接在 c 最后。要求进行 k 次行动,使得 \sum a_i|S_i| 最大,其中 k 为常数。结果对质数取模。n\le10^6。
0601
A(1s/512M):给定一棵 n 个点的树。定义一局游戏为:初始点 a 为白色有一颗白子,点 b 为黑色有一颗黑子,其余所有点无色。白色先手,黑白双方轮流共进行 k 次操作,每次操作移动自己的棋子到一个相邻位置,然后把该位置染成对应颜色,最终令 x 表示白色点数减去黑色点数,白色方要使其最大化,黑色方反之。q 次询问给定 a,b,k,求最优策略的 x。n,q\le2\times 10^5。
B(3s/512M):有一个 n\times(m+1) 个点的无向图。给定 e 个三元组 (x_i,y_i,w_i),表示所有点 (x_i,j) 与点 (y_i,j+1) 有连边权为 w_i。对于所有 k\in[2,m+1] 求保留所有 b\le k 的点 (a,b) 时图的最小生成树。n,m\le3\times10^5,e\le10^6,w_i\le50。
C(2s/512M):有一个点数为 n! 的图,其中每个点对应一个长为 n 的排列。对于排列中第 i 个位置,它取值为 j 时的权值为 w_{i,j},保证 w 各不相同。点 p 向点 q 有连边当且仅当 q 可以由 p 交换两个相邻元素得到,且交换后这两个位置的权值都变大。给定 x,y,求从点 \{1,2,\dots,n\} 出发能否到达一个排列 p 满足 p_x=y,同时要求最大化 p_i=i 的位置。多组数据。T\le20,n\le200。
0604
A(1s/512M):给定 n 个区间 [l_i,r_i],要求对每个区间选择一个 x_i\in[l_i,r_i] 满足所有 x_i 各不相同或相邻。要求构造解,多组数据。\sum n\le3\times 10^5。
C(3s/512M):给定一张 n 点 m 边的无向图,每个点有属性 a_i,b_i。初始从点 1 出发,要求按以下规则经过所有点,允许重复经过:初始有值 x,到达一个点 u 时必须有 x\ge a_u,且不允许出现 u\to v\to u 的走法;到达一个点后 x\gets x+b_i。求使得存在一种合法走法的 x 的最小值。多组数据,特别地,为了方便有 a_1=b_1=0。\sum n\le10^6,\sum m\le2\times 10^6。