A
本題描述了一個最優路徑規劃問題的解法，核心思路是利用數軸上區間覆蓋的特性，將問題簡化為兩個端點的訪問問題。以下是關鍵點的詳細解析：
核心觀察
-
區間覆蓋特性
- 給定的位置數組?
x1, x2, ..., xn?是嚴格遞增的（即?x1 < x2 < ... < xn）。 - 在數軸上，若要訪問區間?
[x1, xn]?內的所有整數點，只需從起點移動到?x1?或?xn，再移動到另一個端點，即可覆蓋中間的所有位置。
- 給定的位置數組?
-
最優路徑選擇
-
從起點?
s?出發，訪問?x1?和?xn?的路徑只有兩種可能：- 路徑 A：
s → x1 → xn
總步數：|s - x1| + |xn - x1| - 路徑 B：
s → xn → x1
總步數：|s - xn| + |xn - x1|
- 路徑 A：
-
兩種路徑的共同部分是?
|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：
cnt[l] ≥ 3
選擇第二個出現的l作為b，其前后的字符分別構成a和c。 - 條件 2：
cnt[l] = 2且s的首尾字符不全為l
選擇非首尾位置的l作為b，確保a和c非空。
- 條件 1：
- 統計每個字符在
算法實現
貪心算法：通過局部最優選擇（優先考慮|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;
}
