广东省队集训留档

A(2s/1024M)：给定 $n$ 点 $m$ 边的无向连通图，边有边权 $a_i,b_i$ 。对于所有 $k\in[0,m]$ ，求恰有 $k$ 条边取边权 $a_i$ ，其余边取边权 $b_i$ 时最小生成树边权和的最大值。 $n\le9,m\le100$ 。
B(1.5s/1024M)：初始时有变量 $x=1$ 。有 $n$ 个操作，分为两类：令 $x\gets a_i$ ；令 $x\gets x\times a_i\bmod p$ ，其中 $a_i$ 为操作的参数， $p$ 为常数。可以随意安排操作顺序，求所有操作都恰好执行一次后 $x$ 能够取得的值的个数。 $n,p\le10^6$ 。

A(4s/1024M)：有 $n$ 个怪物，有属性 $a_i,b_i$ 。有 $m$ 个道具，有属性 $c_i,d_i$ 。你可以花费 $c_i$ 代价使用道具 $i$ ，然后它消失。有常数 $k$ ，如果你使用了 $k$ 个或更多 $d_i$ 大于 $b_j$ 的道具，则怪物 $j$ 消失，否则你需要额外花费 $a_j$ 的代价。有 $q$ 次修改，每次修改一个怪物或者一个道具的属性值，对每次修改后求最小总代价。 $n,m,q\le2.5\times10^5,k\le10^4$ 。特别地，有 $qk\le5\times10^5$ 。
B(1s/512M)：给定集合 $B$ ，对于 $S=\{1,2,\dots,x\}$ ，求 $S$ 有多少个子集的线性基为 $B$ 。其中 $x$ 为定值。特别的， $B$ 中元素以及 $x$ 的值域为 $[0,2^m-1]$ ，其中 $m$ 为定值。 $n,m\le2000$ 。
> Day3 上课，神秘省集甚至把题目放到 vj 上了不公开，非常恶劣。

A(1s/512M)：给定两棵 $n$ 个点的树。定义一个整数集合 $S\subseteq[1,n]$ 是好的，当且仅当 $\forall u,v\in S$ ，若 $u$ 在 $T_1$ 中是 $v$ 的祖先，则 $u$ 在 $T_2$ 中也是 $v$ 的祖先。求好的集合的最大大小。 $n\le40$ 。
B(2s/512M)：给定长为 $n$ 的序列 $a$ 。定义一个整数集合 $S\subseteq[1,n]$ 的权值为：满足 $[l,r]$ 中的整数都在 $S$ 内的二元组 $(l,r)$ 的数量乘 $k$ 减去 $\sum a_i,i\in S$ 。 $q$ 次询问，每次临时修改 $a_x=y$ ，求能取得的最大权值。 $n,m\le3\times10^5$ 。

A(4s/512M)：给定一张 $n$ 个点的图，初始图上没有边，点有颜色 $0/1$ 或者无色。在这张图上随机连 $m$ 条边，允许重边自环，然后两个人开始玩游戏：定义一张图的权值为 $0\to1$ 的边的数量减去 $1\to0$ 的边的数量。两个人轮流染色，先手希望最终图的权值最大，后手则相反。点/边之间均有区别，对所有可能的 $n^{2m}$ 个图求它们对应的最终图的权值之和。 $n,m\le50$ 。

A(1s/1024M)：给定长为 $n$ 的序列 $a$ 。定义一次操作 $[l,r]$ 为：从 $l$ 开始每三位分别执行 $+1,-1,0$ 直到位置 $r$ 。求使得 $a$ 变为全 $0$ 序列的最少操作数。多组数据。 $T\le30,n\le3\times10^4,|a_i|\le10^{10}$ 。
B(4s/1024M)：给定 $n$ 个点的 DAG，其中对于点 $2\sim n$ ，恰好各有两条出边，分别连向 $a,b$ 。对于点 $i$ ，保证 $a,b$ 在 $[1,i-1]$ 中随机生成。 $n-1$ 次询问，第 $i$ 次给定 $x$ ，求点 $i+1$ 到点 $x$ 的最短路。 $n\le2\times10^6$ 。
C(1.5s/1024M)：给定一棵 $n$ 个点的数，点有点权 $a_i$ 。定义一次操作为选取一条边，使得对应的父亲节点点权 $-1$ ，孩子节点点权 $+1$ ，要求父亲节点操作后点权非负。求任意次操作后可能得到的序列 $a$ 的个数。 $n\le8\times10^3,0\le a_i\le10^9$ 。

A(2s/512M)：给定一棵 $n$ 个点的树，点有点权。定义一条边的不平衡度为将它删去后形成的两棵子树的点权和之差的绝对值。定义一棵树的不平衡度为其上的关键边的不平衡度的最大值。 $q$ 次询问，每次选择树上的 $k$ 条边作为关键边，并给定 $l,r$ ，求进行至少 $l$ 次至多 $r$ 次单点 $+1$ 后树的不平衡度的最小值。询问独立。 $n,\sum k\le3\times10^5$ 。
B(2s/512M)：给定一棵 $n$ 个点的树，点有点权。定义一条链的权值为其最长上升子序列长度，一棵树的权值为它上面所有链的权值的最大值，一个森林的权值为其中所有树的权值的最大值。求删掉一个点能够得到的森林的最大权值。 $n\le10^5$ 。

A(1s/512M)：给定一张 $n\times m$ 的棋盘，每个位置可能是空地或者障碍，空地上可能有一颗棋子。对于一颗棋子，每次操作可以将它向上/左/右移动一格，要求同一颗棋子不能重复到达同一个格子且不能到达障碍，不同棋子可以重叠。两个人轮流操作，先无法操作者判负。 $n,m\le1000$ 。
B(2s/512M)：给定 $2n\times2m$ 的表格，标号从 $0$ 开始。把每 $2\times2$ 的格子看作一组，把相邻组黑白染色。其中第 $i$ 行 $j$ 列的数为 $2n(i-1)+j$ 。有五种操作：对所有 $i$ 交换 $2i,2i+1$ 列(或行)；对所有 $i$ 交换 $2i+1,2i+2$ 列(或行)；对黑色的组顺时针旋转 $90$ 度，对白色的组逆时针旋转 $90$ 度。给定 $n,m$ 以及操作序列，求最终的序列。 $nm\le10^6$ 。

文章操作