NFLS NOI 训练赛

mikefeng / 2023-05-03 / 原文

NOI2023训练赛12

门把手集合

每个点的价值是子树中与自身距离不超过 $k$ 的点权两两异或的平方和。

异或想到拆位，平方只与两个为有关，枚举两个位置，合并子节点权值，实时删去距离大于 $k$ 的节点，可以做到 $O(n\log^2 V)$。

本题卡空间，dsu on tree 做到时间复杂度 $O(n\log n\log^2 V)$。

武装直升机

dp 转移是取 $f$ 和极差的 max，区间极差随右端点增大而减小，有效 $f$ 值则增大，dp 转移点有单调性，可以单调队列维护区间 $\text{min,max}$ 和 $f$，时间复杂度 $O(n)$。

NOI2023训练赛13

线下单杀

正解是 $Z$ 函数预处理+排序，但是不会，用哈希拼接+二分找 lcp 判断字符串相对大小，复杂度最高是 $O(n\log^2 n)，充分发扬人类智慧，先判断是否相等，然后看前 $10$ 位是否相同，最后再二分，可以通过。

ps：一定要用 stable_sort。

四字名称

把胜负场数看做 $x,y$ 坐标：

\[a_{x,y}=\frac{\binom x {x+y}}{2^{x+y}}a_{0}{0} \]

答案合法要求对于任意 $a_{x,y} (x\in[0,n-1],y\in[0,m-1])$ 是 $2$ 的倍数。

由 kummer 定理可得，$\binom x {x+y}$ 的 $p$ 次幂数是 $\sum_{i=1}^\infty \lfloor\frac{x+y}{p^i}\rfloor-\lfloor\frac{x}{p^i}\rfloor-\lfloor\frac{y}{p^i}\rfloor$

所以只取右上角 $30\times 30$ 个点计算即可。

事实上数据只要取 $20\times 20$ 个点就行了。

原料运输

首先可以发现我们在计算的途中可以去掉 $v$，计算答案时再除掉并不会影响答案。

显然 $F$ 一定时 $W$ 越大越好，假设最大流总和是 $Z$，那么有 $F+W=Z$。

设 $f(W)=(\frac{Z-W}{v})^a W^{1-a}$，对其求导求函数最大值：

$\begin{alignedat}{3} f'(W)&=\frac{1}{v^a}(-a(Z-W)^{a-1}W^{1-a}+W^{-a}(Z-W)^a)\\ &=\frac{1}{v^a}(Z-W)^{a-1}W^{-a}((1-a)Z-W) \end{alignedat}$

可以得到如下结论：

$\begin{cases} f(W)单减&(W\le 0)\\ f(W)单增&(0<W\le (1-a)Z)\\ f(W)单减&((1-a)Z<W\le Z)\\ f(W)单增&(Z<W)\\ \end{cases}$

因此 $F=aZ,W=(1-a)Z$ 时答案最大，其实也可以三分最大值。

注意取值范围，跑一次 $F,W$ 最大流和一次 $F$ 最大流即可得到边的流量。

NOI2023训练赛14

延误列车

题意转化为找到一个时刻，使得 $a$ 大于 $0$ 和 $a$ 小于 $0$ 的列车分在 $d$ 两侧，发现只关注 $a>0$ 的列车的最右值和 $a<0$ 列车的最左值。

设 $f_i$ 表示 $i$ 时刻 $a>0$ 的列车的最右值，$g_i$ 表示 $i$ 时刻 $a<0$ 的列车的最左值，$f_i$ 下凸，$g_i$ 上凸，然后考场上降智了，只写了暴力。

一个 trick：把两个函数相减，要求 $g_i-f_i\ge 0$，得到的 $h_i=g_i-g_i$ 是上凸的，三分求函数最大值即可。

ps：开始还读错题了，加速度是$2a$ 不是 $a$，浪费了 $1h$。

串

因为 T1 时间太长没怎么看，只写了 $sub1,2$。

把文本串建出 Trie 树，可以简单递归求出每个点处的答案，并且预处理一个点按照 $c$ 一直跳会跳到哪里，修改的时候倍增跳祖先，然后找到新的点，直接输出答案即可。

NOI2023训练赛15

AVL树问题

设 $f_x$ 是最大深度为 $x$ 的点数，$g_x$ 是最大深度为 $x$ 时的答案手推前几项，发现 $f_x=f_{x-1}+f_{x-2}+1,g_x=\lfloor\frac{x-1}{2}\rfloor$。

压位高精+双指针计算，注意 $x=6$ 时要特判。

基因突变问题

区间取反和循环可以暴力，发现区间循环是 $O(n^3)$ 的，充分发扬人类智慧只取前 $20$个位置左右即可通过。

达尔文芯片问题

发现大问题可以归结为一个个的子问题，进行区间 dp，$f_{i,j}$ 可以由 $f_{i,k},f_{k+1,j}$ 转移过来。

复杂度过高，发现 $f_{i,j}$ 的转移点只会在 $f_{i+1,j},f_{i,j-1}$ 的转移点之间，可以通过数据。