再试试发个题解

题解发帖测试# 第十八届西南科技大学正式赛赛题题解

## A.花非花

### 题解：

先构造出一个序列 ，用 算法处理出以 为中心的最长回文串的长度 ，因为 是回文串，所以对于 ， 也是回文串，显然这样包含了所有以 为中心的回文串，也即以 为开头的回文串数量都 ，可以用差分来处理区间加，时间复杂度 。

## B.为欢几何

### 题解：

本场签到题之一。题意是按顺序输出 个字符串的第一个字符。

做法很多种，方法之一是开一个 数组 。循环 次输入字符串 ，每次循环过程输出 即可。

## C.花空烟水流

### 题解：

可知，长度为 ，由 种字符组成的字符串共有 种，而对于字符串 来说，连续子串的数量一定小于 。由此可得， 最长不会超过 。算出每个 的最大 ，然后直接暴力bfs搜索即可。最终复杂度为 。

## D.似花还似非花

### 题解：

如果没有不可选取 的这个限制，显然需要的最小操作次数就是排列长度 扣掉排列 的最长公共子序列长度，对于不属于最长公共子序列的元素，至多只需要1次操作就可以把它挪动到恰当位置。

如果限制了元素 不可被选取，那么答案就是排列长度 扣掉排列 的包含元素 的最长公共子序列长度。

因此，这个题实际上是求解两个排列的包含某一特定元素 的情况下的最长公共子序列长度。

两个排列的最长公共子序列长度问题可以转化为最长上升子序列长度问题。定义表示元素在数列出现的位置，定义，也就是数列中第个元素所在数列当中的位置，我们可以得到一个新数列。

这种情况下，求数列，的最长公共子序列问题其实就是求数列的最长上升子序列问题。

对于求解某数列的最长上升子序列问题，有一个动态规划+二分的解法，主要步骤如下：

1.定义一个动态数列，初始为空

2.从左到右遍历所有元素

2.1 获取当前遍历到的元素

2.2 如果该元素比中所有元素大(为空时也成立)，则把它放在数列最右端，跳过2.3

2.3 找到数列中大于的最左边的元素，并把它替换为

(在整个算法过程中，数列永远是单调递增的）

3.此时，数列的长度就是数列的最长上升子序列的长度。当然了，并不一定是的最长上升子序列，只是长度一致。

该算法时间复杂度为 ，因为步骤2.3可以通过二分查找来进行优化。

至于为何如此，请读者自行思考。

显然，我们可以通过该方法求解最长下降子序列问题，因为它们性质是一样的。



学会了如何求解最长上升子序列长度，就可以求解本题。

我们创建一个长度为的数组,和一个数组。

我们先从左往右遍历数列，求解该遍历顺序下的最长上升子序列长度，但是在算法步骤的2.2之前，需要统计数列当中有多少元素小于当前遍历到的元素，并把这个统计结果存入数组当中。

然后从右往左遍历数列，求解该遍历顺序下的最长下降子序列长度，同样地，在步骤2.2之前，统计有多少元素大于当前的，将结果存入当中

这样两遍处理完所需要的数据之后，在数列的某个元素被固定选取的情况下，数列的最长上升子序列长度就是 (它本身)。

这样，就可以以 的效率进行预处理，对于每个询问，以 的效率查询答案。

总体时间复杂度为 。

## E.西楼暮，一席疏雨

### 题解：

一个简单的排列组合问题。

选定一个数，剩下的位置就是一个 的排列，所以每个元素在式子中出现 次，用快速幂求即可，注意欧拉降幂，即 ，其中 是欧拉函数；根据排列的对换性质，逆序数为奇数的排列的个数和逆序数为偶数的排列个数一定相等，所以 产生的 的个数是 。时间复杂度为 。

特别的，当 等于 时特判，此时逆序数为 ，所以答案为 。

## F.青山隐隐，败叶萧萧

### 题解：

本题属于简单题。题意简化后如下：任意多次操作后，能否使得一个序列任意相邻两数之和为是质数，且每个数都是质数。

前置知识：奇数 奇数 偶数，奇数 偶数 奇数，偶数 偶数 偶数； 是最小的质数，也是唯一的偶质数。

又有无穷多个数满足：自身是质数，自身 仍是一个质数。这样的例子有很多，例如： 这些数都满足该性质。

所以题目一下就简单起来了：只要该序列是 "奇数偶数交替" 排列的数即可构造出满足题意的序列。

从第二个数开始遍历序列，判断是否满足 为奇数即可。

只有一个数的时候，则一定可以满足。

总时间复杂度为 。

## G.几番烟雾，只有花难护

### 题解：

由题意可知，本题要求的是 。

正常暴力跑，每一次单独计算答案，则时间复杂度为 ，显然会超时。

考虑使用整除分块的思想处理该问题。

设一共有 表示 的因数个数 个数满足 ，我们令 为这 项之和，即令 表示正整数 的第 个因子，则 。我们将原式的每一项的 部分均看成不能整除的结果，则每一项的该部分均可以改写成 ，故答案只需要在此基础上减去 即可。

根据先前推理，则所求原式可做以下变式：

原式





我们将该式子化为三个部分：

①： 部分，已经推得 ，计算 的一种方法是， 暴力遍历 的所有因子，计算所有因子的平方和。最后 注意要边累加边求余。

②： 部分，设 ，这显然是一个平方数前 项和公式。由多种方法均可推导出

，故直接计算值即可。但由于模运算中并不存在除法的性质，所以注意使用乘法逆元。

③： 部分，设 ，对于每个块均有：









该计算过程中，仍需要注意边累加边求余，且也需要使用乘法逆元，也需要注意括号内可能为负数，使用减法求余。



综上所述，可得原式 。令 ，仍需要注意的是，该项有可能为负数，使用减法求余，应输出 。

计算因子和整除分块的时间复杂度均为 ，故总时间复杂度为 。



最后注意：需要预处理 。若把他写在 函数中，则会被调用 次，其本身时间复杂度就达到 级别，会造成超时，总时间复杂度 。

## H.岸风翻夕浪，舟雪洒寒灯

### 题解：

：序列 的长度为 ；

：对于 位二进制数， 和 的后 位是相等的；

：对于 位二进制数， 共有 个数；

结论：第 位上的值即为 二进制位最低位 的位置。

假设对于 结论成立，那么对于

①：序列前 项与 相等，满足结论；

②：序列后 项等于前 项，由 可知满足结论；

③：序列第 项的值为 ， 的最低位 的位置为 ，满足结论；

(1)：由 ①②③ 可知，即当 满足结论时， 也满足结论；

(2)：对于 ，第 位的值为 ，满足结论；

由 (1)，(2) 可得结论成立；

可以通过位运算或者 `__builtin_ffsll()` 计算 的最低位 的位置，时间复杂度 。

## I.醉漾轻舟，信流引到花深处

### 题解：

这是一道二分答案 折半搜索的题型。折半搜索的部分是板子，但是这个算法比较冷门。二分答案倒是不难想到。

首先是二分答案，我们假定一个答案 ，如果得到的方案数未达到 ，那么往小调整答案区间，否则往大调整。

关键在于如何在限定时间内统计出可行购买方案数：

至多有 个物品，可以考虑把这 个物品分成较为平均的两部分、，然后购买情况有四种：

. 中什么都不买，中也什么都不买，显然只有 种方案；

. 中购买若干件物品，中购买若干件物品；

. 中购买若干件物品，中什么都不买；

. 中什么都不买，中购买若干件物品；

于是，我们可以对、 两个部分，分别进行 ，枚举所有的购买情况下花费的金额，每个部分至多只有 种方案。

那么我们可以很快统计出情况 和情况 的方案数。至于方案 ，我们先对， 枚举得到的金额花费列表进行排序，然后我们枚举 中的购买方案，再根据剩余的金额去二分搜索出 中有多少种购买方案，把方案数计入统计结果。枚举完之后得到的就是情况 的所有方案数。

最终将4种情况的方案数加起来就是对于这个 得到的最多方案数。

折半搜索部分，复杂度为 = 。

因为外层还有一个二分答案， 的取值最大可能取到 ，因此总体时间复杂度 。

## J.满城烟水月微茫，人倚兰舟唱

### 题解：

我们可以将牌堆看成 个队列，然后直接模拟即可。总时间复杂度为 。

## K.对潇潇暮雨洒江天，一番洗清秋

### 题解：

最短路问题，关键在于如何存这个图，另外还需要注意到的可能有些圆上没有点。

假设所有点都在前 的圆内，且每层均匀分布，那么建边的复杂度为 ，空间就已经爆了。可以发现，一般的，同一层的所有点都可以通向邻层上的所有点和次邻层上的所有点，而这些边显然都是冗余的，不难想到创建一个层结点，层结点到该层的所有点的花费为 ，一层上的所有结点（不包括层结点）到邻层、次邻层建边，注意与层结点相连的边都是有向的。

上的所有点只有出边， 上的所有点只有入边。假如“始元”上有 个结点，这些点都是源点，那么就需要跑 次最短路，假设最短路用优先队列优化的 Dijstra 算法，那么时间复杂度为 。最后所求的答案是所有源点的最短路的最小值，可以发现，对于最终的最短路径，不可能有从一个源点经过另外一个源点的最短路。所以可以保存所有"始元"上的点到其他"元"上的点的花费，省去"始元"中的其他点，即把这些 个点"压缩"成一个点，保留这个点到其他层的点的边。这样时间复杂度为 。

~~还有~~比较阴间的是，存在一种情况，点分布在 ，，这样就需要 点体力值， 在这个范围内，也就是卡了初始化无穷大的值。

## L.夜暗方显万颗星，灯明始见一缕尘

### 题解：

计算一个 的矩形网格中所有矩形的数目，即计算 的值。(每一种长度的边都能有一次贡献，长和宽相乘即为答案) 。


设挖去一个坐标为 的単位格子，包含点 的矩形数目就是： ，由均值不等式可得，当 和 越靠近中心时，这个值越大。同理可得，把被挖去的单位格子拓展为矩形，很容易得出，包含以 为左下角， 为右上角的矩形的方案数 。对这个挖去矩形的左侧共有 个点，右侧共有 个点。设左右相加的值为 ， ，可得 为一个常量。设 ，则 。可得

。再次使用均值不等式可得，当且仅当 取最大值为 。由于要让被挖去矩形的影响最小，所以 和 的差距要尽量大。左右如是，上下亦同理可得。综上所述，将被挖去矩形放在角落是最佳选择。

现分析将矩形"横"放还是"竖"放。计算 "L"型矩形网格的总矩形个数方法有很多，如图所示：


该"L"型矩形网格中矩形总数

。

是一个定值。二次均值不等式及简要证明后可得以下结论：

和 的差的绝对值越大，总矩形数越多。例如上图"竖"放，。若是"横"放，则 。将其带入上式，答案分别为 和 。

故最终只需要比较 和 的差的绝对值，取大的那种组合，带入式子即可得出答案。

注意要使用 哦~

## M.劝君终日酩酊醉，酒不到刘伶坟上土

### 题解：

一个很简单的签到题。计算过程中注意要使用 防止数据溢出。计算答案的方法若选择暴力累加，则造成超时 (时间复杂度为 ) ，需要使用等差数列求和公式减少运算量 ，时间复杂度为 。

可以发现，决策只和第一次拿行还是列有关，与第几行，第几列都无关。如果行数大于等于列数，则先拿列，反之先拿行。

假设 很大，易证得，只有前 次拿取是有效的，后面的拿取获得的酒均为 。

设酒桌大小的两个参数中 (即默认列 行，只是为了方便书写，毕竟参数顺序不影响解题)

设 次操作 里，奇数编号 (拿行) 的操作次数为 ，偶数编号 (拿列) 的操作次数为 。则有

拿行获取的酒的数量 。可以看出，这是一个首项为 ，末项为 ，公差为 的等差数列的总和。由等差数列求和公式可得， 。

若 ，则拿列获取的酒的数量 。

若 ，则拿列获取的酒的数量 。可以看出，这是一个首项为 ，末项为 ，公差为 的等差数列的总和。由等差数列求和公式可得， 。(而实际上也并不需要特判，推理出的式子 当 时其值也为 ，为了保持逻辑清晰度分类讨论)

所以最终输出结果即为 。由于 一定都不会不大于 ，所以运算过程并不会溢出 的范围。



附带检验 (**非严谨检验，只是代值计算**)：当 时，此时所有的酒都会被拿完，令 。







把 带入得：

原式



，代值检验完毕。