2024年华东交通大学“双基”程序设计竞赛题解

期望难度：G EC JH ABI DF

G.ECJTU

纯签到，略。

E.劳苏的数字

三个数字非常大，所以要用字符串来读入，显然，我们只需要关注其中的某个数字的数位之和能否能被 $3$ 整除即可。

C.斐波那契

注意一个很重要的性质：

奇数 + 奇数 = 偶数
奇数 + 偶数 = 奇数
偶数 + 偶数 = 偶数

除开全是偶数的情况，相邻两项的奇偶性搭配只有三种，那么当长度等于5时，相邻情况有四种，根据鸽巢原理，第四种必然与前面某一种相同，所以从第四项开始，奇偶性必然会进入循环，且循坏节的长度不超过3。

那么只要分四种情况来考虑：

$x$ 是奇数， $y$ 是偶数，那么循坏节为 $\textbf {奇偶奇}$ ，那么 $f(i,x,y)$ 是偶数当且仅当 $i \ mod \ 3 = 2$ 。
$x$ 是奇数， $y$ 是奇数，那么循坏节为 $\textbf {奇奇偶}$ ，那么 $f(i,x,y)$ 是偶数当且仅当 $i \ mod \ 3 = 0$ 。
$x$ 是偶数， $y$ 是奇数，那么循坏节为 $\textbf {偶奇奇}$ ，那么 $f(i,x,y)$ 是偶数当且仅当 $i \ mod \ 3 = 1$ 。
$x$ 是偶数， $y$ 是偶数，那么 $f(i,x,y)$ 恒为偶数。

J.Never Loneliness

容易从题目给出的要求发现，我们需要构造出一个相邻前缀和的符号相反的序列，所以我们的序列只有下面两种状况

+ - + - + -.....

或者

- + - + - +.....

所以我们只需要分别将数组变成上面的形式之后取 min，这样就可以得到最小值。

当应该为正时但前缀为负时则强制转化为 $1$ 。
当应该为负时但前缀为正时则强制转化为 $-1$ 。

H.乖乖起飞！

题意为每次操作可以从第 $i$ 号点到第 $i 1$ 、 $i - 1$ 、 $i a[i]$ 或 $i - a[i]$ 号点，求从 $1$ 到 $n$ 的最少时间？

用 $bfs$ 即可。

A.环形取数

多模拟几遍游戏过程我们可以发现，当先手拿走第一个元素后，后续的数只能在已选数的左右取一个，后续的游戏内容相当于两个选手轮流从一个序列两端选择一个数取走。

我们先假设先手第一个数取得是 $a_1$ ，那么整个游戏过程就相当于 $Alice$ 和 $Bob$ 轮流从序列两端选择一个数取走，只是钦定了 $Alice$ 要先选 $a_1$ 。

这个问题怎么解决呢？

我们定义 $\text dp(l,r)$ ： $Alice$ 和 $Bob$ 在 ${a_l,a_{l 1},...,a_r}$ 这个子数组两端轮流选择一个数取走，先手能获得的最大总得分。

定义 $\text sum(l,r)$ 为 $a_l,a_{l 1},...,a_r$ 的和。

那么我们有： alt

通过这个式子，我们就可以在以 $O(n^2)$ 的时间复杂解决这个简化的问题，答案就是 $a_1 sum(2,n) - dp(2,n)$ 。

现在我们回到原问题，原问题先手可以任意选择第一个元素，所以我们的序列不一定就是 $a_1,a_2,...,a_n$ ，

还有可能是 $a_2,a_3,...,a_n,a_1$ ， $a_3,a_4,...,a_n,a_1,a_2$ 等等。

我们不妨将 $a$ 序列复制一遍，接到 $a$ 序列后面，形成一个长度为 $2\times n$ 的序列，那么先手的每种初始选择都对应一个长度为 $n$ 的序列。例如：

先手第一个元素先选择 $a_1$ 或 $a_n$ ，那么游戏相当于轮流在 $a_1,a_2,a_3,...,a_n$ 这个序列两端轮流选择一个数取走。

先手第一个元素先选择 $a_1$ 或 $a_2$ ，那么游戏相当于轮流在 $a_2,a_3,...,a_n，a_2$ 这个序列两端轮流选择一个数取走。

那么我们的答案就是 $\max_{i=1}^ndp(i,i n-1)$ 。时间复杂度 $O(n^2)$ 。

B.gcd 之和

首先我们考虑一个暴力的解法：枚举区间左右端点，暴力计算区间 $\text {gcd}$ 和 $\textbf {按位或和}$ 。

主要代码如下：

        int ans = 0;

		for (int i = 1; i <= n; i++) { // 枚举区间左端点
            int x = 0, d = 0;
            for (int j = i; j <= n; j++) { // 枚举区间右端点
                x = x | a[j]; // 区间或 
                d = gcd(d, a[j]); // 区间 gcd
                ans += x * d;
            }
        }

这个做法的复杂度是 $O(n^2log)$ 的，并不能通过此题。

现在我们考虑如何优化。

注意一个重要的性质： $gcd(a_l,a_{l 1},...,a_r) \ge gcd(a_l,a_{l 1},...,a_r,a_{r 1})$ ，当且仅当 $d$ 整除 $a_{r 1}$ 时取等号，否则只能取小于号，并且 $gcd(a_l,a_{l 1},...,a_r) \ge gcd(a_l,a_{l 1},...,a_r,a_{r 1}) \times 2$ 。

我们记 $d = gcd(a_l,a_{l 1},...,a_r)$ ，那么 $gcd(d,a_{r 1})$ 要么等于 $d$ ，要么小于等于 $\frac{d}{2}$ 。

所以对于左端点相同的区间，区间 $gcd$ 的取值最多只有 $log_{_2}a_l$ 种。

现在我们假设区间 $[l,x],[l,x 1],...,[l,y]$ 些区间的 $\text gcd$ 都相等，那么我们只要知道这些区间的 按位或和 的和，就可以快速计算这部分区间的权值和。

现在我们考虑如何快速计算区间 $[l,r]$ 所有前缀的 按位或和 的和，因为 按位或 运算对于每一位二进制之间是独立的，我们可以考虑拆位来计算，算有多少个前缀的 按位或和 第 $i$ 位是 $1$ ，这个比较简单，只要记录一下 $a_l$ 右边（包括 $a_l$ 自己）第一个第 $i$ 位是 $1$ 的数在哪里就好了，假设这个位置是 $pos$ ，那么区间 $[l,r]$ 所有前缀的 按位或和 中，有 $r - pos 1$ 个第 $i$ 位二进制是 $1$ ，这样我们就可以在 $O(log)$ 的复杂度内求出 $[l,r]$ 所有前缀的 按位或和 。

求区间 $[l,r]$ 所有前缀的 按位或和 的和代码如下:

int get_or(int x,int y){ // 返回 a_x 到 a_y 的前缀或的和。
    int res = 0;
    for(int i=30;i>=0;i--){
        int cnt = max( y - r[i][x] + 1, 0ll);
        res += cnt * (1 << i);
    }
    return res;
}

现在我们已经能求出区间 $[l,r]$ 所有前缀的 按位或和 的和，那么我们如何求区间 $[l,x],[l,x 1],...,[l,y]$ 的 按位或和呢？

只要利用前缀和的思想即可解决。

$[l,x],[l,x 1],...,[l,y]$ 是区间 $[l,y]$ 的前缀的一部分，所以 $[l,x],[l,x 1],...,[l,y]$ 的 按位或和 为 $get\_or(l,y) - get\_or(l,x-1)$ 。

现在我们只需要对固定的左端点 $l$ 找出 $\text gcd$ 发生变化的位置即可，这个问题如何解决呢？

假设我们现在已经找出了左端点为 $l$ 的区间根据 $\text {gcd}$ 划分的段及各段对应的 $\text {gcd}$ : $[l_1,r_1,d_1]，[l_2,r_2,d_2]，...，[l_i,r_i,d_i]、...、[l_m,r_***mp;preview=true$ ，其中 $d_i > d_{i 1}$ 。

段 $[l_i,r_i,d_i]$ 的含义为：区间 $[l,l_i],[l,l_{i} 1],[l,l_i 2],...,[l,r_i]$ 的 $gcd$ 都是 $d_i$ 。

现在我们来找左端点为 $l-1$ 的区间根据 $\text {gcd}$ 的划分，只要在 $l$ 的划分的基础上加上 $1$ 个段 $[l-1,l-1,a[l-1]]$ ，然后把 $l$ 划分的每一段 $[l_i,r_i,d_i]$ 的 $d_i$ 替换成 $\text {gcd(di,a[l-1])}$ ，最后合并 $d_i$ 相同的段就得到了 $l-1$ 的划分。（ $O(log^2)$

事实上，对于同一个 $l$ 划分的段具有一个性质:

d_{i 1} | d_i

由此得：

\ \ \ \ gcd(d_{i 1},d_i) = d_{i 1} \\ gcd(d_{i 1},a[l-1]) \\ \ \ \ \ = gcd(\ gcd(d_i,d_{i 1}),a[l_1]) \\ = gcd(d_i,d_{i 1},a[l-1]) \\ \ \ \ \ \ \ \ \ = gcd(gcd(d_i,a[l-1]),d_{i 1})

我们可以记一个 $temp$ 来记录下一段要和谁取 $\text {gcd}$ ，更新完下一段的 $gcd$ 后，将 $temp$ 替换掉，那么每次更新后， $temp$ 要么不变，要么至多变成原来的一半，若 $temp$ 不变，说明 $gcd(temp,d_i) = temp$ ，此时这个 $gcd$ 是 $O(1)$ 的，对固定的 $l$ 最多有 $log$ 段，所以每次求 $l$ 的划分是 $O(log)$ 的。

这样可以使得分段过程更快速。

复杂度分析：

划分段的整个过程的复杂度是 $O(n\ (log\ a[i]))$ 。

总共划分的段大概是 $nlog$ 段。

统计每一段的答案的复杂度是 $O(n\ (log a[i])^2)$ 。

所以总的复杂度是 $O(n\ (log a[i])^2)$ 。

I.Reinforced Problem

题解比较新手向，讲解的会比较细。

假如直接贪心从前往后选，能选就选，会发现这样会影响到后面的决策，所以我们需要把状态存起来，考虑使用动态规划。

不妨称连续玩原神的几天为一个区间，这些区间都是不相邻的，因为假如两个相邻的话，这两个区间就等价于一个区间了。

那么这个区间怎么样是合法的呢？由于这些区间都是不相邻的，所以只要保证这个区间的所有愤怒值前缀和的值都小于 $m$ 。

那么我们的问题就变成了选出若干个合法区间，使得这些区间的喜悦值之和最大。

由于我们发现，每一个区间只有右端点的决策会影响后面的决策，所以我们设 dp[i] 为最后一个区间的右端点是 i 的最大喜悦值。

然后考虑怎么更新 dp[i]，影响 dp[i] 的因素有最后一个区间的左端点，倒数第二个区间的右端点。

所以我们遍历 dp 数组的时候还需要枚举一下这两个因素，设最后一个区间左端点为 $j$ ，倒数第二个区间右端点是 $k$ 。

总结为以下步骤。

判断区间 $[i,j]$ 是否合法。
计算出 $[i,j]$ 的喜悦值。
枚举倒数第二个区间的右端点。
更新状态 dp[i]=max(dp[i],sum + dp[k])。

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

难以通过此题。

考虑怎么优化，状态转移时第二层循环里面还有两个循环，第一个循环是计算 $[i,j]$ 的喜悦值之和，以及判断是否合法，计算喜悦值之和可以用前缀和优化，判断是否合法也可以使用一个前缀和数组，st[i][j] 表示 i 到 j 的愤怒值之和，但是直接这样是会出错的，因为区间合法的条件是这个区间的所有前缀之和都要小于 m，这里我们可以用一个小技巧，假如我们计算前缀和过程中（计算左端点是i的区间的前缀和），上一个区间的前缀和大于 m，那么这个区间是不合法的，那么直接把这个区间的前缀和设置成 m+1，这样就可以 $O(1)$ 判断某个区间是否合法了。

状态转移方程 dp[i] = max(dp[i], dp[j - 2] + sum[i] - sum[j - 1]);

时间复杂度 $O(n^2)$ 。

这显然也是不足以通过这个题目的，考虑继续优化。

前面算法的复杂度的瓶颈有两个，一个是预处理出 st 数组，一个是状态转移。

观察到 st[i] 是单调的，假如 st[i][j] 不合法，那么 st[i][j+1] 也一定不合法所以我们可以预处理出 st[i] 表示从 i 开始往右最多可以选到哪里，这个可以使用单调栈 $O(\text{n})$ 或者线段树 $\text{O(nlog(n))}$ 快速求出。

然后考虑如何快速转移。

考虑从前往后转移，将状态转移方程进行变换一下， $dp[j] = \max_{j<=st[i]}(dp[i-2]-sum[i-1]) sum[j]$ 。

用 $dp[i]$ 往后转移会发现转移的目标是一个连续的区间，可以用线段树完成，细节可能较多。

时间复杂度 $\text{O(nlog(n))}$ 。

D.? vs 1

题意为从 $n$ 个物品中选出若干个植物的战斗力公约数最大的情况下总和恰好为 $m$ 的最大值减最小值的差值最小。

观察到一个性质，假设战斗力是 $a[i]$ ，那么有效的个数是 $ceil(m/a[i]) 1$ 个，因此不需要 $n$ 个植物。

有效植物数为 $\sum_1^m (ceil(\frac{m}{a[i]}) 1)$ 个植物，用放缩的写法可以证明是不超过 $mlogm$ 个，然后还可以用二进制优化多重背包的方式继续优化。

公约数答案一定是 $m$ 的因子，我们从大到小枚举因子，找每个因此是否可以当作答案。

然后我们可以 $dp$ ， $dp[i][j]$ 表示从前 $i$ 个取总和是 $j$ 的拿的最小值最大的战斗力。

转移就是 $dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]])$ ，特殊地，若 $j==a[i]$ ，那么 $dp[i][j]=a[i]$ 。答案就是 $min(a[i]-dp[i][m])$ 。

实现做法较多，也可以用 bitset 做。

时间复杂度为 $O(T\times d(m)\times m^2logm)$ 。实际上二进制优化后很快。

F.String

题意翻译过来就是问有多少个子串三元组 $(a,b,c)$ ，使得 $a b=c$ ，然后考虑如何计算答案。

$a b=c$ 也可以看为将 $c$ 分割成S的两个子串，考虑枚举这个分界点。

定义 $\text{g}(l,r)$ 为 $S[l:r]$ 在 $S$ 中的出现次数，答案可以表示为

\sum_{i=1}^{n-1}(\sum_{j=1}^{i} \text{g}(j,i))\times(\sum_{j=i 1}^{n}\text{g}(i 1,j))

考虑如何计算 $\sum_{j=1}^{i} \text{g}(j,i)$ 和 $\sum_{j=i 1}^{n}\text{g}(i 1,j)$ 。

这两个计算方法同理，本文只介绍前者的计算。

关于后缀的计数问题我们可以考虑使用后缀数据结构，我们选择使用后缀自动机，会发现，对于每一个 $i$ ，我们计算的是以 $i$ 为后缀的所有子串的出现次数的和。

每一个 $S[1:i]$ 都对应不同的等价类，发现计算这些等价类的答案会简单很多。

不妨利用 $parent$ 树的计算每个的等价类的答案。

我们先用后缀自动机求出字符串 $S$ 中每个 $\text{endpos}$ 等价类的出现次数，然后在 $parent$ 树中的每一个节点，从上往下考虑对儿子的答案的贡献。假设 $sum[x]$ 表示编号为 $x$ 的等价类在 $S$ 中的出现次数，那么贡献就是等价类 $x$ 表示的串的数量乘以 $sum[x]$ 。

同样的方法求出 $\sum_{j=i 1}^{n}\text{g}(i 1,j)$ 即可。

需要注意答案可能会超过 $\text{long long}$ 的表示范围。

题解 | #环形取数#