2025.07.15 Day1 组队赛报告
提交情况（6 + 1）
赛题分析
C - Clamped Sequence 2 （补）
容易发现最优解一定可以调整为至少一个边界与某个 $a_i$ 相同的情况。因为固定一点，另一点在值域相邻的两个 $a$ 之间移动时距离与答案呈现一次函数，因此至少存在一个边界可调整至某个 $a$ 值上。
我们不妨假设在某个 $a$ 值上的边界是上边界，下边界同理。考虑此时上下界距离与答案的关系，发现呈现为一条由 $n$ 个线段组成的折线。
我们将以每个点作为某一边界组成的所有线段取出，共 $O(n ^ 2)$ 条线段，答案即为求所有线段的某一前缀最大值。
可以使用离线扫描线，或者使用在线李超树的方法维护这一答案。时间复杂度均为 $O(n ^ 2 \log n + q \log n)$。
G - Symmetry Intervals
签到题，暴力扫描区间，对于所有相同的连续段长度记为 $len_i$，求 $\sum \frac {len_i \times (len_i + 1)} 2$ 即可。
H - Symmetry Intervals 2
卡常题，这里我们队在暴力的基础上注意到瓶颈为最内层的一个 if，判定两个串对应位置是否相同。我们注意到在随机数据情况下 CPU 流水线分支预测命中率较低的情况下会带来极大的卡顿，为此我们将条件判断语句更换为了全运算语句的版本，即通过了此题。
I - Iron Bars Cutting
注意到可以使用区间 DP，设定状态 $f[l][r][lim]$ 代表若从 $a_l \sim a_r$ 开始切割，第一次切割的不平衡值为 $lim$，将这一段切割完成的最小代价。容易发现枚举切断点的过程即确定了 $lim$，而两个子区间上传的转移可以使用前缀最小值加上二分答案取得。
一个容易的实现是令 $f[l][r]$ 为一个 vector，存储 $lim$ 与值的二元组，便于实现且常数较小。
时间复杂度 $O(n ^ 3 \log n)$。
L - Numb Numbers
签到题，使用类似优先队列结构处理即可。
2025.07.17 Day2 个人赛报告
FudanXCPC-2025Summer-Personal-0716
提交情况（9 + 0）
赛题分析
A - Achromatic Number (Codeforces Gym 100431A)
发现问题即为给定 $n$，让找到一个最大的 $m$，使得在 $m$ 个点的完全图上存在一个长度正好为 $n$ 的回路能够通过每条边至少一次。
当 $m$ 为奇数时由于完全图中每个点的度数均为偶数，图中存在一个欧拉回路，长度为 $\frac {m \times (m - 1)} 2$；对于 $m$ 为偶数的情况，我们可以添加 $\frac m 2$ 条边，为每一个点增加一个度数，使得新图中存在一个欧拉回路，长度为 $\frac {m ^ 2} 2$。
由于 $n \le 1000$，先根据上述边数找出最大的满足条件的 $m$，暴力搜索找出欧拉回路后考虑添加一些额外的边使得回路长度能够增大到 $n$。
一个易于处理的方法时提前断开 $1$ 与 $2$ 之间的一条连边，对原图求欧拉路径，从 $1$ 开始，到 $2$ 结束。当我们还需要添加额外的点时可在末尾添加 $\to 3 \to 2 \to 3 \dots$。注意到当我们添加至少一个点后会破坏原有的一条 $1$ 与 $2$ 的连边。当 $m$ 为偶数时并不影响，因为这两点间还存在另一重边已访问；当 $m$ 为奇数时，若需要添加的额外点数大于一，则可以通过先在末尾添加 $1$ 再添加上述点完成合法构造，否则该 $m$ 不能得出合法构造，需要使用 $m - 1$ 进行构造。
B - Binary Search (Codeforces Gym 100431B)
由于 $n \le 1000$，我们考虑先枚举最终答案位置 $x$。模拟一遍二分过程，在二分过程可以通过 $x$ 与 $l,~r$ 的位置关系得出 $a[m]$ 与 $a[x]$ 的大小关系。我们记录这一过程中要求小于 $a[x]$ 的数量 $cnt_1$ 和要求大于 $a[x]$ 的数量 $cnt_2$，其他节点权值任意。
枚举 $a[x]$，此时答案即为 $a[x] ^ {cnt_1} \times (n - a[x]) ^ {cnt_2} \times n ^ {n - cnt_1 - cnt_2 - 1}$。
需要使用高精度，可用 Python 进行实现。
一个可优化之处是上式最后一项指数中 $cnt_1 + cnt_2 + 1 \le O(\log n)$。可取一常数 $p = \log n + O(1)$，在计算过程中替代指数中的 $n$ 进行运算。求和完成后再为答案乘上 $n ^ {n - p}$。可以节省一些运算。
D - Bubble Sort (Codeforces Gym 100431D)
模拟即可，从右向左从排序完成的有序序列反推至排序前的序列。
F - Permutations with Monotonic Segments (Codeforces Gym 100431F)
考虑令 $f[i][j]$ 代表完成了前 $\sum_{x = 1} ^i a_x$ 个数的排列构造，其中最后一个元素位于排列中的值 $j$。转移考虑将 $a_{i + 1}$ 个数插入其中。转移时枚举 $k$ 表示新的最后的元素的位置，计算时可以使用简单容斥使用总插入方法减去不合法方法（全部 $< j$）得到合法方法进行转移。
G - Persistent Queue (Codeforces Gym 100431G)
可先忽略所有的弹出操作，维护队列尾节点，所有的插入操作可持久化后可形成一个树状结构。
对该结构标注 DFS 序，重新遍历所有操作，维护队列头节点，弹出时向下移动到尾节点对应子树即可。
H - Sea Port (Codeforces Gym 100431H)
模拟题，阅读后可发现货轮和吊车的使用优先级都为一个 $\{ Time,~ID \}$ 二元组。对于货轮这一时间代表其入港时间，对于吊车则代表其上一个任务的完成时间。为此我们可以使用 priority_queue 或者 set 构建所有存储货轮和吊车的结构。
进一步阅读可以发现，对于每一个时刻，我们先取出所有此时入港的货轮，和此时结束上一任务的吊车。根据题面结构，我们发现货轮和吊车均有一个“立即处理”->“缓存”的过程，对于货轮来说为停靠码头（dock），对于吊车来说是保持闲置（idle）。而对于同一时刻出现的货轮和吊车，我们发现吊车实际拥有主动权选择此时入港的货轮，而货轮只能够选择更早空闲（idle）的吊车。
因此我们先按照 $ID$ 升序依次枚举所有货轮，检查是否存在可匹配的吊车，若无则加入 dock；随后再按照 $ID$ 升序依次枚举吊车，此时也可以匹配刚加入的货轮，对于每一吊车枚举其所有可搬运的货轮的最优者，若无则加入 idle。
对于时间轴维护，可以使用一个 priority_queue 以 $\{ Time,~Event \}$ 记录事件二元组。在优先队列非空的情况下，每次取出所有与最早任务时间相同的所有任务，解析后加入货轮和吊车的单独队列，根据上文的描述进行处理即可。
对于 dock 和 idle 均可使用 $C$ 个 priority_queue 或 set 维护上文提及的 $\{ Time, ID \}$ 信息，实时维护每一货物种类对应的所有可用货轮和吊车。
J - Uniformly Distributed (AtCoder arc120_b)
签到题，发现每一左下—右上对角线均需要为同一颜色。
K - Bracket Score 2 (AtCoder arc120_d)
首先发现对于每一对括号对应的位置，可以不限制其差取绝对值。只需要其中一个提供正贡献，另一个提供负贡献即可。
考虑极优情况，即最大的 $n$ 个位置提供正贡献，另外最小的 $n$ 个位置提供负贡献。容易发现对这一情况存在一正一负的匹配构造。
记 $f_i$ 当 $a_i$ 提供正贡献为 $+1$，当 $a_i$ 提供负贡献为 $-1$。同时记 $pre_i = \sum_{x = 1} ^i f_i$。
对于位置 $i$，当 $a_i$ 提供负贡献且 $f_{i - 1} \le 0$，即左侧还有若干失配负贡献节点，令 $s_i = $ (，否则代表左侧还有若干失配正贡献节点，令 $s_i = $ )。当 $a_i$ 提供正贡献时同理。
L - 1D Party (AtCoder arc120_e)
每一个人需要在整个操作时间轴上先后完成与它两侧的人的相遇。因此表现总是为先向一侧的邻居方向移动，完成与它的相遇后折返向另一侧的邻居移动。
考虑将这一折返行为去除，而视作它与它的邻居互相穿过，继续保持原有方向而没有各自掉头。同时它与它的邻居互换下一任务，即与对方的另一边的邻居相遇。
考虑原有的“任意相邻两人均相遇”条件，即为对于任意相邻的两人的行动路径存在相交。在这里我们假设所有人的相对位置并没有改变，则相邻两条路径存在相交的条件可以转化为，所有 $n$ 条路径在 $x - t$ 图像上连通。容易证明这两个条件的等效性。
结合上述可将相遇视作穿过的方法，可将上文中所有人相对位置没有改变的假设去除。也就是每个人任意走一条路径，所有的路径最终完成连通即可。
容易想到，每个人选择一个 $+1$ 或者 $-1$ 的速率并且在全局保持移动是一个不劣的选择。我们需要在此情况下使得所有 $n$ 条射线连通。
我们首先进行二分答案，二分最终需要的时间 $K$。则每一条射线为 $a_i \to a_i \pm K$。二分答案的一个容易想到的检查方法是使用贪心。对于 $a_1$，其射线一定向右。随后我们找出一个最大的 $x$，使得 $a_1 + K \ge a_x - K$，我们令此位置射线向左，完成 $a_1 \sim a_x$ 的连通，随后我们使用 $a_{x - 1}$ 向右作出射线，并重复找到下一个最大的 $x$，重复贪心检查是否能够完整覆盖 $a_1 \sim a_n$。
但是容易发现贪心存在的一个问题，此处最右的位置 $a_x$ 射线向左，实际上并不能对答案产生贡献，而是 $a_{x - 1}$ 对答案产生贡献。在此情况下我们取最大的 $x$ 是不一定正确的，比如在一些情况下我们可能希望 $a_x$ 的射线向右，帮助我们拥有一个更加向右的射线位置。而且容易找出一些反例使得可以通过变换构造使得 $a_x$ 向右。
可以改用动态规划，考虑状态 $f_i$ 代表 $a_1 \sim a_i$ 已连通，此时这一块内向右的射线的最大终点位置。在此状态下 $i$ 的射线一定向左。$f_i$ 可从 $f_{i - 1}$ 转移而来，只要 $f_{i - 1} \ge a_i - K$，即此位置向左可以与左侧块连通即可使用 $f_{i - 1}$ 更新 $f_i$ 的值。
另外 $f_i$ 还可以从 $f_{i - 2}$ 转移而来，对应刚才贪心的优秀策略，即通过 $i$ 向左侧引出射线连通 $1 \sim i$，使用 $i - 1$ 向右引出射线的答案 $a_{i - 1} + K$ 更新 $f_i$。
容易理解这一动态规划方法的正确性，并且可避免先前的问题。时间复杂度 $O(n \log A)$。
解题时没有注意到存在 $A_i$ 单增的性质。对于 $A_i$ 无序的情况，注意每一个极值点一定会保持向内测移动。因此可对每一个连续极长单调段进行独立检查。
2025.07.18 Day3 组队赛报告
提交情况（9 + 1）
赛题分析
1002 - 夜世界
不难发现对于一个区间，从左侧进入时的金币与右侧离开时的金币的对应关系呈现为两个一次函数拼接的结果。具体地，可以使用两个参数 $u$ 和 $\delta$ 来描述这一区间：任何从左侧进入的金币数 $x$ 离开时会变为 $\max(u,~x) + \delta$。
使用线段树维护上述信息即可。由于有回退操作，额外支持可持久化即可。对于每次查询，以每个给定点作为断点，从左向右模拟经过每个连续段即可。
1006 - 景区建设
注意到传送器的造价远高于其他代价，因此我们首先需要最小化传送器的数量。我们先从起点做一次 FloodFill，随后按照 $a$ 从大到小的顺序枚举每一个位置，若未访问则它为一个极大值，建立一个传送器并且执行一次 FloodFill 即可。
连接各传送器至连通则为一个最小生成树问题。观察后发现传送线路的价格中 $| a_x - a_y |$ 一项起决定性作用，因为其相当大的系数和 $a$ 互不相同的限制。也就是说，只需要将所有建立传送器的位置按照 $a$ 排序，依次连接排序后相邻两个传送器即可。
1008 - mod 2 （补）
注意到计算 $b$ 的数量可以使用两部分相乘得出：
- 无序可重集满足 $even$ 结果正确的集合数量。
- 无序可重集重排为数列 $b$ 的方案数。
注意到第二部分答案在大部分时候均为偶数。记可重集中各数值出现的次数为 $cnt_v$，则答案应为 $\binom k {cnt_1,~cnt_2,\dots,cnt_c}$。由 Lucas 定理与 $\sum_i cnt_i = k$ 可得，此值为奇数当且仅当在二进制表示上各个 $cnt_i$ 均为 $k$ 的子集，且各不相交。换言之，将 $k$ 表示为 $k = \sum_i 2^{x_i}$，我们需要将集合 $\{ x_i \}$ 中的各个元素分至 $c$ 个不为空的集合中，其中 $c$ 为此无序可重集的权值种类数。此方案数为第二类斯特林数。
再考虑第一部分计算。我们先考虑 $k$ 为偶数的情况，注意到按照上述方式得到的 $cnt_i$ 均为偶数，且各不相同。令 $c$ 等于 $odd(a[L, R])$ 的长度即可，完成划分后根据 $cnt_i$ 的大小依次赋予 $odd$ 中对应值即可。此时答案即为上述第二类斯特林数。
对于 $k$ 是奇数的情况，我们得到的一个 $cnt_i$ 为奇数，其余均为偶数，并且仍互不相同。令 $c$ 等于 $odd$ 的长度加一，完成划分后将最低位所在 $cnt_i$ 拿出，分以一个与其他数值不同的数值，其余 $cnt_i$ 根据 $k$ 偶数时的策略划分即可。此时的答案为第二类斯特林数乘上取一不同值的方案数。
也就是说，我们现在只需要知道 $odd(a[L, R])$，就可以 $O(1)$ 地计算出最终答案。另外我们注意到，若 $odd$ 的项数多余 $\log V$，上述第二类斯特林数无法完成划分，答案必然为零，也就是说我们只需要在项数小于 $\log V$ 的情况下求出 $odd$ 即可。
考虑使用线段树维护区间哈希值，线段树下标为 $a_i$，记录当前每个权值出现的次数为奇数或是偶数。这里可以为每一个 $a_i$ 随机一个哈希值，然后线段树维护区间异或哈希值。
随后对线段树进行可持久化，第 $i$ 个版本记录 $a_1 \sim a_i$ 的统计哈希信息。当我们需要找出 $[L,~R]$ 中所有出现次数奇数的数值时，我们同时枚举 $L - 1$ 和 $R$ 两个版本的对应节点，若哈希值不同则暴力递归查找。最终在 $\log V$ 次暴力递归中找出 $odd$ 的结果。
我们注意到我们只关心 $odd$ 的项数，即可完成最终答案的计算。但是一个特殊情况是，我们还需要找出 $odd$ 中的最大值，检查该值是否大于 $V$，否则显然无法构造对应 $b$。
时间复杂度 $O(n \log a + q \log n \log V)$。
1009 - 子序列
签到题。
按照从小到大枚举每一个数值，同时使用双指针维护大于此值的排列中最左和最右的元素位置。
我们找出当前数值在排列中的下标，令他为子序列中较小的一端，双指针中的某一个指针作为其较大的一段，其中间的元素则可使用树状数组维护区间计数。
2025.07.21 Day4 个人赛报告
提交情况（9 + 1）
赛题分析
A - Martadella Strikes Again
计算圆面积大小即可。
B - Amer and Graphs
对每一对无序对随机一个哈希值，用所有边的哈希值之和代表一个图的哈希值，进行统计即可。
C - Help Shahhoud
在每一次必须要转换交换方向时计数即可。
E - Floods
对于每个位置，维护其前缀最大值和后缀最大值，两者较小者即为此处的水深。对于相邻两个位置，计算其横坐标之间梯形或是三角形的面积即可。
F - Random Sort
相同值对应的位置没有顺序要求，其阶乘之乘积即为答案。
G - Weird Requirements （补）
检查每个数值均满足基本要求，即为 gcd 的倍数和 lcm 的因数，不符合要求者必须操作。
只需要有两个需要操作的数值，即可通过将他们分别赋值为 $X$ 和 $Y$ 完成构造。对于至少两个位置需要操作的情况同理。
对于只修改一个数值即使得整个序列满足条件的情况，我们考虑当前序列在 gcd 上需要合法，需要额外增加哪些因数的最小指数，和 lcm 需要合法需要增加哪些因数的最大指数。这两个因数集合若相交，则必然需要至少两个操作才能合法，否则可以于一个位置进行修改，同时满足这两者的要求。
I - Ildar Yalalov
对于堆数为奇数的情况，可以观察到不管执行哪种操作均会使得石头总数奇偶性发生变换，因此总数为奇数时先手必胜，偶数时后手必胜。
对于堆数为偶数的情况，可以观察各堆的石子最小值。注意到所有堆的石子数均为最小值时对应总堆数为偶数的状态，这一状态可能不得不选择将最小值减一的操作，除此之外的状态均可以选择令最小值减一，奇偶性不变，或者是最小值不变，奇偶性改变的两种选择。最后可以发现最小石头数为奇数时总是先手必胜，当最小石头数为偶数时石头总数为奇数时先手胜，否则后手胜。
J - Saeed and Folan
注意到值域范围小，暴力模拟即可。
K - Another Shortest Path Problem
基环树上求两点最短路。
L - V–o_o–V
在树上对权重数组进行一次差分，树剖后依次对每个点至根节点的路径进行标记增加权重差分数组，和求总和即可。使用线段树维护即可。
2025.07.22 Day5 组队赛报告
提交情况
赛题分析
A - Ad-hoc Newbie
构造，注意利用性质 $1 \le f_i \le i$。
考虑能否令最终构造矩阵能够沿主对角线对称，这样可以令横向与纵向的限制同样对称。在这样的条件下，我们考虑仅由 $A_{i, 1},~A_{i, 2},\dots,~A_{i, i}$ 构造出对应 mex，且使得 $\forall x > i,~A_{x, i} \neq f_i$。
可以发现这样是可以完成构造的，在构造 $A_{i, i}$ 左侧数值时，注意到每个位置均有限制除了 $A_{i, i}$，也就是说始终可以留有一个位置可以填充当前位置无法填充的值，而当前位置无法填充得值又仅有一个：$A_{i, j} \neq f_j$，且填充的这些数值可以互不相同，因此构造显然存在。
因此可以将 $0,~1,\dots,~f_i - 1$ 放入一个集合。若数值数量不足，可用 $f_i + 1,~f_i + 2,\dots$ 填充。随后从左往右遍历 $A_{i, i}$ 左侧的每个位置，填入任意集合内除当前位置不可填充数值之外的数值。以此即完成构造。
B - Bitwise Puzzle
当 $a = b = 0$ 且 $c \neq 0$ 时无解，容易发现其他位置均有解。
考虑在步数无限制的情况下我们会如何完成此任务。我们可以考虑类似线性基的构造方法。我们先将 $a$ 的最高位通过 1 操作提升至 $30$，随后按需要执行一次 4 操作令 $b$ 的最高位也提升至 $30$。若此时 $a$ 中位于 $b$ 最高位的数值不正确，则执行一次 3 操作令 $a$ 异或 $b$，翻转此位。随后执行一次 2 操作将 $b$ 最高位下移一位。反复执行上述操作直至 $b = 0$，此时一定有 $a = c$。最后执行一次 4 操作，令 $b = c$ 即可。
考虑在 64 步限制下如何执行此操作。我们可以先将 $a$ 与 $b$ 的最高位对齐。随后我们进行 $a$ 最高位的检查，并按需要执行 3 操作与 $b$ 异或。完成检查后我们判断，若 $a$ 初始最高位尚未达到 $30$，则执行一次 1 操作提高最高位，相当于 $b$ 相对于 $a$ 仍下移了一位；若 $a$ 初始最高位已达到 $30$，执行 2 操作令 $b$ 最高位直接下移即可。
初始的最高位对其花费 $1$ 步，中间的检查操作将执行 $31$ 次，移动操作执行 $31$ 次，最后令 $b = a$ 花费 $1$ 步，最坏情况下步数正好为限制 $64$ 步。
C - Capella （补）
对限制经过观察后我们最终可以发现其等效于：选择一个最长的区间，满足区间长度为奇数且区间内字符集大小为奇数。
我们先考虑全局区间 $[1,~n]$，若全局字符集为奇数，且 $n$ 为奇数，则答案即为 $n$。
若全局字符集为奇数，但是 $n$ 为偶数，我们考虑将区间缩短为长度 $n - 1$。但是此时需要注意缩短区间可能遇到删除节点在区间内仅出现一次，导致字符集奇偶性发生变化的情况。我们考虑找出一个长度为 $c_l$ 的前缀，使得该前缀内每个字符在区间内仅出现一次，再找出一个长度为 $c_r$ 的后缀，也使得该后缀内每个字符在区间内仅出现一次。注意到区间长度为偶数，但是字符集为奇数，因此至少有一个字符在区间内出现了两次，因此前后缀并不会相交。可以发现前后缀内的元素在被排出区间时会使得区间长度和字符集大小的奇偶性同时翻转，因此我们必须要额外排除前后缀之间的一个元素。因此这一场景下的答案为 $n - \min(c_l,~c_r) - 1$。若该长度为偶数，需额外减一。
我们再考虑全局字符集为偶数的情况，一个贪心的想法是我们可以对于每一个字符，维护全局该字符相邻出现位置距离的最大值。我们可以对于所有字符的该最大值找出最大值，设这两个相邻位置为 $[l,~r]$，则区间 $[l + 1,~r - 1]$ 内字符集大小一定为奇数。因为该区间长度最大，并没有其他区间包含该区间，因此不会有其他字符在区间内不出现。若此时得到的区间长度为奇数，则答案即为该值，否则会遇到与上文相似的问题：当我们尝试缩短区间时可能导致字符集奇偶性的改变。
考虑我们若尝试从 $[l + 1,~r - 1]$ 中排出 $S_{l + 1}$。若该位置在区间内出现多次，则直接排出该位置，然后区间即为答案；否则下一个满足 $S_x = S_{l + 1}$ 的位置一定有 $x \ge r$，等号成立当且仅当 $x = r = n + 1$。我们先考虑 $r \le n$，则 $x > r$ 一定成立。但是 $x - (l + 1) \le r - l$，因为原区间为一最长区间。因此可以发现成立 $x = r + 1$，即 $S_{l + 1} = S_{r + 1}$。我们发现 $[l + 1,~r + 1]$ 与 $[l,~r]$ 相似，也为全局长度为最大值的相邻两个位置。进一步，对于任意 $x$，均有 $[x,~x + (r - l)]$ 满足该性质。若不满足该条件，则说明在 $l$ 移动至 $x$ 时能够遇到某一位置在区间内出现多次且可排出，答案即为 $r - l - 2$。
考虑满足该情况时，我们必须移除一个在 $l$ 和 $r$ 的平移过程中均没有被访问到的位置。因为在平移过程中被访问到的所有位置，在区间内均没有其他相同元素，移除仍会使得区间长度和字符集大小的奇偶性同时改变，无法使得更新后的区间满足条件。我们发现可以继续使用上文字符集为奇数，长度为偶数时的分析方法。该方法需要区间内前后缀唯一出现的元素的长度较小值尽量小。因此在当前情况中，我们可以取 $[1,~1 + (r - l)]$ 与 $[n - (r - l), n]$ 两个区间进行该分析，取较小值即可。因为这两个区间在所有合法的区间中能够满足前后缀长度较短值尽可能短。
暴力平移过程中由于元素均唯一，平移总数不超过 $|\Sigma|$。配合恰当的实现，该题总复杂度可以为 $n \log n + q (|\Sigma| + \log n)$。
D - Distant Control
我们发现若全局存在至少一个长度为 $a$ 的连续开机位置。在所有机器人没有全部开机的情况下，则我们可以找到一个长度为 $a$ 的连续开机位置且其与一个关机位置相邻。我们将这 $a$ 个连续开机位置关机，便能够形成一个长度至少为 $a + 1$ 的连续关机位置，再将他们开启。即可完成将相邻位置变为开启状态的目的，以此类推可将所有位置全部开机。
类似的，若存在连续 $a + 1$ 个关机位置，我们也可以通过执行一次操作将他们均变为开机，随后执行上述操作。
因此全局只需要存在一个可操作位置，所有机器人均可开机。否则答案即为初始开机数。
F - Flower
签到题。
2025.07.24 Day6 个人赛报告
提交情况（8 + 1）
赛题分析
A - Today's Word
注意到当长度超过 $2m$ 时该后缀每次操作后仅会发生全局偏移的情况，暴力模拟前几次即可。
E - LCM Plus GCD
对 $x$ 进行质因数分解，得到 LCM 和 GCD。随后可对 LCM 和 GCD 同时应用容斥，计算出 LCM 与 GCD 恰好为对应值的方案。
F - Timaeus
使用动态规划线性递推概率即可，需注意 $B = 1$ 时自我转移的情况。
G - Moving Boxes （补）
注意到最后移动的路径形成一个回路，因此起点的具体位置并不重要，只需要构建回路即可。
考虑对于每一个 $i$，讨论数轴上 $i \sim i + 1$ 的这一个长度为一的段被经过了多少次。注意到最终构造的回路在这一个段上向左经过的次数与向右经过的次数一定相同，设 $a_i$ 为该位置向左经过的次数与向右经过的次数的较大值，则回路在此处经过的次数一定至少为 $a_i$。设最终回路在这个段上的经过次数为 $b_i \ge a_i$。
容易发现，在位置 $i$ 处掉头的次数为 $|b_{i - 1} - b_i|$。当前回路需要花费的总时间为 $2 \sum b_i + C \sum |b_{i - 1} - b_i|$。
容易发现若存在一个长度不超过 $C$ 的段，且段的两端的 $b$ 值均小于外侧相邻的位置，则将此段的 $b$ 全部加一，能够通过减少两次掉头并增加一些路程完成总时间的减少。最终从左向右线性扫描并用一个单调栈维护相邻段，贪心提升所有满足要求的段即可。
H - Neil's Machine
贪心即可。
I - Elevator
签到题。
J - Similarity (Easy Version)
此题数据范围小，暴力查找即可。
K - Similarity (Hard Version)
此处可以使用一个这样的构造。由于 $n \le 300 < \frac {26 \times 25} 2$，我们可以为每个 $i$ 分配两个不同的字符 $a_i$ 与 $b_i$，且任意两个 $i$ 的字符对均不相同。
对于每一个 $i$，我们可以这样构造字符串：$m$ 个 $a_i$ 字符，随后一个 $b_i$ 字符，随后 $m$ 个 $a_i$ 字符，再一个 $b_i$ 字符，如此类推。
特判 $m = 0$ 与 $m = k$ 的情况，其余情况如此构造即可。
L - Architect
考虑较为模拟的情况我们可以如何做，我们可以创建一个三维差分数组，添加每一个长方体时我们修改差分数组中的八个点位即可。最终我们对整个差分数组进行三维前缀和，即可得到每个位置被覆盖的次数。我们还可以将初始的大区间以负一的贡献加入差分数组，最终我们要求差分数组前缀和完后每个位置均为零。
进一步的，我们发现差分数组进行前缀和后得到的数组均为零，等价于差分数组本身每个位置均为零。使用 map 维护差分数组即可，只需要检查最后 map 中的每个位置的权值为零即可。
2025.07.25 Day7 组队赛报告
提交情况（8 + 1）
赛题分析
1004 - 三带一 （补）
假设我们将第 $i$ 个花色分为了 $A_i$ 个“三”，$B_i$ 个“一”。设当前一共有 $k$ 个三带一，我们发现只要满足：$\forall i,~A_i + B_i \le k$，且 $\sum A_i = \sum B_i = k$ 即可将他们进行配对以满足条件。
我们可以二分答案 $k$，随后对于每个 $i$，先尽可能多的分出“三”，再在剩余的部分尽可能多地分出“一”。完成后我们可以考虑将一些多余的“三”转化为“一”。我们发现它可以有三种转化：一个“三”可以变为三个“一”，或者两个，或者一个，取决于当前 $k - A_i - B_i$ 的余量。我们可以每次按照余量排序所有花色，优先转化余量较多的花色的“三”。这样即可完成最优情况下的构造。
1007 - 性质不同的数字
注意到只要各个位置上覆盖的线段的集合不同即可。我们可以为每个线段随机一个哈希值，并记录各个线段端点上的集合哈希值，找出全局出现的不同哈希值的数量即可。
1008 - 01 环
输入时我们先将所有偶数位的比特翻转，我们的目标是使得所有比特变为零或者变为一。
对于每一个极长的错误比特段，操作它变为正确的最小次数是 $\lceil \frac {len} 2 \rceil$。累加即可。
Comments | NOTHING