序列操作

将每个序列转换为 $X_i=2\sum_{k<i}A_k+A_i$。删除位置 $i$ 后，对后方位置 $j$，若距离为奇数，其前缀和减少 $A_i$，元素增加 $2A_i$；若为偶数，其前缀和增加 $A_i$，元素减少 $2A_i$。因此转换值不变，操作只会删除对应位置。 该变换可逆：已知前方元素之和 $P$，下一元素为 $X_i-2P$。所以要保留转换后两序列的最长公共子序列。若 LCS 长度为 $L$，答案为 $N+M-2L$。 子任务 1 直接枚举实际删除操作的可达状态并比较。状态至多 $2^N$ 个，使用有序集合时保守时间上界为 $O((2^N+2^M)(N+M)^3)$。完整解使用 LCS 动态规划，时间 $O(NM)$，空间 $O(M)$。 初始转换值绝对值不超过 $49\,995\,000$，以后始终是其子序列。因此恢复出的任一元素绝对值不超过 $(2\cdot5000-1)49\,995\,000<5\cdot10^{11}$，有符号 64 位整数足够。 Solution written by GPT6.1