2024年浙江工商大学新生赛题解

A.选择

方法一：固定中位数的思想。先对数组从左到右按非递减顺序排序，枚举第 $i$ 个元素作为中位数的情况，那么我们只需要在满足第 $i$ 个元素是中位数的前提下选择尽可能多的元素。如何保证第 $i$ 个元素是中位数？令位置 $i$ 左边的元素选了 $x$ 个，位置 $i$ 右边的元素选了 $y$ 个，只需要满足 $x=y$ 或 $x 1=y$ 即可。如何在此条件下选择最多的元素？令位置 $i$ 左边有 $a$ 个元素，位置 $i$ 右边有 $b$ 个元素，令 $t=min(a, b)$ ，那么取 $x=t，y=min(t 1,b)$ 最优。

方法二：通过证明结论减少方案的选择。先对数组从左到右按非递减顺序排序，如果记 $mid=\left \lfloor \frac{n 1}2 \right \rfloor$ ，那么只需要考虑中位数对应下标 $pos$ 满足 $pos\ge mid$ 的情况而不需要考虑 $pos \lt mid$ 的情况，证明显然：考虑对于所有 $pos \lt mid$ 的情况，对所选元素下标按照中心位置对称，即对于所选下标 $i$ 都改成 $n 1-i$ 后一定合法且不劣，因为所选大小不变，而中位数可能不变或增大。因此直接枚举所有下标 $i(1\le i\le n)$ 作为左端点下标 $n$ 作为右端点的连续区间更新答案即可。

B.ljl的魔方矩阵

因为中间的数给定了，那么行和其实也给定了，就是中间这个数的三倍。然后每次暴力判断每行、每列、对角线是否只缺一个数，判断六次即可，这样操作后会出现两种情况。

此时所有的数已经全部填好了。
此时缺少四个角的数，这种情况处理一下即可。

标程给的是更一般的解法，即中间的数不给定也可以处理，先通过线性代数的知识解出三个基础解系，然后用给定的三个数构造出三元一次方程组。解出系数即可。

C.交换

根据本题的数据范围，将使用DP进行解题。

假设 $n$ 次操作要加的数组下标为 $p_1, p_2, \cdots, p_n$ 。显然，加到总分里的数不可能为 $0$ ，并且 $p_1 \le p_2 \le \cdots \le p_n$ （后面大的数只会往前移动，不可能把前面大的数移到后面进行处理）。于是问题转化为求 $\sum\limits_{i=1}^n a[p_i]$ 。

定义 $dp[t][last][m]$ 表示第 $t$ 次操作， $p_t=last$ ，且已经进行 $m$ 次交换最多可以得到的分数。

分以下两种情况进行转移：

$p_t = p_{t-1}$ ：对于这种情况，转移为 $dp[t][last][m] = dp[t-1][last][m-1] a[last]$ 。
$p_t \gt p_{t-1}$ ：首先， $p_t \ge t$ ，所以把 $p_t$ 的数移到 $t$ 的位置需要 $p_t - t$ 次移动。所以 $dp[t][last][m] = \max\limits_{j=1}^{last-1} (dp[t-1][j][m-(p_t-t)]) a[last]$ 。这里可以使用前缀最大值优化，使得计算 $\max\limits_{j=1}^{last-1} dp[t-1][j][m-(p_t-t)]$ 只需要 $O(1)$ 的时间复杂度。

总的时间复杂度为 $O(n^3)$ 。

D.狭义"LJL"

签到题。读入整行字符串，对连续的三个字母判断是否是"ljl"，如果是则跳过这三个字母，输出"ncljr"，否则输出当前字母。使用python可3行秒杀。

E.上升还是下降

题目大意:

给定一个长度为 $n$ 的排列，每人轮流操作，最后序列变成升序则ljl获胜，变成降序则ljr获胜，如果分不出胜负则平局。

题解

统计三个值，只有ljl需要操作的数的数量 $t1$ ，只有ljr需要操作的数的数量 $t2$ ，ljl和ljr 都需要操作的数的数量 $t3$ 。

如果 $t3=0$ ，此时ljl和ljr的策略都是独立的，由于ljl先手，所以 $t1 \le t2$ 时ljl获胜，不然ljr获胜，不会出现平局情况。

$t3 \gt 0$ 时，来看 $t1$ 和 $t2$ 的关系。如果 $t1 \gt t2$ ，此时ljl没有获胜的可能，所以此时只会出现卢减亮获胜或者平局的情况。如果 $t1 \gt t2 t3$ ，ljr获胜，不然平局。同样的，如果 $t1 \le t2$ ，此时只会出现ljl获胜或者平局的情况，如果 $t2 \ge t1 t3$ ，ljl获胜，不然平局。

F.感谢庆典的MEX

题意：已知长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ ，定义一次操作的过程为：选择任意一个元素，随后将 $a_i$ 从原序列中删除，并将 $\left \lfloor \dfrac{a_i}{m} \right \rfloor$ （向下取整）添加回原来的位置。你可以进行任意多次操作（也可以一次操作都不做），要求使得序列的 $\rm MEX$ 最大，求这个最大的 $\rm MEX$ 值。

首先我们发现题目给的数值特别大，而这题实际上最大的 $\rm MEX$ 也不会超过 $n$ ，因为 $\rm MEX$ 为没有出现在数组中的最小非负整数。那么由于只有 $n$ 个数字，所以最坏情况是所有数字从 $0 \sim n - 1$ 出现一次，那么答案就会是 $n$ ，否则由于有一些数字大了导致 $0\sim n - 1$ 中有空值了，就会取到那个值而不会更大，所以答案一定 $\le n$ 。

知道这个性质有什么好处呢？这为之后的二分和特判埋下了伏笔。

这里先看 $m!=1$ ，如果我们求出了答案为 $ans$ ,那么是不是相当于 $0 \sim ans-1$ 的数都出现过了，而 $ans$ 没有出现过，所以假设我们求出了一个值 $x$ 在 $0\sim ans - 1$ ，那么 $x$ 一定满足是 $\rm MEX$ 的，因为我们可以一直除以 $m$ 达到让答案变成 $x$ ，如果 $x$ 大于等于 $ans$ ，那么由于 $ans$ 不可能在数组那个数组中出现，一定不能作为答案，所以我们会发现答案具有二段性，小于 $ans$ 的都可以变大，大于 $ans$ 的都必须变小，那么我们就确定了上下界为 $1 \sim n$ （为什么不为 $0$ ,因为 $m \gt 1$ 一定可以将一个数一直除到 $0$ ,那么最小答案一定为 $1$ ）。那么我们就可以二分枚举答案，再判断一下 $0\sim ans - 1$ 是不是都能被构造出来。那么问题就变成了我们要将数组除以 $m$ 使得所有 $0 \sim ans - 1$ 的数值都要出现。

判断的时候就可以贪心去想了，记二分中点为 $mid$ ,首先所有小于 $mid$ 的值 $x$ 我们都可以先在数值为 $x$ 位置填上，如果重复了就直接除以 $m$ ，直到到达一个没有填过的位置，如果变成 $0$ 了还没有位置就停止，所有大于等于 $mid$ 的数值都可以直接除以 $m$ 变小，直到到达 $mid$ 以内第一个没有填过数值的位置，然后填上，如果变成 $0$ 了还没有位置就停止。然后检查下 $0\sim mid - 1$ 的每个位置上是否有数，如果都有就让二分的左端点变成 $mid$ ，否则就让右端点变成 $mid$ 。

证明贪心正确:

首先是如果有一个位置只有一个数能到达，那么它一定要在那个位置上，如果前面还有它能到达的，但是没有数字填上去，那么它如果到前面的位置了一定会空出当前位置导致有一个值没出现，一定会让mid变小，所以这样到达 $mid$ 以内的第一个位置一定更优。

而如果有一个位置有两个及以上的数字能够到达，那么我们让后面到达的数向前走，两个是等价的，所以一定可以得到更优解。（这里可以用跟最优解比较法进行比较以得出这种贪心一定更优）。

所以证明贪心正确。

由于二分有个 $log_2n$ ，而如果将 $10^{18}$ 对 $2$ 整除最多进行 $60$ 次左右，枚举位置为 $n$ 。所以最坏时间复杂度为 $O(nlog_2nlog_210^{18})$ ，大约为 $10^8$ 左右，可以通过本题，但是建议先将所有 $a_i$ 先除到 $n$ 以内，因为 $n$ 以为都为无解（上证明过），这样可以快大约 $4$ 倍左右。

你们以为结束了吗？还没有，这里有一个坑人的点，就是任何数除以 $1$ 都为本身，所以当 $m=1$ 时要特判，这就是简单的求一个数组的 $\rm MEX$ 的问题，这个可以先对数组离散化，然后找出从 $0\sim n$ 第一个没有出现的数输出。也可以先把所有数插入 $set$ 中，然后找出从 $0\sim n$ 第一个没有出现在 $set$ 中的数输出。时间复杂度为 $O(nlog_2n)$ 。

所以总的时间复杂度为 $O(nlog_2nlog_210^{18})$ 。

G.约数

问题为求 $F(n) F(n 1) \cdots F(m)$ ，可以转化为求 $\sum\limits_{i=1}^m F(i) - \sum\limits_{i=1}^{n-1} F(i)$ 。

对于 $\sum\limits_{i=1}^m F(i)$ ，如果挨个求 $F(i)$ ，那么时间复杂度为 $O(m\sqrt m)$ ，会超时。转化一下思路，对于一个正整数 $x$ ，它在 $1~m$ 中出现了多少次？由于 $1~m$ 中 $x$ 的倍数有 $\lfloor \frac{m}{x} \rfloor$ 个，所以 $x$ 的约数和为 $\lfloor \frac{m}{x} \rfloor \times x$ 。

所以， $\sum\limits_{i=1}^m F(i) = \sum\limits_{i=1}^m \lfloor \frac{m}{i} \rfloor \times i$ 。显然，现在可以采用整除分块去计算。对于一段区间 $[l,r]$ 来说，其 $\lfloor \frac{m}{i} \rfloor$ 值是相同的，但是 $i$ 的值不同，需要利用等差数列公式计算出这一段区间的 $i$ 之和，然后与 $\frac{m}{i}$ 相乘便是这段区间 $[l,r]$ 的贡献。注意整个计算过程要取模。

时间复杂度为 $O(\sqrt n \sqrt m)$ 。

H.ljl要不对称的美

题目类型：字符串

这道题目数据规模较大，进行暴力肯定会超时。所以面对每次查询，我们必须要用 $O(1)$ 的时间复杂度去处理。

注意到：

当真子串长度 $len = 1$ 时，该子串被认为是对称子串，所以一律不考虑。
当区间串中的所有字符都相等时，所有偶数的长度（ $len \% 2 == 0$ ）都不可计入答案，否则都可计入。

如 "aaaaaaa" 查询 "1 7"，可以发现找不出长度为 2 、 4 和 6 的非对称字符串；

而 "aaaaaab" 查询 "1 7"，即可找到非对称字符串"ab"、"aaab"、"aaaaab"，从而答案+=3。
当区间串中所有偶数位的字符相等，所有奇数位的字符相等，则所有奇数的长度（ $len \% 2 == 1$ ）都不可计入答案，否则除 $1$ 外都可计入。

如"abababa" 查询 ”1 7“，可以发现找不出长度为 3 和 5 的非对称字符串；

而"abababc" 查询 "1 7"，即可找到非对称字符串 "abc"、"ababc" ,从而答案+=2。

代码思路：

从左往右存与当前位字符相等的、最近的字符的距离。如"abca"，第一个a的相等的最近距离为3。

在查询时只用查找区间中第一位或第二位的最近相等位置，然后按上面这个规律去判断：如果第一位的最近相等的字符没超过区间，则所有偶数的长度计入答案；如果第一位或第二位的步长为2的相等的字符没超过区间，则所有奇数的长度计入答案。（注意！所有查询都是真子串，所以区间长度不计入答案。）

I.数字重组

不妨把这个数字看成一个大小最大为9的数组，

那么重组这个数字的所有可能即为该数组的全排列，时间复杂度为 $O(n!)$ ， $n_{max}=9$ 。

我们只要暴力枚举所有的情况然后用 $O(n)$ 的时间维护这一排列情况的大小即可。

总时间复杂度为 $O(n!\times n)=3265920=3\times 10^6$ 。

如何暴力枚举

1.DFS

ll ans = 0;
bool vis[15];
void dfs(int x) {
    if (x == N) {
        string t;
        for (int i = 0; i < N; i++) {
            t += s[p[i]];
        }
        ans = max(ans, cal(t));
        return;
    }
    for (int i = 0; i < N; i++) {
        if (vis[i]) continue;
        vis[i] = 1;
        p[x] = i;
        dfs(x + 1);
        vis[i] = 0;
    }
}
dfs(0);

2.next_permutation()

for (int i = 0; i < N; i++) p[i] = i;
do {
    string t;
    for (int i = 0; i < N; i++) {
        t += s[p[i]];
    }
    ans = max(ans, cal(t));
} while (next_permutation(p, p + N));

计算权值

ll cal(string &t) {
    reverse(t.begin(), t.end());
    ll res = 1;
    for (int l = 0; l < t.size(); l += 3) {
        int r = min((int)t.size() - 1, l + 2);
        int v = 0;
        for (int i = l; i <= r; i++) {
            v = v * 10 + t[i] - '0';
        }
        res *= v;
    }
    return res;
}

J.优雅的字符串

如果 $s$ 中还有两个相同的字符，则输出 $-1$ 。

否则，总是可以通过替换 $?$ 来使得 $s$ 变成优雅的字符串。做法如下：顺序扫描 $s$ ，如果碰到 $?$ ，需结合前一个字符 $prev$ 和后一个字符 $next$ 进行判断填写。如果 $next$ 为 $?$ ，则只需要填写与 $prev$ 不同的字符即可。如果 $next$ 不为 $?$ ，则需要填写与 $prev$ 和 $next$ 都不相同的字符。为了处理方便，需在 $s$ 的头尾各加一个 $?$ 进行扫描。

时间复杂度为 $O(|s|)$ 。

K.ljl想找到最佳数

签到题。根据题意模拟即可。