信友队模拟赛留档

---

题目评分

• T0：
• T1：0309A,0314B,0314C,0317C,0319B,0323C,0324A,0324C,0327C,0330A,0330B,0401B,0403C,0408C,0410B,0413A,0415A,0415B,0415C,0416B,0416C,0418C,0421B，0425B,0428B,0430A,0430B,0430C,0507A,0508A,0508B,0509A,0509B,0509C,0511B,0511C,
• T2：0309B,0314A,0316A,0317A,0317B,0319A,0319C,0323C,0324B,0326A,0326B,0403A,0406C,0413C,0418B,0421A,0421C,0428A,0428C,0507B,0511A,0513C,0514A,0514B,0514C,
• T3：0323B,0330C,0401A,0403B,0408A,0408B,0410C,0410A,0416A,0425C
• T114514：
• T?：0316B,0401C,0406A,0406B,0413B,0507C,0508C,0513B

---

0309

• 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$。
• C(2s/1024M)：同 CF1773G，但 $m$ 范围加强到 $21$。

0316

• A(4s/512M)：给定一棵树，要求一个访问序列 $s$，使得每个点的出现次数为 $a_i$，且走过的边总长度最长。$m$ 次询问，每次断开一条边，连上一条边，询问互不相关。$n\le3\times10^5,m\le1.5\times10^6$。
• 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$。
• C(1s/512M)：定义 $f(x)$ 表示 $x$ 二进制表示下 1 的个数的奇偶性，再定义 $s(l,r)$ 表示 $f(l)+f(l+1)+\dots+f(r)$，其中加法表字符串拼接。给定 01 串 $T$，其中 $T=s(l_1,r_1)+\dots+s(l_n,r_n)$，$l,r,n$ 给定。$m$ 次询问每次给出 $S_i$，求 $S_i$ 在 $T$ 中的出现次数（可重叠）。$n,m,\sum|S|\le10^5,l_i\le r_i\le10^9$。

0326

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

0330

• A(1s/512M)：对于一棵边权为 $0/1$ 的树 $T$，定义其直径为满足 $\operatorname{dis}(u,v)$ 最大的无序点对 $(u,v)$，据此定义 $f(T)$ 为其直径的数量。给定树形态，对 $2^{n-1}$ 种赋权方案，求 $f(T)$ 之和。$n\le2000$。
• 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$。
• B(2s/1024M)：一个 $n\times m$方格图，每个格子可以有黑白两种颜色。$k$ 次操作，每次在左上角格子中放入一个小球，小球根据以下规律运动直到走出边界：如果格子为黑色则往下一格，格子为白色则往右一格。每次移动后格子颜色取反。有部分边界格子是特殊的，小球从此格子离开边界会有 $1$ 的得分。$q$ 次询问，每次给出 $l_i,r_i$ 求最终得分在 $[l_i,r_i]$ 内的初始染色方案数。$n,m\le10,q\le10^5,l_i,r_i,k\le10^{18}$。
• 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$
• C(2s/1024M)：有 $n$ 盏灯，灯有持续时间 $t_i$，点亮一盏灯后的 $t_i$ 个时刻内它是亮着的，否则它是熄灭的。每个时刻恰可以点亮一盏灯。给定两个灯的集合 $S_1,S_2$，求最小的 $t_2$ 满足存在 $t_1<t_2$ 和一个合法操作序列，使得 $t_1$ 时 $S_1$ 中的灯都亮者，$t_2$ 时 $S_2$ 中的灯都亮着。特别地，要求在这两个时刻不能操作灯。$n\le8000$。

0415

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

0421

• A(1.5s/64M)：给定序列 $a$，$q$ 次询问给定 $l,r,k$，对 $i\in[l,r]$ 求 $a_i/k$ 下取整能得到的不同的非零值的个数。注意到不同寻常的时空限制。$n,q\le2\times10^5$。
• B(3s/1024M)：有初始为空的字符串 $s$。$q$ 次操作分三类：在 $s$ 末尾加上一个串；翻转 $s$；给定串 $t$ 求 $t$ 在 $s$ 中的出现次数。$|s|\le5\times10^5,\sum|t|\le10^7$。
• C(1s/1024M)：有 $n\times m$ 的表格，其中有若干个关键格子。每行有颜色 $a_i$，每列有颜色 $b_j$，颜色只有黑白两种。$a,b$ 中部分位置已经确定，部分位置还未确定。要求构造方案，确定 $a,b$ 的值，并去掉若干行/列的关键格子，使得对于所有剩下的关键格子 $(i,j)$ 满足 $a_i\neq b_j$，同时去掉的行/列总数最小。输出最小值及方案。$n,m\le10^3$。

0425

• 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$。
• C(3s/2048M)：给定排列 $p_0$。定义一个排列 $p$ 的生成图 $G(p)$ 为：对于每个数 $i$，向排列中向前的第一个比该数大的数连边，又向第一个比该数小的数连边，向后同理。定义图的染色数为对点染色使得任意边两侧点颜色不同的最小颜色数。$q$ 次询问每次给定 $l,r$，求 $q_{l,r}$ 的所有子区间形成的生成图的最大染色数，以及求对应的子区间个数。$n,q\le3\times10^5$。

0508

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

0509

• A(1s/512M)：给出长为 $n$ 的序列 $a$，每个位置有颜色 $c_i$ 和权值 $w_i$。定义一次操作为：选择一个区间 $[l,r]$，满足区间内所有数均为正且颜色相同，把区间内所有数减一，代价为 $w_l+w_r$。$q$ 次操作分为三类：单点修改 $a_i,w_i$；区间赋颜色；查询使得区间 $[l,r]$ 中所有数都为零的最小代价。$n,q\le2\times10^5$。
• 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$。

0525 图灵杯

• A(1s/512M)：给定一棵 $n$ 个点的树，点有属性 $a_i,b_i$。要求对所有 $a_i=-1$ 的点赋值 $a_i\in[0,n]$，满足对于所有 $b_i\neq-1$ 的点 $i$，其子树内所有点的 $\mathrm{mex}=b_i$，求合法的赋值方案数。$n\le5\times10^3$。
• B(7s/512M)：定义一个整数二元组集合 $S$ 是好的，当且仅当 $\forall (a,b),(c,d)\in S$，若 $[a,b]\cap[c,d]$ 非空则 $(a,d),(b,d)\in S$。给定 $n,c$，定义集合 $S$ 的权值为 $c^S$，对于所有 $S\subseteq\{(i,j)|1\le i\le j\le n\}$ 求它们的权值和。对质数取模。$n\le700$。
• > 暂时不多记了，CD 全场无人通过，不知道我能会到哪一步。

0528

• A(1s/512M)：给定长为 $2n$ 的序列 $a$ 和括号串 $s$，其中 $s$ 偶数位的括号被替换为 ?。定义一个合法括号串的权值为：对于每一对匹配的括号 $s_l,s_r$，对权值加上 $\sum_{l+1}^r a_i$ 的贡献。对于一个偶数位为 ? 的括号串定义其权值为：如果不存在合法替换方案则为 $0$，否则取所有合法替换方案的权值的最小值。对于所有 $1\le l\le r\le n$，求 $s_{2l-1,2r}$ 的权值和。对质数取模。$n\le10^6$。
• 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$。
• B(1s/512M)：给定 $n$ 个带问号的 01 串。定义一次游戏为：初始有得分 $x=0$，每次随机取出一个串的串首，如果为 $0$ 则 $x\gets x-1$，反之则 $x\gets x+1$，如果得分为 $-1$ 则失败。重复此流程直到所有串都为空且没失败则生离。特别地，$x=0$ 时如果有 $1$ 则一定会取出 $1$。求有多少个替换 $?$ 的方式使得无论如何都能保证胜利。对大质数取模。$\sum|s_i|\le10^4$。
• 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$。