THUPC2024 邮寄
THUPC2024 邮寄
和Mikefeng和Harry23182组队, 来看看往年题.
THUPC2023 Pre
P9140 [THUPC 2023 初赛] 背包
因为 $V$ 远大于 $v_i$ 和 $n$, 所以考虑贪心, 选出其中性价比最高的元素 $i$, 则就是要在模 $m=v_i$ 的意义下求恰好为 $V$ 的最大价值, 这个几乎是同余最短路, 因为此时总代价是 $\dfrac{V-v}{m}c_i + res$, 其中 $res$ 为选出的元素的 $c$ 之和, 所以实际上是最大化 $res-\dfrac{v}{m}c_i$, 于是同余最短路时先 $i\to j+v_i$ 连 $c_i-\dfrac{v_i+j}{m}c_i$ 的代价即可.
然后同余最短路实际上不用写最短路, 它是个模 $m$ 的完全背包问题, 加入物品时这个物品的转移形成 $gcd(m, v_i)$ 个环, 只要对每个环转移两圈即可保证转移完全. 复杂度 $nm$
P9143 [THUPC 2023 初赛] 众数
从大到小排即可.
P9134 [THUPC 2023 初赛] 拧螺丝
老板肯定每次拿走最大的, 小E肯定尽量平均的加, 于是反向考虑, 最后拿走时是 $n$ 个, 那么上一次一定是 $n-k, n-k$, 往后推下去, 则老板每次会让最大值数量增加 $1$, 然后小E让最大的若干个减少 $1$, 暴力就是朴素的模拟这个直到最大值变成 $0$. 于是同一时刻只有最大值和最大值减 $1$ 两个数.
那么考虑把最大值次大值不变的一段压到一起处理, 又因为高精所以复杂度 $n^2$, 然后再特判掉 $n=2$ 时答案是 $2^{n-2}$.
P9133 [THUPC 2023 初赛] 大富翁
支配的代价实际上是有祖先关系的点对代价 $1$, 那么就是最后局面 $\text{敌方点祖先中我方个数}-\text{我方点祖先中敌方个数}$, 于是对于每个我方点 $u$, 答案是 $\text{深度}-\text{我方祖先个数}+\text{敌方子孙个数}$, 转化贡献, 变成每个点给所有子树中的我方点贡献 $-1$, 就成了 $dep_u-siz_u$, 于是按照 $dep_u-siz_u+w_u$ 排序贪心选即可.
P9142 [THUPC 2023 初赛] 欺诈游戏
纳什博弈的结论好像就是最优策略下所有情况期望收益相等.
但是不排除可能双方各自放弃一些决策的情况, 不过发现看起来放弃任意一个位置都是不优的.
如果猜到结论, 选取任意情况期望都相等, 就可以直接列式子解出策略了, 当然不能高斯消元, 注意到式子形如 $x\sum_{i<x} p_i+\sum+{i>x} p_i dfrac{i}{2}$, 此时 $x+1$ 减 $x$ 的式子是 $\sum_{i<x} p_i+p_x+p_{x+1}\dfrac{x+1}{2}=0$, 此时可以递推的把所有 $p$ 用 $p_1$ 表示, 最后用 $\sum_i p_i=1$ 就能解出来.
P9137 [THUPC 2023 初赛] 速战速决
分类讨论, 如果你手里有两张相同的则你可以保证对面一张也收不回去(保持牌底的另一张在你手中), 否则对面至少收回去一次, 并且可以让它最多收回去一次, 发现只要第一次放 $n$, 后面跟着小 $J$ 放即可.
P9138 [THUPC 2023 初赛] 公平合作
后手策略一定是一直装直到大于先手装的的或者爆了. 那么可以设 $f_i$ 表示要求至少装到 $i$ 的情况下不爆的概率(先手选 $i$ 时后手胜的概率), 那么先求 $g_i$ 表示装到 $i$ 的概率 $g_i=\sum_k g_{i-a_k}\dfrac{1}{n}$, $f_i=1-(\sum_{k<i} g_k\sum_{k+a_l>n} \dfrac{1}{n})$, 最后先手再列一个递推式 $h_i=\min f_i, (\sum_k \dfrac{1}{n}h_{i+a_k})$. 于是获得了一个 $nL$ 的做法.
然后不会了, 然后发现这三个都是常系数线性递推, 可以做到 $n\log n\log L$
P9144 [THUPC 2023 初赛] 最后的活动
注意到只有 $6$ 层, 于是可以直接设 $f_i$ 表示打到当前还剩 $i$ 到 $m$ 的情况下的概率, 枚举每一层的策略然后每次转移一整局, 如果这一局收益为 $x$ 那么转移到 $f_{i-x}$, 但是转移可能成环, 即 $x=0$, 于是考虑直接二分, 因为 $f_i$ 一定会乘上一个系数所以答案一定比你赋的初值更接近真实值, 就做完了.
P9135 [THUPC 2023 初赛] 快速 LCM 变换
只操作一次, 就是删掉两个数再插入一个数. 但是lcm的和对每个质因数没有好的独立性, 所以只能一起做.
现在只考虑一个因数 $d$, 删除了数 $p, q$, $d$ 的最大值会变成 $\max (smx, p+q)$, 那么如果 $p+q$ 有贡献一定意味着 $p, q$ 都是 $mx$, 此时一定不会让 $d$ 的最终指数减少, 也就是说它们的贡献可以独立着看, 要么是 $p$ 或 $q$ 带来的减少要么是 $p+q$ 带来的增加, 或者说可以写出函数使得 $f(x)$ 为删掉 $x$ 的贡献, $g(x)$ 为增加 $x$ 的贡献, 则答案为 $\mathrm{lcm}({a_i})f(x)f(y)g(x+y)$
于是这个就好做了啊, 卷卷即可.
P9139 [THUPC 2023 初赛] 喵了个喵 II
先考虑如果 $2$ 次怎么做, 则若有两种数的出现位置发生包含 $a, b, b, a$, 则一定无解, 因为一定是一个 $a, b$ 一个 $b, a$. 否则一定有解(一个子序列都放第一次出现的).
然后 $4$ 次, 考虑能不能把这 $4$ 个位置 $a, b, c, d$ 先分成两个颜色, 则只有 $(a, c), (b, d)$ 和 $(a, b), (c, d)$ 是可能的划分, 那么可以写出2sat关系.
但是直接2sat关系爆炸了, 注意到实际上每个2sat关系限制是矩形: $(a, c), (b, d)$ 连向有区间被 $(a, c)$ 或 $(b, d)$ 包含的区间选择另一种方式, 而包含是矩形, 于是主席树建图优化2sat即可.
P9136 [THUPC 2023 初赛] 种苹果
就是加叶子, 边上加点, 区间加, 区间rank, 因为这个东西序列上都不能低于根号所以树上你肯定也得根号复杂度.
于是树分块, 此时区间加区间rank就维护有序数组和加法标记上去二分, 加叶子和边上加点, 发现可以直接上去调整, 树的形态只维护父亲就行, 然后保证复杂度需要根号重构, 最后平衡复杂度是 $n\sqrt{n\log n}$
THUPC2022 Pre
P8213 [THUPC2022 初赛] 挑战
直接倒着dp就行吧
P8207 [THUPC2022 初赛] 最小公倍树
考虑要么是Kru要么是Brovka, 同时这个lcm大概让你考虑gcd.
考虑枚举gcd值 $d$, 对于 $dk, d(k+1)\ldots d(k+p)$, 暴力会连 $p^2$ 条边, 但后面的都只要和 $dk$ 连就好了, 于是总连边数是调和级数过了.
P8208 [THUPC2022 初赛] 骰子旅行
根据期望线性考虑能不能单独求每个点的期望经过次数, 那么暴力dp是计算 $f_{u, i, t}$ 表示现在在 $u$, 走了 $i$ 次, $t$ 的期望经过次数, 复杂度是 $(\sum m)nT$, 同理可以出 $g_{u, i, t}$ 表示现在在 $u$, 走了 $i$ 次曾经过 $t$ 的概率.
P8211 [THUPC2022 初赛] 搬砖
注意到如果所有 $b\ge 1$ 则最多只会进行 $\sqrt n$ 次, 按照 $d$ 是否 $>\sqrt n$ 讨论即可证明.
于是肯定考虑一次处理一段 $d$ 不变的, 而这个只要找到下一个不为 $0$ 的 $b$, 直接二分就是单log, 并查集可以整成线性.
但是不对, 因为可能在这过程中因为没有搬完一摞而结束, 所以考虑对每个 $d<\sqrt n$, 按 $d$ 分块, 根据一开始的偏移维护 $d$ 个长 $\dfrac{n}{d}$ 的数组, 每次插入一个数遍历每个 $d$, 会修改两个偏移区间的同一个位置的值, 于是就是 $\sqrt n$ 次单点修改和查询, 总复杂度 $n\sqrt n\alpha(n)$
关键大概是 $\sqrt n$ 次以及对小于 $\sqrt n$ 的每个长度和偏移分块是 $n\sqrt n$ 的
P8212 [THUPC2022 初赛] 喵喵花園
确定一个起始位置就都确定了, 那么考虑随着起始位置变化本来每个点位置都在直线上移动, 直到有一个点移动到下一条边, 于是整个函数是 $n$ 段的. 就成了已知每个点坐标为 $p_i+v_it$ 求面积, 而面积是相邻两项叉积的和, 是二次函数, 那么每次暴力算下一个段的起始点并暴力求二次函数看起来是简单的啊.
但是是不是, 当你修改一个位置的时候你只是单点改 $p$ 和 $v$, 于是二次函数修改可以 $O(1)$, 而每次要找下一个起始点也可以维护, 是单点改大, 求最小值, 看起来可以单log整体.
P8215 [THUPC2022 初赛] 分组作业
看到这么离谱的东西应该想流, 先给每个人建一个点
然后首先最基本的是愿意, 可以用一边的边建成割/不割表示是否愿意, 也可以用两边的与源汇连边表示愿意, 看起来后者信息更多, 这里认为割源点的边表示愿意.
然后对于合作, 只要两者各建一条边连 inf 到一个新点, 新点向汇点连代价, 这样只有这条汇边被保留表示合作. 同时再用一条边连到源点, 也是二选一表示合作和不合作即可.
然后对于 $e$ 的代价显然只要两个人之间连有向边.
然后喜欢就是刚才的合作建出来的点向另一边表示愿意的点连边即可.
然后你要保证你做的是不能一个人/组把连到源点汇点都割了, 因为这么连人和组都至少割一个, 所以给这些边每个加 $inf$ 最后减掉即可.
THUPC 乱做
P7609 [THUPC2021] 游戏
让人想起移动金币那个题, 考虑逐位做, 设 $f_{i, S, j, 0/1}$ 表示考虑完低 $i$ 位, 当前 $S$ 中的数顶上界, 他们的和进位为 $j$, 总和是否小于等于 $n$ 的方案数.
然后直接做复杂度带 $4^m$ 爆炸, 这里按位从低往高不如从高往低, 因为那样只要考虑 $S$ 中的数, 其他数都不可能变的顶上界, 复杂度会变成 $3^n$,因为数位dp从高往低性质其实是比从低往高好在大小限制变化单调
P7604 [THUPC2021] 形式语言与自动机
考虑分成三段后它们的把括号看成 $\pm 1$ 序列后的和以及前缀 $min$ 的值 $s_1, s_2, s_3, m_1, m_2, m_3$, 则换完之后显然要满足 $m_1\ge 0, s_1+m_3\ge 0, s_1+s_3+m_2\ge 0$.
我们大概率扫描 $r$ 也就是枚举 $3$, 那么看起来第二个条件转化成 $m_2-s_2\ge 0$, 也就是后缀 $min=sm_2\ge 0$, 这样转化的好处是满足第二个条件的变成了一个区间, 显然 $m_1\ge 0$ 也是一个区间, 剩下的是 $m_3+s_1\ge 0$, 其中 $m_3$ 确定, 就是求 $s_1$ 的和大于某个值了. 总结一下发现这就是下标一维和一维的二维数点, 做完了.
P7605 [THUPC2021] 小 E 爱消除
容易想到区间dp, 那么设 $f_{l, r}$ 为答案后要转移, 以左边为例, 要么 $l$ 最后也没被消掉可以直接从 $f_{l+1, r}$ 转移, 否则假设找到与 $l$ 颜色相同的另一个位置 $i$, 则一定是拿出 $l$, 消空 $i$ 左边或右边(可能用到没被消空的一边), 比如消没左边, 那么枚举用了右边的 $k$ 个, 就转移到 $f_{i+1, r-k}$, 于是需要知道把 $j, k$ 端不可被删除的区间 $[i, j], [k, l]$ 完全消空的最小杯子大小 $g_{i, j, k, l}$, 而 $g$ 可以用一样的方式转移, 最后复杂度 $n^6$, 然后靠玄学常数过题.
P7606 [THUPC2021] 混乱邪恶
好棒的题
就是, 本来你肯定直接dp设 $f_{i, l, g, x, y}$ 表示考虑完前 $i$ 个idea, 然后 $l, g$ 的值和自己的坐标 $x, y$(六边形可以转化成走 $x, y$ 和沿着 $y=x$ 走), 然后获得复杂度 $n^3p^2$ 再靠bitset压上 $\dfrac{n^3p^2}{w}$
见识新dp优化方案了. 一个众所周知的结论是二维平面随机游走期望距离 $\sqrt n$, 所以可以把输入的idea随机打乱然后把 $x, y$ 只开到 $\sqrt n$, 使得转移过程中不会出现很大的 $x, y$, 复杂度就成了 $\dfrac{n^2p^2}{w}$
[trick] 随机游走结论更改添加物品顺序以优化dp状态
P7136 [THUPC2021 初赛] 方格游戏
注意到最关键的部分: 对任意 $i, j$, $D_i+1<U_j$ 或 $D_j+1<U_i$ 以及横向的, 这个说明不可能用障碍物围迷宫之类的, 甚至任意两点只会被一个障碍物影响, 因为横竖独立可以光看一边, 以纵向绕远为例, 因为某个障碍物绕远的条件是起点终点都属于障碍覆盖的纵坐标区间, 则会绕一下.
而绕远距离是简单一次函数, 求完和二次函数乱算即可.
P7607 [THUPC2021 初赛] 赌徒问题
看起来枚举 $s$, 然后拿出所有因数暴力背包的复杂度是 $m^2d(mk)$, 其中 $d(mk)$ 大约是 $6000\sim 10000$ 之间, 过不了.
考虑背包的时候 $k$ 的约数先都加进去, 每次只插入不是 $k$ 的约数而是 $sk$ 的约数的部分, 复杂度就下来了.
于是开打THUPC2024 pre
7题, 但自己只过了一个, 被队友带飞了.
M. 你说得对, 但是AIGC
如果是You are right, but开头就是AI.
H. 二进制
今天也是喜欢二进制串的一天, 小 F 开始玩二进制串的游戏.
小 F 给出了一个这里有一个长为 $n$ 的二进制串 $s$, 下标从 $1$ 到 $n$, 且 $\forall i\in[1, n], s_i\in {0, 1}$, 他想要删除若干二进制子串.
具体的, 小 F 做出了 $n$ 次尝试.
在第 $i\in[1, n]$ 次尝试中, 他会先写出正整数 $i$ 的二进制串表示 $t$(无前导零, 左侧为高位, 例如 $10$ 可以写为 $1010$).
随后找到这个二进制表示 $t$ 在 $s$ 中从左到右第一次出现的位置, 并删除这个串.
注意, 删除后左右部分的串会拼接在一起形成一个新的串, 请注意新串下标的改变.
若当前 $t$ 不在 $s$ 中存在, 则小 F 对串 $s$ 不作出改变.
你需要回答每一次尝试中, $t$ 在 $s$ 中第一次出现的位置的左端点以及 $t$ 在 $s$ 中出现了多少次.
定义两次出现不同当且仅当出现的位置的左端点不同.
请注意输入输出效率.
$n\le 10^6$
Harry秒了
显然这个尝试的串长度是 $\log_{10}(n)$ 的, 非常短, 那么直接字符串哈希(都不用哈希, 直接拿这个串表示的二进制数就行), Harry写的是可删堆去维护hash值的出现位置并求位置最小值(因为删掉原序列一个数两边拼起来会减少一些hash形成一些新的hash, 要暴力更新, 所以要支持删除), 上链表维护删除一个数并把两边拼起来的操作, 用BIT维护被删了的元素的位置.
复杂度是2log, 但有一个log底数是10.
C. 前缀和
小兰很喜欢随机数.
TA 首先选定了一个实数 $0 < p < 1$, 然后生成了 $n$ 个随机数 $x_1, \dots, x_n$, 每个数是独立按照如下方式生成的:
- $x_i$ 有 $p$ 的概率是 $1$, 有 $(1-p)p$ 的概率是 $2$, 有 $(1-p)^2p$ 的概率是 $3$, 以此类推.
生成完这些随机数之后, 小艾对这个数列求了前缀和, 得到了数列 $y_1, \dots, y_n$.
给定 $1\leq l\leq r\leq n$, 小兰想知道, 期望有多少 $y_i$ 落在 $[l, r]$ 内?
$n, l, r\le 10^9$
赛时代数推导天地灭式子的角标推错了, 还是靠Mikefeng, 喵的重推一遍.
$x_i$ 为 $n$ 的概率显然是
$$
[z^k]\dfrac{pz}{1-(1-p)z}
$$
于是 $y_k$ 为 $n$ 的概率是
$$
\begin{gathered}
[z^n]\dfrac{p^kz^k}{(1-(1-p)z)^k}\
=[z^n]p^kz^k\sum_j \binom{-k}{j}(-1)^j(1-p)^jz^j\
=[z^n]p^kz^k\sum_{j=0}^{n-k} \binom{k+j-1}{j}(1-p)^jz^j
\end{gathered}
$$
原来要求 $[l, r]$ 中的可以改成求 $[1, r]$ 中的差分, 其中少于 $r$ 的期望个数为
$$
\begin{gathered}
\sum_{i=1}^n \sum_{j=0}^{r-i} p^i(1-p)^j\binom{k+j-1}{j}\
=\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}p^{i-j+1}(1-p)^j\binom{i}{j}\
=\sum_{i=0}^{r-1}p(1-p+p)^{i}\
=rp
\end{gathered}
$$
所以答案就是 $(r-l+1)p$
K. 三步棋
K 家里有一条不成文的规矩. 如果家里只有 K 和 H 两个人, 那么两个人会通过一种叫作”三步棋”的游戏来决定谁做饭. 三步棋的规则与五子棋有一些相似之处. 众所周知, 五子棋是一种先连出五枚己方棋子者获胜的游戏. 与五子棋相同的是, 三步棋中双方也轮流在网格状的棋盘上摆放棋子, 并根据是否连成指定的图案决定胜负. 与五子棋不同的是:
- 三步棋不区分双方的棋子, 即可以认为双方执同色棋子进行游戏;
- 在判定时, 指定的图案不能旋转;
- 如果连成指定的图案时, 棋盘上的棋子数量恰好为 $3$ 的倍数, 则连成指定的图案的一方获胜, 否则判定该方负(即对方获胜).
在 K 家, 为了节约时间, 通常使用 $5\times 5$ 的初始为空的棋盘进行三步棋. 同时, 每次也只会随机选择一个由不超过 $4$ 枚棋子组成的四连通图案. 显然三步棋不存在平局, 所以 K 和 H 约定由输的一方负责做饭. K 想知道, 如果自己和 H 都足够聪明, 那么以选中的图案进行的三步棋游戏是否为先手必胜; 因为如果她更容易赢, 她就要偷偷地给自己的妹妹放水.
首先容易看出这是个爆搜题.
然后HarryTLE了, 爆搜冲不过, 需要打表. . .
打完就过了, 这里可以用对称性少打几个.
J. 套娃
我们定义一个集合的 $\mathrm{mex}$ 是最小的不在 $S$ 中的非负整数.
给定一个序列 $a_1, \dots, a_n$, 对于每个 $1\leq k\leq n$, 我们按照如下方式定义 $b_k$:
- 对于 $a$ 的所有长为 $k$ 的子区间, 求出这个子区间构成的数集的 $\mathrm{mex}$.
- 对于求出的所有 $\mathrm{mex}$, 求出这个数集自己的 $\mathrm{mex}$, 记为 $b_k$.
请你求出序列 $b$.
$n\le 10^5$
Mikefeng秒了.
包含某个出现了 $cnt$ 次的值的区间在平面上是 $O(cnt)$ 个矩形, 不包含的是一个下阶梯, 那么相当于平面上若干个矩形取min后得到的就是mex, 那么转换维度, 从小大大枚举值, 维护mex小于当前值的区域(一个下阶梯), 每次插入一个矩形就是给阶梯新添加一块, 且新加的区域的mex恰好是当前枚举的值, 而且新加的一块在 $x+y$ 上一定是一个区间, 也就是新加的区域的区间长度是一个区间, 而当前值插入的所有矩形求出的区间的并就是那些包含至少一个区间以当前值作为mex的所有长度.
求出长度区间扫一遍就做完了.
E. 转化
小 E 有 $n$ 种颜色的球, 其中第 $i$ 种有 $a_i$ 个. 有两类工具, 第一类可以把一个指定颜色的球变成一个任意颜色的球; 第二类可以把一个指定颜色的球变成两个这种颜色的球. 一个变化之后的球也可以通过工具产生新的变化. 关于第 $i$ 种颜色的第一类工具有 $b_i$ 个, 第二类工具有 $c_i$ 个.
小 E 想知道, 如果每一个工具最多只能使用一次, 那么对于每种颜色 $i$, 第 $i$ 种颜色的球最后最多能有多少个. 以及, 小 E 最后最多能有多少个球.
$n\le 5\times 10^5, a_i, b_i, c_i\le 10^9$
C过之后去开E了, 很好想, 但是一直在写愚蠢错误, 并且没有大样例不知道错哪的贪心题.
先考虑第一问求到第 $k$ 种颜色的最多有多少, 那么把其他球分成三类, $b_i=0$ 的部分不用考虑, $b_i\ne 0, a_i\ne 0$ 的可以直接 $a_i’: = a_i+c_i$, 并可以提供 $d_i\min (b_i, a_i’)$ 的贡献(这里把贡献定义成可以根据需要转换成任意颜色的球数), 然后 $b_i\ne 0, a_i=0$ 的球, 需要先消耗一个球, 然后用二类工具, 则它们的贡献是 $\min (b_i-1, c_i)$, $-1$ 是把转入的球转出去的代价. 这样答案就是所有点的贡献, 再加上 $a_k$, 此时求出来的结果如果不为 $0$ 就再加 $c_k$.
对于第二问, $a_i\ne 0, b_i\ne 0$ 的球不变, $a_i=0, b_i\ne 0$ 变成了如果转入一个球会贡献 $\min(b_i-1, c_i)$, 会给总数增加 $(c_i)$, 此时你会剩下若干贡献可以转换成其他球, 这些应该送到 $b_i=0 0, a_i=0$ 中 $c_i$ 前若干大的球, 然后对于 $b_i=0, a_i\ne 0$ 的球直接把 $a_i+c_i$ 到总数.
调了一年, wa了4发///fn
D. 多折较差验证
对于所有折痕互相平行的说明书, 可以按照说明书上文字的阅读顺序从上到下给每条折痕分别编号 $1, 2, \cdots, N$, 这 $N$ 条折痕将说明书分成了 $(N+1)$ 条纸带. 每条折痕可能为两种形态之一: 一种是垂直纸面向内凸出, 对应将纸的上下两半向前对折; 一种是垂直纸面向外凸出, 对应将上下两半向后对折. 根据折痕截面的形状, 分别使用小写字母
v表示向内凸出的折痕,^(ASCII 码为 $94$)表示向外凸出的折痕. 假设所有纸带的宽度都是一样的, 并且折纸的过程中说明书不发生形变, 那么沿着一条折痕对折后两侧的纸能够重合, 当且仅当两侧的折痕是相反的; 即, 如果沿着第 $k$ 条折痕折叠, 那么对于所有满足 $1\le k-m<k+m\le N$ 的正整数 $m$, 第 $(k-m)$ 条折痕和第 $(k+m)$ 条折痕的形态是相反的. 例如, 对于折痕依次为v^v^^^^v的说明书, 可以沿其第 $7$ 条折痕进行折叠. 根据定义可知, 一张说明书总能沿着第一条或最后一条折痕进行折叠. 折叠之后的说明书可以用被折叠的折痕两侧中, 剩余折痕数量较多一侧的折痕表示, 如v^v^^^^v沿着第 $7$ 条折痕折叠后得到v^v^^^. 如果被折叠的折痕两侧折痕数量相等, 那么用哪一侧的折痕表示折叠后的纸都可以, 因为折痕在三维空间中是旋转对称的. 特别地, 对只剩下一条折痕的说明书, 即v或^进行折叠后, 所有 $(N+1)$ 条纸带都重叠在一起, 此时称这张说明书被折叠整齐.虽然按顺序依次折叠每一条折痕, 总能将说明书折叠整齐, 但 Kanan 觉得这样并不美观. 一种美观的折法应该尽量少折, 并且每次折的时候折痕两侧应该尽可能的对称. 定义一种折法的不对称程度为每次折叠时, 被折叠的折痕两侧的折痕数量之差的总和. 给出一张说明书的折痕, Kanan 想知道最少需要折多少次才能将这张说明书折叠整齐, 以及所有折叠次数最少的折法中, 不对称程度的最小值.
$n\le 5000$
长得像区间dp, 真的是区间dp, 直接区间dp显然是 $n^3$ 的.
然后你看到这个就会猜有效转移不多, 因为条件看着很苛刻, 所以考虑求出所有有效转移只转移这些, 然后过了.
题解表示能卡到 $n^2\log n$, 但也没证出来.
B. 一棵树
这里有一棵树, 具体的, 这是一张有 $n$ 个节点和 $n-1$ 条边组成的无向联通图.
每个节点初始颜色为白色, 你需要恰好将其中 $k$ 个节点染成黑色, 定义一条边的权值是, 断开这条边之后, 两个连通块的黑色节点个数之差, 定义一棵树的权值为所有边的权值求和, 你需要最小化整棵树的权值.
$n\le 5\times 10^5$, 1s
赛时最后1. 5h会了这个题, 结果没调出来寄了.
以 $1$ 为根, 首先显然可以把贡献转化成 $\sum_{u\ne 1} \vert k-2cnt_u\vert$, 其中 $cnt$ 为 $u$ 内黑点个数.
于是dp, $f_{u, i}$ 表示 $u$ 子树内染了 $i$ 个黑点, 转移的话是先把所有子树做 $\min, +$ 卷积然后再加上绝对值函数 $\vert k-2i\vert$, 这东西是很典的凸性题.
实现的话因为这个绝对值加的位置固定所以直接开两个大根堆, 堆里塞 $pair(k, l)$ 表示一个斜率为 $k$, 长度为 $l$ 的斜率连续段, 这样区间加直接打标记, 然后用启发式合并. 复杂度 $n\log^2 n$, 赛时先T一发, 卡常完了还CE了然后比赛结束.
靠这里启发式合并直接换可并堆就单log啊.
[think] 碰到这种凸性题之后要想到底要维护什么, 维护原数组, 差分数组(用数据结构维护每个位置即对应差分)/差分连续段(搭配堆/数据结构)/差分变化 $1$ 的位置. 要做闵和而且不是和 $O(1)$ 段函数做闵和的时候基本上只有差分连续段是能用的对应直接数据结构合并. 此外一般需要你维护/能快速求某个特定位置的dp值来求答案.
比赛结束之后发现写的会WA, 输麻了, 码力过低.
G. 采矿
矿坑是二叉树形结构, 有 $n$ 个节点. $1$ 号点为地面, 对于所有的 $2\le i\le n$, $i$ 号节点与更浅层的 $f_i$ 号节点通过通道相连, 其中 $f_i<i$, 且相同的 $f_i$ 最多出现两次. 矿坑的不同节点的产量和开采难度均不相同. 对于 $i$ 号节点 $(2\le i\le n)$, 如果派一个机器人开采, 一单位时间内能有 $r_i$ 的产出; 如果派一个人类开采, 一单位时间内能有 $p_i$ 的产出. 地面没有产出. 你有一个机器人, 初始位于 $s$ 号节点. 你的矿坑里初始没有人类工人.
你现在有 $q$ 条计划需要按顺序执行. 每个计划分为准备、执行、调整、开采四个阶段.
在准备阶段, 人类可以在满足移动规则的前提下任意移动, 但不能进入或离开矿坑(矿坑内的工人到达 $1$ 号节点不算离开矿坑), 移动的顺序和次数均没有限制. 机器人不能移动.
在执行阶段, 不同计划需要做的事情可能不同, 共分为 $4$ 种:
- 机器人只能沿通道向更浅的方向移动, 且至少需要经过一条通道. 人类不能移动.
- 机器人只能沿通道向更深的方向移动, 且至少需要经过一条通道. 人类不能移动.
- 使一名人类从 $1$ 号节点进入矿坑(这意味着该阶段开始时 $1$ 号节点上必须没有工人). 除此之外所有工人都不能移动.
- 使一名人类从 $1$ 号节点移出矿坑(这意味着该阶段开始时 $1$ 号节点上必须有一名人类). 除此之外所有工人都不能移动.
在调整阶段, 限制与准备阶段相同. 在开采阶段, 所有的工人会采一单位时间的矿.
问按顺序执行完所有计划之后, 你所有计划的产出之和最多可以达到多少.
$n\le 300, q\le 600$
PS: 移动时不能穿过有工人的点
那么这不直接dp设 $f_{i, u, j, k, 0/1}$ 表示经过了前 $i$ 步, 现在机器人在 $u$, $u$ 的两棵子树分别有 $j, k$ 个人, 机器人是否移动过, 用树上背包一样的分析状态数是 $qn^2$, 转移用前缀和可以 $O(1)$
这题该过的, 只是最后榜上也只过了8个队根本不敢做.
I. 分治乘法
小艾想要挑战分治乘法. TA 将策略抽象成了如下问题:
现在给定一个目标集合 $T$, 该集合是 ${1, \dots, n}$ 的一个子集($1\leq n\leq 5\times 10^5$). 你需要通过一系列操作构造一些集合最后得到 $T$, 具体来说有以下三种操作:
- 创造一个大小为一的集合 $\vert S\vert =1$.
- 将已经被构造出的两个不交集合 $A, B$ 并起来, 得到 $A\cup B$.
- 将已经被构造出的一个集合 $A$ 进行平移, 也即 $A+x = { a+x : a\in A }$.
一个已经被构造出的集合可以在之后被使用多次. 同时你需要保证操作过程中出现的所有集合都是 ${1, \dots, n}$ 的子集.
你的代价是构造出的所有集合的大小之和, 你不需要最小化代价, 只需要让代价控制不超过 $5\times 10^6$ 即可. 你用的操作数量也不应超过 $10^6$.
朴素做法是直接用 $1$ 操作先把所有数拿出来然后合并, 复杂度显然是 $n\log n$, 比限制差不多正好大一倍.
考虑怎么使用操作 $3$, 按照 $L$ 分块, 则一块有 $2^L$ 种可能, 然后设 $S_i$ 表示 $i$ 这种可能出现的所有下标的集合, 则 $S_i$ 大小是 $\dfrac{n}{L}$, 构造出一个 $S_i$ 的代价就是 $\dfrac{n}{L}\log n$, 然后平移覆盖, 代价是 $n$
创建完之后要合并现在得到的 $L2^L$ 个集合, 直接分治复杂度是 $n\log (L2^L)=n\log L+nL$, 于是取 $L=\sqrt {\log n}$, 总复杂度 $n\sqrt {\log n}$
很厉害啊赛时只想着把连续的 $L$ 个分块, 处理出 $L2^L$ 种, 然后平移的代价是 $n$, 合并的代价是 $n\log \dfrac{n}{L}$ 没变. . .
[think]
题解: 先合并出 $L2^L$ 个总大小为 $\dfrac{n}{L}$ 的集合, 第二步合并 $L2^L$ 个集合.
我: 先合并出 $L2^L$ 个总大小为 $L2^L$ 的集合, 第二步合并 $\dfrac{n}{L}$ 个集合.
两步的合并是具有对称性的, 关键是把两步的复杂度平衡.
A. 排序大师
由于你是排序大师, 你经常被路过的游客刁难, 要求用一些奇怪的操作给序列排序.
由于你是远近闻名的排序大师, 邻国的排序萌新小 I 慕名前来拜访, 留下了一个长度为 $n\le 2000$ 的排列 $a_1, a_2 \cdots, a_n$, 并要求你用以下操作将排列升序排序:
- 定义 $a_{i \sim j} = {a_i, a_{i+1}, \cdots, a_j}$. 选定 $1 \le i \le j < k \le l \le n$, 交换 $a_{i \sim j}$ 和 $a_{k \sim l}$, 即交换过后序列变为 $a_{1 \sim i-1}, a_{k \sim l}, a_{j+1 \sim k-1}, a_{i \sim j}, a_{l+1 \sim n}$.
由于你是因精益求精而远近闻名的排序大师, 你需要给出一个排序方案最小化操作次数.
根本不会.
考虑分析下界, 因为这个是区间操作所以建图 $p_i+1\to p_{i+1}$, 前面带上 $0$, 这样构造是为了让最后是环 $n$ 个自环, 这样最后是 $n$ 个自环, 分析环数, 则发现一次操作是相当于进行两次子操作: 交换两个点的出边, 那么每次这个子操作可以增加/减少一个环, 于是每次操作可以改变环数 $2$, 下界有了, 开始构造.
找到最小的 $a_x$ 使得存在 $a_y>a_x, y<x$, 拿出最大的 $y$, 则 $a_x-1$ 一定在 $a_y$ 左边, $a_y+1$ 一定在 $a_x$ 后面, 就可以交换 $x-1, y$ 和 $x, y+1$
L 勇闯末日塔
在一个球面上有 $N$ 个点 $M$ 条弧, 保证弧无重边自环, 所有弧构成连通无向图, 且弧各不相交. 每条弧对应容量 $w_i$(需要根据弧长计算). 给出源 $s$ 和汇 $t$, 求删去恰好 $L$ 个点后从 $s$ 到 $t$ 最大流的最小值.
$3 \le N \le 1000, 1 \le L \le \min{8, N −2}$
弧各不相交, 则图是平面图, $M\le 3N-6$
然后最大流等于最小割等于对偶图最短路等于在球上找一个最小环让 $S, T$ 分别在两边.
为了在两边, 先bfs出一条 $S\to T$ 的路径, 然后要求找到的最小环经过 $S\to T$ 奇数次, 然后从一个点开始spfa dp, 状态要记录当前点和删了几个点, 而对于一个点转移次数是 $M$ 相关的, 总复杂度 $N^2L$
std8. 4k的怪物.
F.
大模拟
Summary
开局想了个假B浪费时间, 然后C式子推寄了浪费时间, E调了1. 5h+wa了好几发.
本来应该至少再过一个B的, 时间充足的话还有G只要仔细看了题就很有希望.
主要问题是自己码力太弱, 写完了调不对, 写代码犯智障错误.
% Mikefeng&Harry27182 %, 最后70名还是很好的.