A

本题描述了一个最优路径规划问题的解法，核心思路是利用数轴上区间覆盖的特性，将问题简化为两个端点的访问问题。以下是关键点的详细解析：

核心观察

区间覆盖特性
- 给定的位置数组 x1, x2, ..., xn 是严格递增的（即 x1 < x2 < ... < xn）。
- 在数轴上，若要访问区间 [x1, xn] 内的所有整数点，只需从起点移动到 x1 或 xn，再移动到另一个端点，即可覆盖中间的所有位置。
最优路径选择
- 从起点 s 出发，访问 x1 和 xn 的路径只有两种可能：
  1. 路径 A：s → x1 → xn
    总步数：|s - x1| + |xn - x1|
  2. 路径 B：s → xn → x1
    总步数：|s - xn| + |xn - x1|
- 两种路径的共同部分是 |xn - x1|（即区间长度），因此只需比较起点到两个端点的距离，取较小值。

公式推导

最优解的公式为：

min(|s - x1|, |s - xn|) + (xn - x1)

解释：

min(|s - x1|, |s - xn|)：选择起点 s 到区间左端点 x1 或右端点 xn 的较短距离。
xn - x1：区间的长度，即覆盖整个区间所需的最小步数。

算法实现

该算法的时间复杂度为 O(1)，因为只需读取输入并计算两个端点的位置。具体步骤：

读取输入的起点 s 和位置数组 x。
计算 x1（数组第一个元素）和 xn（数组最后一个元素）。
代入公式 min(|s - x1|, |s - xn|) + (xn - x1) 计算结果。

代码

#include<bits/stdc++.h>
using namespace std;
void solve(){int n,s;cin>>n>>s;int a[n+1];for(int i=1;i<=n;i++){cin>>a[i];}int l=min(abs(a[1]-s),abs(a[n]-s))+a[n]-a[1];cout<<l<<endl;
}
int main(){int t;cin>>t;while(t--)solve();return 0;
}

B

简化问题

如果存在满足条件的分割方案，则必然存在一种方案使得中间字符串b的长度为 1。
证明：假设存在分割s = a + b + c，其中|b| ≥ 1。选择b中的任意字符x，将b拆分为b = b_prefix + x + b_suffix，则新的分割为：
plaintext
```
a' = a + b_prefix  
b' = x  
c' = b_suffix + c  
```
这种转换不改变分割的有效性，因此只需考虑|b| = 1的情况。

字符出现次数的影响
- 统计每个字符在s中出现的次数cnt[l]。
- 若存在某个字符l满足以下条件之一，则存在有效分割：
  1. 条件 1：cnt[l] ≥ 3
    选择第二个出现的l作为b，其前后的字符分别构成a和c。
  2. 条件 2：cnt[l] = 2且s的首尾字符不全为l
    选择非首尾位置的l作为b，确保a和c非空。

算法实现

贪心算法：通过局部最优选择（优先考虑|b|=1）达到全局最优解，避免枚举所有可能的分割方式。该算法的时间复杂度为 O(n)，具体步骤：

统计字符频率
遍历字符串s，统计每个字符的出现次数cnt[l]。
检查条件 1
若存在任何字符l的出现次数≥3，直接返回 "Yes"。
检查条件 2
对于每个出现两次的字符l，检查：
- 若s的首字符或尾字符不等于l，则返回 "Yes"。
返回结果
若所有条件均不满足，返回 "No"。

代码

#include<bits/stdc++.h>
using namespace std;
void solve(){int n;cin>>n;string s;cin>>s;int cnt[30]={0};for(int i=0;i<s.length();i++){cnt[s[i]-'a']++;}bool flag=0;for(int i=0;i<26;i++){if(cnt[i]>2)flag=1;else if(cnt[i]==2&&(s[0]-'a'!=i||s.back()-'a'!=i))flag=1;}if(flag)cout<<"YES"<<endl;else cout<<"NO"<<endl;
}
int main(){int t;cin>>t;while(t--)solve();return 0;
}

C

矩阵操作后的最小可能最大值分析

这段文字描述了一个矩阵操作问题的解法，核心思路是通过分析矩阵中最大值的分布，确定执行一次操作后可能的最小最大值。关键点如下：

核心观察

答案的可能范围
- 矩阵的初始最大值为 mx。执行一次操作后，答案只能是 mx-1 或 mx。
- 证明：无论选择哪一行 r 和列 c 进行操作，矩阵中的其他元素不会减少，因此最大值不可能小于 mx-1。
何时答案为 mx-1？
- 当且仅当存在一个位置 (r, c)，使得所有值为 mx 的元素都位于第 r 行或第 c 列时，答案为 mx-1。
- 解释：选择这样的 (r, c) 进行操作后，所有 mx 元素都会减 1，从而新的最大值为 mx-1。

算法实现步骤

预处理
- 遍历矩阵，记录：
  - mx：矩阵中的最大值。
  - cnt_mx：mx 出现的总次数。
  - r[i]：第 i行中 mx 出现的次数。
  - c[j]：第 j 列中 mx 出现的次
检查条件
- 对于每个可能的位置 (i, j)，计算：
```
count = r[i] + c[j] - (a[i][j] == mx ? 1 : 0)
```
  其中，r[i] + c[j] 是第 ri行和第j列中 mx 的总次数，但如果 a[r][c] 是 mx，则被重复计算了一次，需要减去 1。
判断结果

如果存在 (i,j) 使得 count == cnt_mx，则答案为 mx-1；否则为 mx。

错解（数组开的过大）：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;  //数组过大
int a[N][N];
void solve(){int n,m;cin>>n>>m;int mx=0,cnt_mx=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];if(a[i][j]>mx){mx=a[i][j];cnt_mx=1;}else if(a[i][j]==mx) cnt_mx++;}}int r[n]={0},c[m]={0};for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]==mx){r[i]++;c[j]++;}}}int flag=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(r[i]+c[j]-(a[i][j]==mx?1:0)==cnt_mx) flag=1;}}cout<<mx-flag<<endl;
}
int main(){int t;cin>>t;while(t--)solve();return 0;
}

正确代码

根据题目约束 1≤n⋅m≤1e5，建议使用动态分配数组定义数组a,同时行数组和列数组使用变量（n，m）定义数组的大小。

使用vector嵌套来定义动态大小的矩阵

#include <vector>// 定义n行m列的矩阵，初始值为0
int n, m;
cin >> n >> m;
vector<vector<int>> matrix(n, vector<int>(m, 0));// 访问元素：matrix[i][j]
matrix[0][0] = 10;  // 第一行第一列赋值为10

解释：

vector<vector<int>> matrix(n, ...)：创建一个包含n个元素的外层 vector，每个元素是一个内层 vector。
vector<int>(m, 0)：每个内层 vector 包含m个元素，初始值为 0。

总代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){int n,m;cin>>n>>m;int mx=0,cnt_mx=0;vector<vector<int>>a(n,vector<int>(m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];if(a[i][j]>mx){mx=a[i][j];cnt_mx=1;}else if(a[i][j]==mx) cnt_mx++;}}int r[n]={0},c[m]={0};for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]==mx){r[i]++;c[j]++;}}}int flag=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(r[i]+c[j]-(a[i][j]==mx?1:0)==cnt_mx) flag=1;}}cout<<mx-flag<<endl;
}
int main(){int t;cin>>t;while(t--)solve();return 0;
}