Source: OCPC 2025 Summer, Day 5: Trademark Contest
A - Canonical Palindromes
首先原区间必须是回文的，否则无解。我们只考察右半部分，相当于求给一个区间降序排序需要多少次插入排序，发现每次插入都至多使序列的 LDS 长度增加 ，故答案为原区间长度的一半减去右半部分 LDS 长度。
区间 LDS 是困难的，尝试从原区间回文这个性质入手，有个经典的结论是本质不同回文串只有 个，从构建回文树这一过程即可得出。
于是我们直接在偶串的回文树上跑树上 LDS 即可，场上回文树忘了怎么写了所以写了哈希暴力建回文树，最终复杂度 。
B - Cocktail Sort
swap 操作执行的次数就是逆序对个数，comp 操作的次数是大循环的轮数 。
考虑循环次数怎么算，设定一个阈值 ，将数列中小于等于 的数设为 ，大于 的数设为 ，则当 取遍 时，对这些 序列排序的循环轮数的最大值就是对原序列排序的轮数，证明是简单的。
于是我们只需快速对一个 序列求循环轮数，设 有 个， 有 个，发现内部的循环相当于每次将一个 和一个 归位（前 个数中的 个数加一， 同理），所以总循环轮数即为初始前 个数中 的个数。注意最后还会跑一轮空循环。
时间复杂度 。
C - Corrupted Odyssey
随机生成的字符串每个字母出现频率的极差不会太大，故极差小的那个字符串为随机生成的。
F - Knapsack One Million
首先考虑一个剪枝：由于是完全背包，所以若对于一个物品 ，若存在另一个物品 满足 且 ，则物品 显然不如物品 优，故不会选择物品 。
将物品看作点置于二维平面上，则有用的点是一个上凸壳，即按 排序后的 的前缀最大值，由于数据随机生成，经典的结论是前缀最大值期望个数是 个的，暴力背包即可，时间复杂度 。
G - Puzzle Boy
先假设全是正数的情况，对某个数做质因数分解，奇数次方的质因数对应位置设为 ，反之设为 ，则某个乘积是完全平方数，当且仅当对应掩码的异或和为零，因此，最优集合必须构成一个线性基。
由拟阵的结论得从大到小往线性基里面加数是正确的，可以在个数最多的条件下最大化乘积，现在来考虑有负数的情况。
把负数当成整数最大化乘积的绝对值，如果最后得到的乘积为正，则答案就是该乘积，否则我们需要调整使得其乘积为正并且最大。
我们将把某个不在基内的数和基内某数交换称为一次调整。若调整超过一次，则除最后一次调整以外的前面几次调整都会破坏基的性质，故直接调整最后一次显然更优并且合法，所以我们只需遍历不在基内的元素，看是否能和基内的某个元素（符号要相反）进行交换。由于基的大小不会超过 ，故复杂度是正确的。
假设用 与基里面的一个数 交换的话，只要看原来的线性基表示出 的元素中是否包含 ，如果是则可以换，否则不行，于是我们遍历线性基找到表示 的所有数并且更新答案即可。
如果全都没法交换，则答案必定为负的，此时我们需要最小化乘积的绝对值，类似地，从小到大往线性基里面加数即可。最后的时间复杂度是 ，其中 。
H - Shell Shock
相当于给 个节点分成若干组，路径条数即为各组大小的乘积。
特判一些边界情况，然后发现 ，于是最多只有两个大小为 的组，其余每 个一组即可，时间复杂度 。
K - Urban Horizons
设 为从边集 出发期望还需添加多少条边才能让图联通，则有以下转移：
注意到 只和 形成的连通块大小的多重集有关，所以一共只有 种不同的状态，其中 为 的划分数，在 时 。
然后移项做 dp 即可，时间复杂度 。