2021省队集训-模拟
2021省队集训-模拟
Day1
A. 数排列
给定 $n$, 和排列 $x_m$, 求有多少个排列 $a_n$ 满足 $x$ 为 $a$ 字典序最小的长 $m$ 的子序列.
膜 $998244353$
$m\le n\le 2. 5\times 10^5$
开门降智
考虑 $x$ 为字典序最小的子序列的条件.
容易发现, 如果某个位置存在 $x_i\le x_{i-1}$, 那么可以选择 $x_{1\ldots i-2}, x_{i\ldots m}$ 以及再往后一个, 这种情况不行当且仅当剩下的位置不够多, 也就是 $x_i$ 的位置后面恰好全是 $x_i$ 往后的部分.
于是我们只需要解决对于一个递增的 $x$ 的问题去凑组合数, 考虑把 $x$ 放一排, 从小到大插空即可.
复杂度线性.
B. 取石子游戏
Alice 和 Bob 在玩取石子游戏, 游戏规则是这样的: 游戏开始时在他们面前有若干堆石子, Alice 先手进行游戏, 两人轮流操作, 玩家每轮操作时可以选取一堆石子, 并从中至少取走 $1$ 颗石子, 可以把这堆石子取空, 如果某轮中某位玩家无法进行任何操作(即所有石子均被取完了), 则她或他输掉游戏, 另一方赢得游戏.
Alice 和 Bob 两人都十分聪明, 并且他们知道彼此均会以最优策略进行操作, 所以他们可以在游戏开始前就预知游戏的赢家是谁.
Charlie 为 Alice 和 Bob 准备了一项任务: 在 Alice 和 Bob 面前有 $n$ 堆石子, 编号为 $1. . . n$, 初始时第 $i$ 堆中有 $a_i$ 个石子.
Charlie 会依次执行 $q$ 次操作, 每次操作是以下两类之一:
- 格式为
1 l r x: 对于编号在 $[l, r]$ 之间的石子堆 $i$, 如果不足 $x$ 颗石子, 把它补充到 $x$ 颗, 否则不做变化.- 格式为
2 l r x: 询问 Alice 和 Bob 如果此时只保留编号在 $[l, r]$ 之间的石子堆, 再加入一堆新的含有 $x$ 个石子的石子堆, 然后进行游戏, 那么 Alice 在进行第一轮操作时有几种操作方案可以保证她的胜利, 两种操作方案不同当且仅当选取了编号不同的石子堆, 或选取了相同编号的石子堆但是取走了不同数量的石子.注意在第 $2$ 类操作中, Alice 和 Bob 并不会真的进行游戏, 所以也不会对石子堆有任何改变.
Alice 和 Bob 虽然回答了询问, 但是 Charlie 不相信他们的答案. 请你编写程序计算每次游戏时 Alice 在第一轮中的可行操作数.
$n, q\le 2\times 10^5$
感觉较简单.
先考虑查询, 考虑求有多少种走完先手必败, 也就是异或和为 $x$, 那么求出当前区间异或和 $s$, 就是有多少个数 $a$ 使得 $a^(a-i)=(s^x)$, 也就是 $a^(s^x)<a$, 发现这个等价于 $a$ 在 $s^x$ 的最高位上为1.
瞪着那个修改, 显然有个均摊: 区间内值的个数是递减的, 可以用Segment Tree Beats, 如果当前区间不只有一个数就向下递归, 维护区间内每个位上的 $1$ 的个数, 复杂度是 $n\log n\log v$
C. 滑冰
有一个 $n\times m$ 的滑冰场, 其中有一些障碍物. 你一开始在滑冰场的某个位置上.
每次你可以选择上下左右四个方向之一进行移动, 因为冰面很滑所以你会一直朝选定的方向移动直到碰到边界或障碍物.
用
.表示无障碍物的冰面, 用#表示障碍物, 用S表示你初始的位置(这个位置也是无障碍物的冰面), 例如:
. . . . .
. . . . .
#. S. #
. . . . .
. . #. .就描述了一个可能的滑冰场. 将第 $i$ 行第 $j$ 列的位置记作 $(i, j)$, 则你在 $(3, 3)$, 向上会移动到 $(1, 3)$, 向下会移动到 $(4, 3)$, 向左会移动到 $(3, 2)$, 向右会移动到 $(3, 4)$.
现在将一些无障碍物的冰面上放上标记点, 用
o表示, 也就是说o表示标记点, 而且这个位置也是无障碍物的冰面.保证你初始的位置上没有标记点.
请问你能否规划一个移动方式, 使得你的移动路线可以经过所有的标记点呢?
对于一个极长的横着/竖着的段, 走到一个点就能走到全部.
对于每个标记点, 要求横着/竖着的段至少选择一个.
这个限制是2SAT, 限制是若两个段不可以在某个方向连通, 就不能同时选, 考虑这样得到的最终选择集合以及其中表示”可以走”的关系的连边, 因为得到的是竞赛图+某些部分有双向边(当双连通时), 因此缩点后是链, 一定可以走出来.
Day2
A. 我已经完全理解了DFS序线段树
给定一棵有 $n$ 个结点的有根树, 根结点为 $1$ 号点.
每个点有权值 $a_i$, 初始时均为 $0$, 以及花费 $v_i$, 表示对它进行一次操作时要花费的代价.
对点 $u$ 进行一次参数为 $x$ 的操作, 即是在树中将它子树中的所有点的权值都加上 $x$. 要求 $x$ 为整数且 $1\le x\le 10^9$
要让每个叶子的权值互不相同且非零, 即当 $i, j(i\neq j)$ 为叶子时要满足 $a_i\neq 0$ 且 $a_i\neq a_j$.
你需要构造一个总花费尽量小的操作序列.
$2\leq n\leq 2\times 10^5, 1\leq v_i\leq 10^9$.
考虑让花费最小: 容易发现一个简单贪心, 合法方案下, 一个点的作用是它可以等同于子树内的任意一点(你可以操作这个点, 然后不操作其子树里的每一个点), 于是可以从底向上贪心.
那么问题是确定了操作集合之后如何构造 $x$.
现在已经有了每个叶子到根的集合互不相同, 也就是任意两个叶子最深的操作点不同, 所以按照操作点从上往下操作, 就可以逐步确定叶子. 于是就可做了.
一个牛逼做法是, 随机, 冲突了就重新随, 大约30次就能找到.
B. 我已经完全理解了字符串哈希
对于两个合适的整数 $base$ 和 $m$, 可以定义字符串哈希函数 $h(s)$:
$$h(s)=(\sum_{i=1}^{|s|}s_i\cdot base^{|s|-i})\bmod m$$
其中 $s = s_1s_2. . . s_{ \vert s \vert }$ 是一个由小写字母组成的字符串, 并且假设每个字符在式中被看成它在字母表中的编号, 例如字符
a被看成 $1$.本题中我们取 $base = 2333333, m = 998244353$.
给定一个字符串 $s$, 请求出它的所有连续子串中哈希值的最大值.
保证给定的字符串是随机生成的: 先指定字符串长度, 每个字符随机在 $26$ 个小写字母中选取.
$\sum \vert s\vert \le 10^6$
第一反应是对着前缀和, 一个数据结构扫描线上去扫, 但被取模干爆了.
注意到数据随机, 那么可以当成有 $n^2$ 个随机数, 此时最大值应该在 $m-\dfrac{m}{n^2}$ 附近, 那么从 $m$ 开始, 每次 $O(n)$ 的验证某个答案, 复杂度是惊喜的 $\dfrac{m}{n}$, 又因为大家都会 $n^2$ 暴力, 平衡一下看起来就很好.
那么问题来到 $O(n)$ 验证是否存在某个答案, 容易想到先前缀和, 于是就是求 $j$ 使得 $s_i-s_j\cdot base^{i-j}=v, \dfrac{s_j}{base^j}=\dfrac{s_i-v}{base^i}$, 于是一个哈希表即可.
C. 我已经完全理解了多源BFS
在平面直角坐标系中, 称横纵坐标均为整数的点为格点.
对于两个格点 $(x_1, y_1)$ 和 $(x_2, y_2)$, 定义它们相邻当且仅当 $\max( \vert x_1-x_2 \vert , \vert y_1-y_2 \vert ) = 1$.
给出 $n$ 个互不相同的作为 BFS 源的格点 $(x_1, y_1), (x_2, y_2), . . . , (x_n, y_n)$, 以及一个参数 $k$, 从它们出发进行多源 BFS:
- 对于所有格点 $(x, y)$, 令 $dis(x, y)\gets 0$. 并维护一个队列, 初始时为空.
- 对于 $1 ≤ i ≤ n$, 将 $(x_i, y_i)$ 入队, 并令 $dis(x_i, y_i)\gets 1$.
- 取出队首格点, 假设为 $(x_p, y_p)$, 如果 $dis(x_p, y_p) = k$, 转到 $5$.
- 枚举所有与 $(x_p, y_p)$ 相邻的格点 $(x_q, y_q)$, 如果 $dis(x_q, y_q) = 0$, 则将 $(x_q, y_q)$ 入队, 并令
$dis(x_q, y_q)\gets dis(x_p, y_p) + 1$.- 如果队列非空, 转到 $3$, 否则多源 BFS 结束.
对所有格点 $(x, y)$ 的 $dis(x, y)$ 求和, 可以证明这个数是有限的.
由于答案可能很大, 你只需输出答案对 $998244353$ 取模的结果.
肯定要扫描线, 那么对于一条平行于 $y$ 轴的扫描线分成若干区间, 每个区间对应的起点相同, 那一个区间改变就是扫描线扫到了某两个出发点在横轴上的中点, 或者进入/退出某个起点的区域, 次数是 $n^2$ 量级的.
开什么玩笑, 俩东西都交点是斜线.
官方正解是考虑按照 $k$ 分层, 每次加上这层的 $k$ 和上层的 $k$ 的面积差再乘 $k$ 的式子, 其中这个会发生 $n^2$ 次变化(两个起点同时拓展到某个区域), 注意到在某个不变化的区间内这个差是二次函数, 所以可以直接取三个点值插出答案. 算点值的方法就成了矩形并矩形面积, 复杂度 $n^3\log n$
另一个做法是直接转曼哈顿距离, 然后过每个起点画横竖线, 得到 $n^2$ 个矩形, 注意到每个矩形都是四个角先被拓展到, 然后才是里面的东西, 而两个角在矩形内的贡献的分割线是一条水平竖直线(相邻)或斜线(对角), 于是每个角的贡献是一个缺一个角的五边形的形态, 可以直接数学方法暴力算贡献, 复杂度为 $O(n^2)$
Day3
陌生的城市
济南对于小猫来说是一座陌生的城市. 今天小猫带来了家乡的土特产——FJOI 字符串题.
小猫喜欢循环串. 如果字符串 $s$ 的长度为 $n$ 而最小循环节长度为 $m$, 定义它的美观度为 $\frac{n^2}m$. 这里循环节要求 $m \vert n$.
FJOI 喜欢子序列. 给定一个只包含 $a, b, c$ 的字符串, 求其全体非空子序列的最大美观度.
多组数据.
$t\le 10, n\le 10^5$
首先, 注意到它写的不是子串(? )
答案最小是 $\dfrac{n^2}{9}$, 于是只用考虑 $m\le 8$ 的那部分, 然后暴力跑匹配, 算一下计算量是 $10^10$
考虑预处理每个位置往后6位, 运算量是 $1. 6e9$.
考虑每个循环移位出来的串, 可以只跑一次匹配, 然后 $O(m)$ 的一起处理, 现在应该在 $2e8$ 到 $3e8$ 之间.
冲!
好吧, 正解表示, 设重复 $k$ 次, 答案是 $k^2m$, 而考虑出现次数最多的那个数的出现次数 $(k\dfrac{m}{3})$, 如果我们不是直接用这一个数更新答案, 那么就有一个不等式, 发现 $m\in {2, 3, 5, 6}$, 就直接做完了.
大原题
有 $n$ 个盒子, 第 $i$ 个盒子里有 $a_i$ 个标有数字 $i$ 的球, 代表第 $i$ 种奖品.
接下来依次进行 $m$ 次操作, 每次指定两个不同的盒子 $x_i, y_i$, 玩家可以从 $x_i, y_i$ 中各拿出一个球交换, 也可以放弃这次机会.
玩家最终会抱着第 $1$ 个盒子回家, 所以目标是最大化第 $1$ 个盒子中的数字种类数.
$n, m, a_i\le 3000$
每个交换看作边, 盒子看作点, 就是一张图, 从 $1$ 出发, 走边权递增的不交的路径能到最多多少个盒子. 考虑网络流, 能到多少个点就成了每个点有 $1$ 的入流求最大流, 前面的部分可以来一个点边互换. 但这是无限 $a_i$ 版.
考虑 $a_i$ 点限制是同一时刻盒子里装的最大球数, 把盒子按照时刻拆点成一列, 每一时刻向下一时刻连 $a_i$, 这样点边互换部分可以删了. 每个点建连用到的时间, 点数是 $n+2m$, 边数是 $4m$ 这样的.
需要快速的网络流.
美丽的世界
小猫和粉兔在异世界探险. 他们得到了 $m$ 件装备, 要进行分配. 小猫和粉兔各有 $n$ 个装备栏, 每栏至多穿戴一件装备. 同一件装备会对两个人的战斗力都产生影响, 他们的战斗力也就是他们所有装备提供的战斗力之和. 现在要求符合条件下的所有分配方案中, 合作战斗力的最小值. 保证存在至少一种合法的分配方案.
$n\leq 5 \times 10^5, m\leq 2n$
$1\leq x_i, y_i\leq n$
$0\leq a_i, b_i\leq 10^6$
$\sum^n_{i=1} a_i, \sum^n_{i=1} b_i\leq 2 \times 10^9$.
容易想到把装备栏看成两排点, 每个装备看成一条边 $(x_i, y_i)$, 那么因为每个栏最后只有一个入度, 所以有解给出的一定是一个基环树-树的森林.
把两个人的得分画到平面上, 那么有若干点, 用 $y=\dfrac{k}{x}$ 去切, 发现最后一定是一个左下凸壳, 于是把每个连通块的所有可能答案(基环树只有两个, 树枚举每个点作为根)算出来跑闵和.