 游记（VP）)
省流
表现分 \(1716\)。
10.19
内含剧透，请vp后再来。
不是题解！！！！！！！
赛时
A 题给定一个字符串，每次操作可以把前一个字符变成后一个，问至少操作几次使所有字符相同。最后一个变不了，肯定要都变成最后一个字符。从后往前遍历，如何不是这个字符的就变成他后一个，故答案为与最后一个字符不同的个数。
B 题是有一个浏览器，上层有 \(n\) 个窗口，每个窗口标准长度为 \(b\)，如果窗口过多塞满了长度 \(a\) 则每个窗口长度为 \(\frac{a}{m}\)。每个窗口的关闭键都在窗口最右侧，求最少要移动几次鼠标关闭所有窗口。当窗口长度均为 \(b\) 时只需要鼠标一直放在最左侧窗口处即可，若填满所有窗口则鼠标一直在末尾处即可。注意 \(b = a\) 时只需要一开始移动到末尾就可以全部删完。
C 题给了一个长度为 \(n\) 的环状序列，每次可以删掉相邻的两个数，使这两个数合并并变为较大的那个，消耗为较大的那个值，问把所有数合并成一个消耗最小为多少。发现当较大值最小的一对数合并后，并不会影响周围两个值接下来合并的消耗，且合并后少了一个较小的数字，总消耗必不可能减小，则从较大值最小的一对数开始合并即可。由于不会影响其他数合并的消耗，故直接将所有对消耗全部加起来，最后删掉最大对即可。
D 题给定一个多重集，把这个多重集分成任意个非空多重集，取出分配后每个多重集的众数作为一个新的多重集，问这个新的多重集有多少种。先想暴力的做法，设计 \(dp[i][j][k]\) 为到第 \(i\) 个数，已经选出了 \(j\) 个众数，有 \(k\) 个数没有被选需要均分到所有被选的众数下。每个数如果选出大于 \(0\) 个众数，则不会增加未被选数，如果等于零，则会增加该数个数个未被选数。然后发现并不关心已经选出的众数个数，选出不为零个众数的情况直接就是原 dp 乘 \(a[i]\) 即可。这样写完后发现样例无法通过，因为并不是每个选择了的数只能抵消一个未被选择的数，而是可以抵消每个未被选择的数各一个，所以要关心的是最大的未被选择数。于是我排序了一下开始动态维护最大未被选择数，不过最后没调出来，比赛结束。
赛后
看了一眼题解，D 题发现只需要关心出现次数最多的那个数即可。如果最多的那个数已经选择，那么所有的数都可以被这个覆盖，如果未被选择，则被选择的数之和要大于这个最大的数。即 dp 结果中未被选择的数小于等于 \(n - maxx\) 的都可以选择。
E 题给了 \(n\) 个数 \(a_i\)，又给一个 \(c\)，要求选择一些 \(b_i\) 使每个 \(b_i \leq a_i\) 使 \(b_i\) 的异或和为 \(c\)。其中可以选择对某个 \(a_i\) 加一，消耗为 \(1\)。求最小消耗。异或没什么用，不想要的直接取 \(0\) 就行。那么题目就变为求所有 \(a_i\) 覆盖 \(c_i\) 为 \(1\) 的位的最小花费。从高位往低位，如果 \(a\) 存在的 \(1\) 大于 \(c\) 这一位的，则直接可以拆开这个一覆盖，输出答案。如果 \(a\) 和 \(c\) 等于，那么就比较下一位。如果 \(a\) 小于 \(c\)，那么就找到一个加到这一位消耗最小的 \(a\)，然后比较下一位。但是 \(n \leq 5e5\)，\(q \leq 5e4\)，不能直接遍历所有 \(a\) 查找。发现当 \(n\) 较大时，最多会修改 \(30\) 个数，而越大的数显然越好修改，所以每次只取出最大的 \(30\) 个数遍历即可。
2025年11月20日