2024.04.20NOIP模拟赛 #34
AT_arc095_d [ARC095F] Permutation Tree
给定一棵树 \(T\), 要求构造一个排列 \(p\)。
对于每一个 \(p_i\) ，找到最大的 \(j\) 使得 \(p_j<p_i\)，然后在 \(i,j\) 间连边。
问是否可以构造出与 \(T\) 同构的树。如果可以，则给出字典序最小的排列。
对于全部数据，\(n\leq 100,000\)。
CF1920F2 Smooth Sailing (Hard Version)
给你一张 \(n\times m\) 的地图，每个点是海
.，岛屿#或者火山v。保证岛屿和非岛屿均可以形成恰好一个四连通块且岛屿不与地图边界接壤，至少有一个岛屿点与一个火山点。
定义一条合法的路径为，从一个非岛屿的点 \(s\) 出发，每次向四联通的非岛屿点走一格，用航线包围岛屿一整圈后回到点 \(s\)。一条路径包围岛屿定义为，不存在一条从岛屿出发的八连通路径可以在不触及路径的前提下到达边界。一条路径的权值为途中经过的所有点到离其最近的火山的曼哈顿距离的最小值。
现有 \(q\) 次询问，每次给定一个点 \((x,y)\)，你需要求出从 \((x,y)\) 出发的合法路径的最大权值。
对于全部数据，\(3\leq n,m\leq 10^5,9\leq nm\leq3\times 10^5,q\leq 3\times 10^5\)。
CF878E Numbers on the blackboard
给出 \(n\) 个数字，每次询问一个区间\([l,r]\) ，对这个区间内部的点进行操作。
每次操作可以合并相邻两个数 \(x,y\)（且 \(x\) 在 \(y\) 之前），将它们变成 \(x+2y\) 对于每次询问输出当最后只剩下一个数字时，这个数字的最大值。
询问互相独立，答案对 \(10^9+7\) 取模。
对于全部数据，\(1\leq n,q\leq 10^5\)，\(-10^9\leq a_i\leq 10^9\)。
AT_arc141_f [ARC141F] Well-defined Abbreviation
标签：逆向,述说,10,路径,岛屿,飞奔而去,times,leq,cdots From： https://www.cnblogs.com/Alston-Wan/p/18147150给定 \(N\) 个由
A、B、C、D组成的串 \(S\)。
对一个串 \(T\) 定义如下操作：
\(•\) 选择一个 \(i\in[1,N]\)，找到一个 \((l,r)\) 使得 \(T[l\cdots r]=S_i\)；
\(•\) 把 \(T[l\cdots r]\) 从 \(T\) 中删除，并把首尾拼接起来。
不断重复以上操作知道任意 \(S_i\) 都不是 \(T\) 的子串。
我们称 \(T\) 是好的，当且仅当操作后 \(T\) 是唯一的。判断是否存在不好的串。
对于全部数据，\(1\leq N\leq 10^6\)，\(1\leq |S_i| \leq 2\times 10^6\)，\(|S_1|+|S_2|+\cdots+|S_N|\leq 2\ \times 10^6\)。