【题解】2024年中国传媒大学程序设计大赛

A 小苯的区间和疑惑

考虑区间和本质上就是一段前缀和减去另一段前缀和，因此我们尽量让这个差值尽可能大即可，那就可以直接维护“前缀和数组 ” 的前缀最小值 和后缀最大值 ，每个 的答案就是 。

B 小苯的三元组

考虑 ，同时
因此 ，两者要想前者大于等于后者，当且仅当取等号，即：。
而
，说明 是 的因子。
，说明 是 的倍数。

因此只需要预处理出 以内所有数字的倍数个数和因子个数（这步可以调和级数 ）。
接着枚举 ，答案加上 的因子数乘 的倍数即可。

C 小红的 CUC

签到题。输出一个CUC后面随便输出啥都行，但最好别随机，否则可能会再随机出一个CUC

D 小红的矩阵构造（一）

解法1：我们首先将的那一行全部填成1，然后将的那一列全部填成0，然后将的那一行全部填成1……以此类推，最终即可填完所有。

解法2（by 炸鸡块君）：观察样例得知，当且仅当时对应位置为1，否则为0。这个性质可以推广到任意排列，因为排列也可以由样例交换某些行/列形成。

E 小红的矩阵构造（二）

签到题。我们按顺序不断复制的全1矩阵即可，直到最终没地方赋值了（位置越界了），如果还没用完则输出-1。

F 小红的子树乘积

通过启发式合并来维护子树乘积的因子数量。我们需要用map维护每个素数的幂次，然后维护最终幂次加1的乘积即为因子数量。如果超过了则可以直接剪枝掉，其祖先必然也是超过的。

G 小红的独特区间

“种类数恰好为3”的区间，即“种类数不超过3”的区间数，减去“种类数不超过2”的区间数。这两个问题都可以用双指针来解决。

H 小红的生物实验

dfs板子题。首先确定“外部区域”，这部分可以从边界部分的 '.' 字符dfs出来。然后根据题意，和“外部区域”相邻的细胞器则为细胞壁，将这些全部变成字符 '.' 即可。

小红种树（一）

求个等差数列第到项最大值和最小值之差求和。

立刻想到若干个等差数列的最大值/最小值构成一个半平面交

可以利用单调栈求得半平面交内的优势直线。

求半平面交的时候有个trick可以避免叉积爆long long，由于查询的点都是整数，所以可以用求得焦点的坐标，向下取整保留整数。的值就是相邻优势直线有事区间的分界点，例如上图红色和蓝色的直线，求得，所以红色直线更优势，的区域蓝色以及蓝色后面斜率更高的直线更优，然后依次遍历求的所有的分界点。

接下来只考虑最大值，考虑最大值和水平数轴的差值，问题转化成求每一条直线的优势区间，假设其优势区间为，等差数列的首项为，公差为，则有等差数列的和，这段优势区间的差值为，对于最小值，重新计算依次再减去即可。

J 小红种树（二）

我们先假设所有树都变得和最高的一样（即最高那棵树增量为0），可以求出每棵树的需要增长的高度。显然最终的答案即这些高度的gcd的因子数量。当我们让最高的树变高的时候，若变高了，则最终所求的是的因子数量（g即为初始求的gcd）。用筛法预处理后，枚举每个即可。