题解数据结构数学 OJ

OJ选题集

4FGR2025-05-232025-11-18

下列OJ平台仅代表题目信息的一个出处，不一定为OJ平台原创

每道题下面的均为其中关键的解题思路，题目大意并非完整题目，只出现解题思路中需要的变量。

（因此，基于测试用例t等无关变量将不会出现）

各题出处如下：

Codeforces
洛谷
力扣
码蹄集OJ(百度)
蓝桥杯
其他

Codeforces

Cherry Bomb

Codeforces Round 1020 div.3 C. Cherry Bomb Problem - C - Codeforces

tags: greedy math sortings *1000

题目大意

两个非负整数数组a与b，当我们称其互补时，当且仅当对于每个编号i，均有a_i+b_i= x, 其中x为一定值。我们希望数组a,b的每个元素均非负且不大于k,并且a与b是互补的。接下来，会给出n和k、完整的数组a，以及不完整的数组b，不完整的地方用-1补齐，请问有多少种填充b的办法满足我们的需要。

核心是如何确定互补值的值域，或者minb、maxb的值域

Fashionable Array

Codeforces Round 1026 Div.2 A. Fashionable Array

Problem - A - Codeforces

题目大意

给一个数组，问通过每次消灭任意一个元素，如何得到(max+min)%2==0的“时尚”数组。

对数组排序，可证明要么开始成功，要么只用从左往右，或者从右往左，找到第一个与 $max$ 或 $min$ 奇偶性不同的值，最大次数是遍历到 $min$ 或 $max$ （消除到只剩一个）。其中奇偶性不同的判断为 $(a+b)\%2=1$ ，结果对从左往右和从右往左搜索的结果取最小值。

Down with Brackets

Codeforces Round 1026 Div.2 B. Down with Brackets

Problem - B - Codeforces

tags: strings

题目大意

给你一个良好顺序的括号字符串s，你能任意破坏一个左括号和右括号，是否破坏完后能使顺序不良好。良好顺序具体定义如下：1.可以是空集。2.如果A顺序良好，则(A)顺序良好。3.如果A、B顺序良好，则AB顺序良好

我们发现如果存在同等级括号，如 $ABC$ 型，则从其中任意两个不同的括号集合如 $AB$ 中分别取括号，那么就破坏了两者的良好性，如果没有干扰，我们知道这不符合定义3，故不良好。

但这实现困难并且存在干扰：如果等级并非最高的，即外面有括号包住，如（$ABC$），我们发现取出的括号会被外面的括号补充，这是不行的。

事实上，我们发现只用判断是否第一个括号和最后一个括号相对应即可，真则不能，假则能。

Vladik and fractions

Codeforces Round 384 (Div. 2) C. Vladik and fractions

Problem - 743C - Codeforces

题目大意:

构造一组互不相同的 $x,y,z$ ,使得 $\frac{1}{x} + \frac{1}{y}+\frac{1}{z} = \frac{2}{n}$

$n = 1$ 时无解，其它则有通解 $n、n+1、n(n+1)$

通解证明简单，带入即可。

Cool Partition

Problem - C - Codeforces

核心：贪心+双map模拟区间

题目大意

将一个区间划为两个区间时，如前一区间的元素全部出现在后一区间，我们称这一次切割为有效切割。试问对于给定的区间，通过有效切割得到的区间个数的最大值。

这是一道贪心题，只要最先就能做有效切割就做(即让前一区间元素尽量少)，显然开始就把第一个元素当作第一个区间，然后这样遍历（我们设前一区间为mp1，后一区间为mp2，原数组为a）:

从 $mp1$ 中删去 $a[i]$，表示无需再检查这一元素
在 $mp2$ 中加入 $a[i]$ ，表示后一区间已有该元素
如果 $mp1$ 为空，说明 $mp2$ 已满足所有前一区间元素，立刻划分，并且 $mp2$ 成为下一 $mp1$，并清空 $mp2$。

Add 0 or K

Problem - 2134B - Codeforces

tags: constructive algorithms math number theory

题目大意

对给定数组a，正整数k，可做至多k次的操作：对每个a中元素可选择加0还是k，全部加上一轮算一次操作，最后使得gcd(a₁,a₂,...,a_n)>1 。

显然，可将题中问题转化为，使得

$gcd(a_1+c_1k,a_2+c_2k,...a_n+c_nk) >1,c_i\in[0,k]$

至少两种解法，这里分别举出构造和数论的两个例子:

构造 $c_i\equiv{a_i} \pmod{k+1}$ 即可，显然能使得最大公约数为 $k+1$
找到一个最小且非 $k$ 的因数的质数 $p$ 作为最大公约数，利用数论知识求解

\[c_i\cdot k+a_i \equiv 0 \pmod{p} \Longrightarrow c_i\equiv (-a_i \cdot k^{-1})\pmod{p}\]

解出 $c_i$ 即可。

Cake Assignment

Problem - C - Codeforces

tags: bitmasks constructive algorithms greedy

题目大意

起初，二人A、B分别有2^k个cake，它们可以任意次数地给对方自己的一半（仅当它们有偶数个cake时），请问若想使得A有x个cake，该如何分配？1表示A给B一半，2反之。

显然，我们把A、B所拥有的cake描述为状态 $(a,b)$ 。那么，这里的核心思路是：from the final state to backtrack。如果存在答案，那么显然我们期望的最终状态是 $(x,2^{k+1}-x)$ 。我们从最终状态开始，如果当前A的数大于B的数，那么说明，上一步操作中，是B把数分一半给了A；反之亦然。注意答案和得到的是顺序相反的，可使用栈存储。

洛谷

[绿]开关

[P3870 TJOI2009] 开关 - 洛谷

tags: 线段树分块

题目大意

有n盏灯排一排，能做两种操作,指定一个区间[a,b]，即可以要求输出区间打开的灯数，也可以改变该区间灯的状态（开的关，关的开），灯泡在初始时是关着的。

n,m 表示灯数与操作数

c表示操作种类（c=0为第一种，c=2为第二种）,a,b,表示指定区间

这是一个线段树的问题，线段树如何实现这里不做叙述，可见数据结构-线段树 | 4FGR の Blog

关键是如何处理操作1，即如何改变灯泡状态。

考虑到灯泡只有两种状态，要么开，要么关，由于我们要求开着的灯泡数量，于是置开为1，关为0，对区间做操作1，实际上是对区间每个编号的值异或1的结果(1异或1为0，由开为观；0异或1为1，由关为开)，注意更新lazy标记的办法也是自异或1(lazy初始为0，01表示是否区间需要翻转)。

[黄]跳石头

[P2678 NOIP 2015 提高组] 跳石头 - 洛谷

tags: 贪心二分

核心：二分答案

题目大意

举办跳石头大赛，从起点到终点的距离是S，其中有N个石头，第i个石头离终点的距离为a_i，举办方打算移除M个石头，求出可实现的最短跳跃距离的最大值。

我们看到，答案一定确定在 $[1,S]$, 并且问题是求最小值的最大值，这时候我们求可以用二分答案来求解。

二分答案，顾名思义，依靠对答案的二分解出最后的答案，因此答案序列得是有序的且有界限，一般可用来解最小值的最大值，或者最大值的最小值。我们用 $judge$ 函数每次评判中间值 $mid$，如果成功，说明这个答案是合法解，最优解要么是它本身，要么就在它右边，若不合法，答案一定在它左边。随时用 $ans$ 跟进合法的 $mid$，显然答案就是最后一个判定为合法的 $mid$。

对于这道题而言,（由于我们用 $l$ , $r$ 表示左右，因此文中的起点到终点的距离用s表示），答案一定在区间 $[1,s]$ 上，我们每次取中间值 $mid$，放入评判函数中。$judge$ 函数如何设置呢？我们遍历每个石头的距离，如果这个距离小于 $mid$，显然这块石头需要被捡走(不然不满足最短距离为 $mid$ 的条件)，记录石头被捡走的次数，如果这个次数比 $m$ (我们本应捡走的)要多，说明不是合法解，否则是合法解。

[橙]小A的糖果

P3817 小A的糖果 - 洛谷

tags: 模拟贪心

题意：对多盒糖果，每次任意吃其中一颗糖果，使得相邻盒子中的糖果数不超过x，求出最少次数。

贪心问题，将问题拆分成子问题考虑，使得子问题最优的同时，尽力方便后续子问题。这里从第一个非头结点开始，先减当前位，不够再减前一位即可。

[橙]Subsequences Summing to Sevens S

[P3131 USACO16JAN] Subsequences Summing to Sevens S - 洛谷

tags: 前缀和

使前缀和数组对 $7$ 取模，这样余数相同的数之间组成的区间和均可被 $7$ 整除，记录余数第一次出现的下标和最后一次的下标，注意对余数 $0$ 有特殊处理。

[橙]最大正方形

P1387 最大正方形 - 洛谷

tags: DP 枚举前缀和

有对应的三种做法

通过二维前缀和，利用容斥原理求出区域和是否为边长平方，并逐步搜索，时间复杂度为$O(nm\times\min(n,m))$
二分答案，由于要求出最大边长 $ans$，大于$ ans$ 肯定不存在，小于 $ans$ 的一定符合条件。那么，区间就锁定在 $[1,min(n,m)]$ , 之后依据暴力即可。同时可结合二维前缀和，将时间复杂度优化至 $O(nm\times\log_2{\min(n,m))}$
使用动态规划DP，状态转移方程为

\[dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1\]

当 $a[i][j]$ 等于 $1$ 时，否则 $dp[i ][j]$为 $0$ 。$dp[i][j]$ 表示以 $(i,j)$ 为正方形的右下顶点所能组成的最大正方形，借由该点的左边、上边、对角点各自的最大三角形，可以组成其自身的最大三角形。时间复杂度最小，为$O(nm)$。

[绿]贴海报

[P3740 HAOI2014] 贴海报 - 洛谷

tags: 线段树、离散化、枚举

我的解法：参照线段树的实现，结点代表区间被贴海报的编号，由于在下传懒标记时也会清空本身结点的值，因此从有结点的编号到根节点的路径上的其他结点的值全是 $0$ ，$0$ 代表着结点表示的区间由多个编号海报组成，或者是未被粘贴（这种情况说明其祖先中一定有一个有值）。显然，之后查询整个区间时，遇到非 $0$ 结点就可以用哈希记录，第一次遇到的 $ans$++ 即可（如用map记录，直接输出mp.size()亦可）
使用线段树+逆序染色。显然，由于染色不能修改已被染色的区域，既然我需要的是最后贴上的海报，那么逆序染色即可了。成功染色一个就 $ans$++ ，否则说明已被后面的海报覆盖。结点之间关系如下:

\[tree[p]=tree[p*2]\&\&tree[p*2+1]\]

由于染色用 $tree[p]=1（或true）$ 表示，这个式子表达的意思是，是否两个子区间均被染色，如果是，显然整个 tree[p] 代表的整个区间已经染色完了。
浮水法。
珂朵莉树

[蓝]矿洞：坍塌

P4979 矿洞：坍塌 - 洛谷

题目大意

对于给出的一字符串s，仅存在三种三种元素：{A,B,C}，对于此字符串，我们想要做如下两种操作： 1. 当flag = A时，给出x,y,op,修改区间[x,y]的所有元素为op。 2. 当flag = B时，给出x,y,查询区间是否"合法" 一个区间合法的标志是：[x,y]区间的元素均相同，且第x-1号元素和第y+1号元素并不相同

这里给出珂朵莉树的解法，实现上采用 `std::set` ，保留经典操作 `split` 和`assign` ，此时如果直接暴力查询，则能得到90分，剩下10分考虑算法优化。

显然，珂朵莉树适用于数据集随机的情况，但此题显然B型操作过多。我们知道当存在大量不同区间时，珂朵莉树从理想下的 $O(mloglogn)$ 趋近于平方级。考虑题重要的一点：元素仅存在三种。说明大量不同区间实际上是可以合并的，比如assign 操作后可能新区间能与邻居区间合并，于是选择在assign 采用 union 操作。虽然时间仍差了一步，但 union 带来的惊喜是，显然相同值的连续区间一定能被一个结点表示，那么就可以优化查询操作（这是最重要的），即得到大于 x 的第一个结点的前驱 itl，大于 y 的第一个结点的前驱 itr ，那么显然itl 和 itr 是一定包含 l 和 r 的。于是我们知道:

itl!=itr ，说明 $[l,r]$ 区间值不全相同，返回 $false$
itl-l < l && itr>r 说明 $x-1$ 和 $y+1$ 的值相同，非法，返回 $false$
如果结点只包含 $[l,r]$ 检查 $prev(itl) == next(itr)$ ，如果成立，非法，返回 $false$
其余返回 $true$

力扣

[困难]接雨水

42. 接雨水 - 力扣（LeetCode）

题目大意

给定一组宽度为1的柱子高度，问下雨之后这一组柱子能接多少水？

三种方法

我的做法是双指针，但由于 $i!=j$ 时会多余遍历剩余元素，并非双指针的最优解（虽然过了）

可不看

设立双指针 $i,j$ ，$j$ 找出第一个比 $i$ 大的值，并结算，再让 $i=j$ ，继续搜索。如果未找到，就记录其中最大高度的位置 $maxp$ ，结算，并让 $i=maxp$ 。显然，$loop$ 的条件是 $i<n-1$

双指针

动态规划

从左边开始扫描一边到 $i$ 前的最大值，同理从右边再扫描一边，两边合起来结算即可。

单调栈

[困难]执行操作后元素的最高频率 II

3347. 执行操作后元素的最高频率 II - 力扣（LeetCode）

题目大意

每个数只能被做一次这样的操作：加上一个范围为[-k,k]的一个数。对于给定的操作数numOperations，问如何使得在所有情况中，数组中的元素的最高频率最大。

元素的频率，指的是它在数组中出现的次数。最高频率的元素，是数组中出现次数最多的元素。

差分法

显然，我们可以利用差分性质得到每个数（包含 $nums[i]+c,c\in[-k,k]$ ）可能实现的频率。

同时，由于有操作次数的限制，如果答案对应的元素在原数组出现的话，消耗的操作次数显然是 $最大频率-原出现次数$ 。因此这里用 cnt 记录每个元素的出现次数。

具体实现如下：

构造差分数组 diff ，所有元素初始化为 $0$
遍历所有元素，使 $diff[nums[i]-k]$ 增加 $1$ ，$diff[nums[i]+k+1]$ 减少 $1$
对差分数组做前缀和操作，得到每个数的可能的最大出现次数 diff[nums[i]]
对于所有的出现次数，比较 numOperation+cnt[nums[i]] 和 diif[nums[i]] ，答案取最大值

注意：

由于数组 $nums$ 的元素范围较大，这里不再使用差分数组，而通过 map<int,int> 类型构造差分序列，由于 $nums[i]$ 存在本来就有的次数，遍历时要注意到它，因此如果其未被插入，就要插入 $nums[i]$ 且值为 $0$ 。（由于可能存在 $nums[i]+c==nums[k]$ ，所以要判断其是否已经插入）

[困难]计算子数组的 x-sum II

3321. 计算子数组的 x-sum II - 力扣（LeetCode）

码蹄集OJ(百度)

[青铜]房间打扫

码蹄杯2022 MC0102房间打扫

码蹄集OJ-房间打扫

核心：寻找等价关系

实际上，最多打扫干净的行数为有着相同字符串，或者说有相同元素的行数的最大值。

[黄金]项链

码蹄杯2022 MC0104项链

码蹄集OJ-项链

核心：数学思维

碰巧做对的思路

每次一最小一最大排列，最后计算美观值。这个实际上是最佳序列的其中一种，它恰好实现了大值加2次，小值减两次，以及个数为奇数情况下的第n/2大个数恰好一加一减被抵消了而已。

我们知道，这道题如果没有绝对值的限制，显然总和为 $0$ ，因为每个数都恰好地被做了一对加减法。在加了绝对值的情况下，对于美观值答案 $ans$，我们显然期望两次加的都是更大的，两次减的都是最小的，因此最佳期望的答案是

\[ans = 2*|最大的n/2个数总和-最小的n/2个数总和|\]

这个最佳序列是可以得到的，只要保证这两队数奇偶位置分别放置即可，即保证大值左右两旁有小值，这样大值就被加了两次。

注意，当个数 $n$ 为奇数时，对于第中间大数 $a_{n/2}$，由于比它大的数与比它小正好匹配，即比它大的数都加了两次，比它小的数都减了两次，可怜的 $a_{n/2}$ 只能本身做一次加减法，因此被抵消掉了。

[青铜]白日梦

码蹄杯2022-MC0112白日梦Ⅰ

核心：前缀极值的动态维护

这道题的核心思想非常巧妙，由于我们只做一次来回兑换，显然我们想要换英镑时汇率是大的，这样我们只要在遍历前记录当前最大值并更新 $ans$ 和最大值 $mx$ 即可。

[白银]水往低处流

码蹄杯2022 MC0116水往低处流

码蹄集OJ-水往低处流

核心：寻找等价关系

题目大意

有一 n*n 的梯田，可往格子里浇上一桶水，同时它和比它严格低的格子会是“湿润的”，问至少需要多少桶水，使得梯田完全湿润。

一道非常巧妙的题，我们要记录需要多少桶水，事实上等价于有多少格子要是“湿润的”，这又等价于有多少格子的邻居没有比它高的，这样不会有水流向它，它只能用上一桶水，并为邻居供水。也可以反过来想，有多少格子可以通过邻居供水（即有邻居比它高，会有水流向它），再用 $n*n$ 减去即可。

[白银]子集统计

码蹄杯2022 MC0126 子集统计

码蹄集OJ-子集统计

核心：位运算、排列组合

有意思的思维题，$a \& c=c$，意味着凡是 $a$ 有 $1$ 的地方都可以随便填，而 $a$ 有 $0$ 的地方只可以填 $0$（因为与操作要求同一位上两个均为 $1$ 才能为 $1$），同理，$c\&b=b$为相反情况，如果 $b$ 有 $1$ 的地方只能填 $0$，如果之前标记了只能填 $0$，那么显然冲突，无解并退出。否则，用 $n$ 记录下可以随便填的位数，一位有两种状态 $0$ 与 $1$，显然答案为 $pow(2,n)$。

[白银]函数的幂Ⅱ

码蹄杯2022 MC0136函数的幂Ⅱ 码蹄集OJ-函数的幂Ⅱ

核心：找规律

题目大意

对于 f(a,b) 存在a=1时，f(a,b) = c*b+d, 否则 f(a,b) = f(a-1,f(a-1,b))。问对给出的a、b、c、d的最终答案的个位数。其中 a 可能高达1e6

显然，函数 $f(a,b)$ 所需要的计算次数是 $2^{a-1}$ 的级别，这是我们所不能承担的，但题目要求的是个位数，我们可以发现这个个位数一定是有规律的，最多有10个不同的数，但注意，可能最开始的几个数并不在循环之中。我们可以使用记忆化搜索，使用 dp\[1000000+10]\[10] 记录出现的结果，从而避免指数级的递归。当然，如若数据实在太大以至于无法存储，我们应该找出其中的规律。

事实上，还可以通过迭代实现，因为是求个位数，我们知道其实 $f(a,b)$ 总能化成 $C_ix+D_i$ 的形式，由于我们只求个位数， $C$ 、$D$ 对其的影响也只有其个位上的数字，每次 $a$ 上升 $1$ 都是倍增的，于是我们可以这样更新：

\[C_{i+1} = C_i*C_i \mod10\]

\[D_{i+1} = (C_i*D_i+D_i) \mod 10\]

[白银]快速计算

码蹄杯2022 MC0152快速计算

码蹄集OJ-快速计算

核心：合并多项操作、预处理

这是比较难的白银题了。要两个要处理的点，一个是所有操作可变成一个线性操作 $Ax+b$，这里无需赘述。但这远远不够——这些数据也开得太大了吧。对总 $q$ 个还要做 $p$ 次操作，还与变量 $x$ 有关！我们发现，$p$ 次操作仍只需一阶 $x$，本来可以化成 $(a^n)x + 一个等比数列和$，但这样我又要搞快速幂和费马小定理，太麻烦了。但由于乘数和加数与 $x$ 无关，只随 $p$ 变化而变化，可以算出各个 $p$ 时的 $mul$ 与 $add$，但难不成我还要根据 $p$ 动态调整？我一看 $p$ 最多 $1e6$，管你多大直接预处理，这样我们便得到了最终答案。

[黄金]水渠规划

码蹄杯2022 MC0154水渠规划

码蹄集OJ-水渠规划

核心：数学

若有线段 $AB$，和点 $P$，则 $P$ 到线段 $AB$ 的最近距离为：

\[ Dis(P, AB) = \begin{cases} |AP|, & \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} < 0 \\ \frac{|\vec{AP} \times \vec{AB}|}{|\vec{AB}|}, & 0 \le \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} \le 1 \\ |BP|, & \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} > 1 \end{cases} \]

当 $\frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} < 0$，即 $P$ 的垂足不在线段上，投影点在 $A$ 左边，则到线段的最近距离为 $|AP|$。
当 $\frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} > 1$，即 $P$ 的垂足也不再线段上，投影点在 $B$ 右边，则最近距离为 $|BP|$。
否则，投影点在 $AB$ 之间，则到线段的最近距离就是到直线 $AB$ 的最近距离，可以通过计算得到。

$\vec{AP} \times \vec{AB}$ 的值恰好为三角形 $ABP$ 面积的两倍，除以底边 $AB$ 的长度，即为高的长度。

剪刀石头布

MC0176剪刀石头布

码蹄集OJ-剪刀石头布

[黄金]世界警察

MC0204 世界警察

码蹄集OJ-世界警察

核心：双指针+动态维护最后位置

用map或者哈希表(unordered_map) 动态维护元素从0到r最后出现的位置，如果已有重复元素并且包含在区间(通过l<=mp[a[i]]判断)，则立马结算(注意区间应为r-1)，并更新map，每次循环结束注意更新ans。

[黄金]未来战争

MC0221未来战争

码蹄集OJ-未来战争

核心: 合并区间|差分

利用差分性质，每次让差分数组 $b$ 中的 $b_l$, $b_{r+1}$ 分别加 $1$ 和减 $1$ ，使得对差分数组做前缀和后，凡是充能区间都为1，最后用 $ans$ 记录最长连续 $1$ 即可。

蓝桥杯

[困难]选数异或

0选数异或 - 蓝桥云课

给定一个长度为 n 的数列 $A_1,A_2,⋯,A_n$ 和一个非负整数 $x$ , 给定 $m$ 次查询, 每次询问能否从某个区间 $[l,r] $中选择两个数使得他们的异或等于 $x$

核心有两点:

a异或b = x 说明 a异或x = b
对于数组b，时刻记录最近的异或对中最远的那个编号，这个“最近”指的也是这些远端中最近的。这样对于区间的处理，只用判断 $b[r]$ 是否大于 $l$ 即可

其他

学校

贪吃蛇

这是我们学校的题 T606586 贪吃蛇

原题应该是棋盘哈密尔顿路径问题 （据AI）

由于是内部校赛的题，链接无用，下面给出题目

贪吃蛇问题

在贪吃蛇游戏中，玩家能够操控一条蛇，它会不停前进，且只能向上下左右四个方向运动，现在,给你的挑战是：给定一个n∗n (1≤n≤5000)的棋盘和蛇的起点坐标(x,y)，请判断是否存在一种方式，可以使得蛇可以不重复地走过棋盘上的所有的格子（忽略蛇的长度）。

这是一道特判题，事实上，只要是偶数阶方阵对任意出发点一定有解，对于奇数阶方阵，出发点只有一种无解情况：abs(x-y)%2 == 1。

AC代码如下:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int x,y,n;
    cin >> n >> x >> y;
    if(n%2==0) cout <<"YES";
    else if(n%2==1 && abs(x-y)%2==1){
        cout << "NO";
    }else cout << "YES";
}

逃离方块: 磨坊

同上 T606553 逃离方块: 磨坊

题目大意

为了提取黑色方块，猫头鹰先生成功将劳拉传送了过来。但是，为了将机器启动，他们还需要输入密码, 机器下方有一串由n位字母构成的文本，而密码就是这段文本中最长的一段连续非回文子文本$s$的长度。请你帮乌鸦先生得到启动机器的密码。

假定s的长度为m

这道题的思路是：先看是否 $s$ 为回文串，显然，如果不是的话输出 $m$ ，而其实别的判断也十分简单。判断是否 $s$ 所有元素相同，是则返回 $0$ ，否则返回 $m-1$，注意单字母如 $a$ 本身也是回文串，作者当时搞错成返回 $1$，吃了好多罚时qaq。

之所以如此，是因为我们可以证明，当 $s$ 为回文串并非所有元素相同时，只用左右两边仍减去一个就为非回文串。首先，显然 $s_1$ 和 $s_m$ 是相同的，如果仍减去一个还要是回文串，那么 $s_1$ 和 $s_m-1$ , $s_2$ 和 $s_{m-2}$…$s_{m/2}$ 和 $s_{m/2-2}$ 就得相同，显然只有 $s$ 所有元素相同才行，因为我们可以由此得到这样一条式子 $s_1 = s_m = s_{m-1} = s_2 = s_{m-2} = s_3...$ 如此循环往复。

赛洛斯星光灯塔

T606530 赛洛斯星光灯塔 - 洛谷

题目大意

对给定的矩阵，起初全为暗，可设置翻转点，使得翻转点上下左右

找出规律即可，事实上，每一层都是连续两个翻转点相隔4格出现，再进入内层（n-4），因此采用递归策略，有两种退出条件，$n==2$ 与 $n==4$ 当 $n/2$ 为奇数时，最小层为 $n==2$ 的情况。反之，最小层为 $n==4$ 的情况。同时注意到翻转点个数为 $n*(n-1)$ 。

#include<bits/stdc++.h>

using namespace std;


void f(long long n,int t){
    if(n == 2){
        cout << 1+t << ' ' << 1+t << endl;
        cout << 1+t << ' ' << 2+t << endl;
    }
    else
        if((n/2) &1){
            int i=1,j=2;
            while(j<=n){ //第一排
                cout << i+t << ' '<< j+t-1  << endl;
                cout << i+t << ' '<< j+t  << endl;
                j+=4;
            }
            i = 5;
            j = n;
            while(i<=n-1){ //最后一列
                cout << i+t-1 << ' '<< j+t  << endl;
                cout << i+t << ' '<< j+t  << endl;
                i+=4;
            }
            i = n;
            j = n-3;
            while(j>=3){ //最后一排
                cout << i+t << ' '<< j+t+1  << endl;
                cout << i+t << ' '<< j+t  << endl;
                j-=4;
            }
            i = n-2;
            j = 1;
            while(i>=4){ //第一列
                cout << i+t << ' '<< j+t  << endl;
                cout << i+t+1 << ' '<< j+t  << endl;
                i-=4;
            }
            f(n-4,t+2);
        }else{
            int i=1,j=3;
            while(j<=n-1){ //第一排
                cout << i+t << ' '<< j+t-1  << endl;
                cout << i+t << ' '<< j+t  << endl;
                j+=4;
            }
            i = 4;
            j = n;
            while(i<=n){ //最后一列
                cout << i+t-1 << ' '<< j+t  << endl;
                cout << i+t << ' '<< j+t  << endl;
                i+=4;
            }
            i = n;
            j = n-4;
            while(j>=4){ //最后一排
                cout << i+t << ' '<< j+t+1  << endl;
                cout << i+t << ' '<< j+t  << endl;
                j-=4;
            }
            i = n-1;
            j = 1;
            while(i>=3){ //第一列
                cout << i+t+1 << ' '<< j+t  << endl;
                cout << i+t << ' '<< j+t  << endl;
                i-=4;
            }
            if(n>4)
            f(n-4,t+2);
        }
}

int main(){
    int t;
    cin >> t;
    while(t--){
        long long n;
        cin >> n;
        cout << n/2*(n/2+1) << endl;
        f(n,0);
    }
}
/*以下为可视化代码
#include<bits/stdc++.h>

using namespace std;
const int N = 1e4;
char a[N][N];

void f(long long n,int t){
    if(n == 2){
        a[1+t][1+t] = '*';
        a[1+t][2+t] = '*';
    }
    else
        if((n/2) &1){
            int i=1,j=2;
            while(j<=n){ //第一排
                a[i+t][j+t-1] = '*';
                a[i+t][j+t] = '*';
                j+=4;
            }
            i = 5;
            j = n;
            while(i<=n-1){ //最后一列
                a[i+t-1][j+t] = '*';
                a[i+t][j+t] = '*';
                i+=4;
            }
            i = n;
            j = n-3;
            while(j>=3){ //最后一排
                a[i+t][j+t+1] = '*';
                a[i+t][j+t] = '*';
                j-=4;
            }
            i = n-2;
            j = 1;
            while(i>=4){ //第一列
                a[i+t][j+t] = '*';
                a[i+t+1][j+t] = '*';
                i-=4;
            }
            f(n-4,t+2);
        }else{
            int i=1,j=3;
            while(j<=n-1){ //第一排
                a[i+t][j+t-1] = '*';
                a[i+t][j+t] = '*';
                j+=4;
            }
            i = 4;
            j = n;
            while(i<=n){ //最后一列
                a[i+t-1][j+t] = '*';
                a[i+t][j+t] = '*';
                i+=4;
            }
            i = n;
            j = n-4;
            while(j>=4){ //最后一排
                a[i+t][j+t+1] = '*';
                a[i+t][j+t] = '*';
                j-=4;
            }
            i = n-1;
            j = 1;
            while(i>=3){ //第一列
                a[i+t+1][j+t] = '*';
                a[i+t][j+t] = '*';
                i-=4;
            }
            if(n>4)
            f(n-4,t+2);
        }
}

int main(){
    int t;
    cin >> t;
    while(t--){
        long long n;
        cin >> n;
        //cout << n/2*(n/2+1) << endl;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                a[i][j] = 'o';
            }
        }
        f(n,0);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
    }
}
*/