NOIP+？准省选难度？已经到了能力的边缘么？
但有点奇怪的是，这三道题的思考方向全部正确，T1 甚至只差临门一脚了；可惜部分分给得不那么让人舒服。
另外，这种“为了卡常而卡常”的时间限制着实令人不适；尤其是当 CWOI 的评测机本身配置落后的情况下。不过这也反过来使得我重新开始关注更底层的常数优化。
分类： 比赛日志
-
MOCK NOIP 20221117 日志
T1 的 Hack 数据提醒我，尽管时间复杂度没有变化，但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。
T2 没有认真读题，忽略了“恰执行一次”的要求。
T3 里面没有使用自己熟悉的存边方式，时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。
简单题解
A – 跳棋
从 $(x,y)$ 跨步跳能够跳到 $(x\pm 2,y),(x,y\pm 2)$，以及 $(x+k,y+k),k=\pm 2$。可以发现 $x,y$ 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块，在这些连通块上 BFS 即可。
若采用
std::map存储，时间复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)$。需要采纳“避免遍历不存在的连通块”之类的优化。 （更多…） -
MOCK NOIP 20221112 日志
仍然是中规中矩的一场模拟赛。前两题正解，第三题暴力，第四题不会。
简略题解
A – 激光
考虑是否有两条及以上双向连边，若是则无解，若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。
B – 碰撞
这类数轴上带标号小球相撞的题目都有一个经典套路：两球相撞调转方向时，我们不认为是球本身转向，而认为两球仍然保持原方向运动，而其编号交换。 （更多…）
-
MOCK ??? 20221012 日志
$4$ 道题全部只会暴力。还不如直接发下来当练习做呢，省得在场上罚坐三小时浪费时间。
简略题解
A – 神灵庙
观察发现：
- 当树的形态确定时，我们总是将权值更大的节点安插到深度更小的叶子上。可以将 $a$ 降序排序后逐层填写。
- 一个节点只可能有 $0$ 个或者 $2$ 个儿子。如果只有 $1$ 个儿子，显然可将该节点删除而整棵子树全部向上平移。
设 $f(d,i,c_1,c_2)$ 表示“现在位于第 $d$ 层（此处“层”指的是节点实际深度）。已经填写好了 $a_1,a_2,\cdots,a_i$，且第 $d$ 层共 $c_1$ 个空置（非叶子）节点，第 $d-1$ 层有 $c_2$ 个此类节点”。那么两层的每一空置节点，均会有一个第 $d+1$ 层的儿子。枚举“下一层要填写 $k$ 个元素”，有转移
$$f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1)$$ （更多…） -
MOCK NOIP 20221110 日志
fread专场。$4$ 道题里面 $3$ 道适合用快读。简略题解
A – 远征
由题意可得 $a_i$ 应为目前战斗力 $x$ 的子集。这一迭代过程最多只有 $10$ 轮（$a_i,x\leq 1023=2^{10}-1$），于是处理出跳转指针暴力模拟即可。
复杂度 $\newcommand\bigO{\operatorname{O}}\bigO(1024n)$。
B – 传送
观察样例可以感知到答案应当只有 $-1,0,1,2$ 四种取值。根据题意，在原图 $G$ 上若有一条简单路径（在迭代加边的过程中绕回原点不符和要求） $x\rightarrow\cdots\rightarrow y$，满足其长度 $l\equiv 1\pmod{2}$，那么 $G’$ 上一定存在边 $(x,y)$。
所以若 $x,y$ 不在同一连通块中，无解；若存在满足题意的路径，答案即为 $1$；否则必须经某个点中转，答案为 $2$。
-
MOCK NOIP 20221108 日志
中规中矩的一场模拟赛。
T1 写得实在是太久了……这也是没办法的事情——如果不对转移作压缩优化就没办法过。
T2 有我喜欢的
马拉车Manacher 算法，是印象里第二次在模拟赛应用。然后就没时间了。后两题仍然只有暴力分，但最近频繁遇到跟凸包和线性函数相关的题目，这使我发现 T3 跟它相关。在最后一点时间里实现了构建凸包的函数。代码本身没问题，但思路是错误的。
简略题解
A – 石蒜反冲
这好像是很早以前的译名了。现在它叫《莉可丽丝》。遇见多模式串匹配，自然想到自动机上 DP。但我们发现题目中给定的两个串
sakanachinanago在任何一个文本串中最多只能匹配其中一个，且匹配位置唯一。于是简单计数 DP 转移，记录当前二者匹配数之差与目前匹配位置即可。一些
不应用就过不了的优化：- 二者数量之差可只记录到 $\frac{n}{15}$。$15$ 是两个串的总长度。
- 转移时对于
?scao还有其他字符分类讨论，保证单次转移复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(1)$。
时间复杂度 $\bigO(n^2)$。 （更多…）
-
MOCK NOIP 20221020 日志
感冒咳嗽，头实在是太晕了，打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。
一句话题解
A – 破坏
简单的 $\newcommand{\bigO}{\operatorname{O}}\bigO(m2^k)$ DP。记录每个节点的路径数奇偶性考虑是否翻转即可。
B – 共识
用
std::bitset写的暴力大家都会。不过如果你胆子大些，不判断是否为部分分数据范围直接提交（加入随机化的）暴力，将喜提 $\text{100 pts}$。命题：现有一个由 $2n$ 个元素构成的集合，保证 $2\mid n$。有 $n+1$ 个大小恰为 $n$ 的子集 $S_1,\cdots,S_{n+1}$。则至少存在 $n/2$ 对无序对 $(i,j),i\neq j, i,j\in[1,n+1]$，使得 $|S_i\cap S_j|\geq n/2$。
证明（引自宋佳兴学长）：记元素 $p,p\in\{1,\cdots,2n\}$ 在所有子集中出现的次数为 $\newcommand{\cnt}{\operatorname{cnt}}\cnt(p)$。则显然有“所有子集两两之交的大小”
$$\sum_{i=1}^{n}\sum_{j=i+1}^{n+1}|S_i\cap S_j|=\sum_{p=1}^{2n}\binom{\cnt(p)}{2}$$考虑计算该式最小为何。不妨先考虑 $\binom{a}{b}+\binom{n-a}{b}$ 在何时取最小值。
引理：$\binom{a}{b}+\binom{n-a}{b}, b\leq n, a\geq 0, a\leq n$ 在 $a=\lfloor n/2\rfloor$ 处取最小值。
-
MOCK NOIP 20221018 日志
堪堪能接受的一场。前两题一个半小时左右做完，后两题实在没什么思路，打完所有可能的暴力之后跑路了。
他们告诉我题目名称可以从上到下连起来读。一句话题解A – （种）菜
可以发现，假若同时有 $\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}$ 和 $a_{i+1},a_{i+2}$ 都可合并，则取 $a_i, a_{i+2}$ 中任意一个合并之后，质因数集合总是变为原来的超集，另外一项仍可合并。
故而可以贪心合并所有合法的邻项，最终检查是否仅剩一项即可。注意到 $[1,700]$ 仅含 $125$ 个质因数，故可以用
std::bitset保存每一项的质因子集合。复杂度 $O(\frac{128n}{\omega})$。赛时竟然还开了数组保存每个质因子的实际指数！（更多…） -
MOCK NOIP 20221015 日志
恕我语文不好，实在不晓得用何种词汇来描述看到下文的感受：
此比赛为正常的提高组难度，
甚至可以用来作为普及组模拟赛。
请选手 AK 后不要大声喧哗，以免影响他人 AK。尤其是这套题的出题人是张隽铠的情况下。当然，OI 圈风气本就如此，我也不好过多评价。No comment.
T1 还算顺利，半小时左右搞定。T2 是大分类讨论，足够恶心人，但好在有相当可观的可以通过暴力与观察拿到的部分分。T3 猜测与线性基相关，但没有相应知识储备，暴力跑路。
T4 就……反正出题人开心就好。到现在都没人改出来。
一句话题解
A – 序列
依次往某个子序列中添加元素。则添加的元素必然成为新的最大值/最小值之一，否则违背题意。
于是枚举子序列首元素，将以其开头的严格上升子序列数与严格下降子序列数相乘即可。使用树状数组转移即可。复杂度 $\operatorname{O}(n \log n)$。 （更多…）
