ABC255

ABC255

• A

简单的模拟，输出 $A_{r,c}$，$\Theta(1)$.

• B

神 Statement

题意简述，平面直角坐标系上有 $n$ 个点，以其中已知的 $k$ 个点为圆心画半径均为 $r$ 的圆，求 $r$ 的最小值使得所有点均不在圆外.

$n \leq 10^3$，时限 2s，考虑预处理这 $k$ 个点到 $n$ 个点距离的值，再考虑每个点到这 $k$ 个点距离最小值的最大值即可，$\Theta(n^2)$.

• C

一个有关等差数列的细节水题，但是许多翻译却很...

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \uparrow$ 上面吐槽翻译有点多，单独拿出来了

题目即求一个整数 $x$ 在数轴上到一个 初項 $A$ 、公差 $D$ 、項数 $N$ の等差数列 $S$ 首项为 $A$，公差为 $D$ 的 $N$ 项等差数列 $S$（其中公差可为 0，此时是常数列）中每个数距离的最小值

设末项为 $b$，

特殊情况1：常数列

$d=0$ 时，$|x-a|$

特殊情况2：公差为负

$d<0$ 时，$a\rightarrow b，a+n\times d\rightarrow a$，转变为正公差的

其他的分 3 类讨论：

1. $x>b$，直接 $x-b$

2. $x<a$，$a-x$

3. $a<x<b$，考虑同余，可凭感觉推出 $\min\{|x\bmod d-a\bmod d|,d-|x\bmod d-a\bmod d|\}$ 的式子

为啥这个式子是对的？以下是不严谨的证明

考虑一条数轴，$-a\bmod d$ 即将等差数列变为 $d$ 的倍数数列，$x\bmod d$ 使得其落入 $[0,d-1]$ 的区间中，则要么到原点最近（$|x\bmod d-a\bmod d|$），要么到 $d$ 表示的点最近（$d-|x\bmod d-a\bmod d|$）

时间复杂度 $\Theta(1)$，跑的飞快

• D

一道有趣的初一数学套分段函数的好题 @Purslane 却认为是模拟题/fn，给出题人一点尊重罢

大意即对于每一个 $x_i$，求数列 $A$ 中所有数与 $x_i$ 的差的绝对值之和

正解在初一叫零点分段法，在初二叫分段函数显然不能 $\Theta(n^2)$ 暴力，考虑绝对值的一些基础性质

本菜鸡一上来想到的是几何性质，放在数轴上搞，但不是很可行

其实就是先将 $A$ 从小到大排序，再考虑 $f(x)=\sum\limits_{i=1}^n|x-a_i|$ 如何拆绝对值的问题，考虑对整个区间进行分段，每段为 $[-\infin,a_1],[a_i,a_{i+1}](1\leq i\leq n-1),[a_n,+\infin]$，显然分完段后每段都是个一次函数，为了让式子好看点，不妨设段数从 0 开始

对于第 $i$ 段，共有 $i$ 个拆完绝对值后形如 $x-a$，有 $n-i$ 个形如 $a-x$，故 $f(x)$ 的斜率即 $i-(n-i)$

接下来考虑截距

题外话：我一上来还想通过每段区间左端点的纵坐标来表示直线（即点斜式），后来发现完全没必要，式子还巨丑，才改成截距

这里假设分段函数的每一段都是一个新的一次函数，设第 $i$ 段函数为 $f_i(x)$，则 $f_i(0)$ 即为截距，这里若采用通项公式表达又回到了 $\Theta(n^2)$，是我们不能容忍的，于是考虑递推式

我们发现对于每个 $f_i(x)$，它与 $f_{i-1}(x)$ 相比只是一个 $a_i-x$ 变成了 $x-a_i$，所以就可以得到 $f_i(0)=f_{i-1}(0)-2\times a_i$，$f_00=\sum\limits_{i=1}^ni$

最后一个小问题：咋找 $x$ 属于哪个段？

二分查找即可，找到之后答案即为 $k_i\times x+b_i$

$\Theta(n+q\log n)$

接下来的部分建议左转@Purslane 神的题解，因为本人赛时写到 D 就跑了 其实是太菜了不会，这些是赛后的描述

• E

大概就是从 $X$ 中选最大的子集 $A$ 使得对任意 $i\in[1,n-1]\cap\mathbb{Z}$ 都有 $a_i+a_{i+1}=s_i$

不妨试几个看看

$a_1+a_2=s_1\Rightarrow a_2=s_1-a_1$

$a_2+a_3=s_2\Rightarrow a_3=s_2-a_2=s_2-s_1+a_1$

$a_3+a_4=s_3\Rightarrow a_4=s_3-a_3=s_3-s_2+s_1-a_1$

不套娃了 扔个式子：

$a_i=\sum_{j=1}^{i-1}(-1)^{j+1}\times s_j+(-1)^{i+1}\times a_1$

所以只要找到最初的 $a_1$ 一切就解决了

然而通过暴力枚举 $a_1$，带到式子里逐一验证是否在 $X$ 内是个 $\Theta(m\times n^2)$ 的笨办法，但是 $\sum\limits_{j=1}^{i-1}(-1)^{j+1}\times s_j$ 是已知的啊，预处理一下就行了，所以就直接枚举 $a_1$，算出 $a_i$，拿 map 跑一下是否在序列里就行了，时间复杂度就是 $\Theta(nm\log nm)$

• F

这真的是数据结构入门题吧，还没 D 难，我逃了是真的亏了/dk

题意即给定前序遍历和中序遍历，确定树的形态

实在是太显然了，就大模拟嘛，初赛知识点

简单说一句吧，就是根据前序找根，通过中序划分，划分后搜索，碰到矛盾 $-1$

太屑了，史上最水 F，我都会

写了这题我的 perf 也不至于刚破 1k /ll/ll/ll

• G

博弈论，不会，留给大佬们填坑

• Ex

@Purslane 爆切了 Ex，膜拜一下

就是离散化一下 . 然后变成区间加区间覆盖的线段树 . 懒标记随便维护一下 .

吐槽：tree bears 有翻译成树熊（树袋熊）的，真的是生物带师

首先 N 是 $10^{18}$,这肯定不能忍

然后离散化,你就很喜悦的发现就是区间操作

不妨设 $d_i$ 表示 $i$ 最后一次修改时间.那么如果没有最后一次修改,我们很容易知道这个人收了多少果子

然而有最后一次修改,那么要减去 $\sum i \times b_i$

$i \times d_i$ 显然可以用线段树维护

讲的太好了直接引用吧，不想作过多阐释了，时间复杂度就是 $\Theta(q\log q)$

听说还有平衡树的解法？不太懂