思路：

1. 二分查找：

   • left = 1（最小可能距離），right = L（最大可能距離）。

   • 每次取?mid = (left + right) / 2，判斷是否可以通過增設 ≤?K?個路標使得所有相鄰路標的距離 ≤?mid。

2. 貪心驗證：

   • 遍歷所有相鄰原始路標，計算它們之間的?gap。

   • 對于每個?gap，計算需要插入的路標數?(gap - 1) / mid。

   • 如果總增設數?required ≤ K，則?mid?可行，嘗試更小的?mid；否則嘗試更大的?mid。

3. 輸出答案：

   • 最終?ans?即為最小的“空曠指數”。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int L, N, K;cin >> L >> N >> K;vector<int> markers(N);for (int i = 0; i < N; i++) {cin >> markers[i];}int left = 1;  // 最小可能距離int right = L;  // 最大可能距離int ans = L;// 二分查找最小的“空曠指數”while (left <= right) {int mid = (left + right) / 2;int required = 0;  // 需要增設的路標數量// 計算需要增設多少路標才能讓所有間隔 ≤ midfor (int i = 1; i < N; i++) {int gap = markers[i] - markers[i - 1];required += (gap - 1) / mid;}if (required <= K) {ans = mid;right = mid - 1;  // 嘗試更小的“空曠指數”} else {left = mid + 1;  // 需要更大的“空曠指數”}}cout << ans << endl;return 0;
}

?
?

思路：

1. backtrack函數：這是遞歸回溯的核心函數。

   • ：n是目標美味程度，current是當前配料組合，sum是當前組合的總和，index是當前處理的配料索引。

   • 當處理完所有10個配料（index == 10），檢查總和是否等于n，如果是，則保存當前組合。

   • 對于當前配料，嘗試1、2、3克，遞歸處理下一個配料。通過剪枝條件提前終止無效的遞歸路徑。

#include <iostream>
#include <vector>
using namespace std;vector<vector<int>> solutions;  // 存儲所有解決方案void backtrack(int n, vector<int>& current, int sum, int index) {if (index == 10) {if (sum == n) {solutions.push_back(current);}return;}// 嘗試1、2、3克for (int i = 1; i <= 3; ++i) {if (sum + i > n) continue;  // 剪枝：總和超過n，跳過// 剩下的配料即使全選1克也無法達到n，剪枝if (sum + i + (10 - index - 1) > n) continue;current[index] = i;backtrack(n, current, sum + i, index + 1);}
}int main() {int n;cin >> n;vector<int> current(10);  // 當前組合backtrack(n, current, 0, 0);cout << solutions.size() << endl;for (const auto& sol : solutions) {for (int i = 0; i < 10; ++i) {cout << sol[i] << " ";}cout << endl;}return 0;
}

正則表達式?

基本概念

• 字符組：用方括號?[]?表示，用于匹配方括號內的任意一個字符。例如，[abc]?可以匹配?a、b?或?c?中的任意一個字符。
• 量詞：用于指定前面的字符或字符組出現的次數。常見的量詞有?*（零次或多次）、+（一次或多次）、?（零次或一次）、{n}（恰好?n?次）、{n,}（至少?n?次）、{n,m}（n?到?m?次）。例如，a*?表示匹配零個或多個?a，a{2,4}?表示匹配?2?到?4?個?a。
• 元字符：具有特殊含義的字符，如?^?表示匹配字符串的開頭，$?表示匹配字符串的結尾，.?表示匹配除換行符以外的任意一個字符。例如，^a?表示以?a?開頭的字符串，a$?表示以?a?結尾的字符串。
• 轉義字符：用反斜杠?\?表示，用于轉義元字符，使其失去特殊含義，而表示其本身。例如，\.?表示匹配字符?.，\\?表示匹配字符?\。

常用操作

• 匹配：使用正則表達式來檢查一個字符串是否符合特定的模式。例如，判斷一個字符串是否是有效的電子郵件地址，可以使用正則表達式?^\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$。
• 查找：在一個字符串中查找符合正則表達式模式的子串。例如，在一篇文章中查找所有的電話號碼，可以使用正則表達式?\d{3}-\d{8}|\d{4}-\d{7}。
• 替換：將匹配到的字符串替換為指定的內容。例如，將字符串中的所有數字替換為?*，可以使用正則表達式?\d?和替換字符串?*。
• 分割：根據正則表達式的模式將字符串分割成多個子串。例如，將一個逗號分隔的字符串分割成數組，可以使用正則表達式?,。

示例

• 匹配手機號碼：^1[3-9]\d{9}$。這個正則表達式表示以?1?開頭，第二位是?3?到?9?中的任意一個數字，后面跟著?9?個數字。
• 匹配身份證號碼：^\d{17}[\dXx]$。表示由?17?位數字和最后一位數字或?X（或?x）組成。
  ?

元字符	說明
.	匹配任意單個字符（除換行符?\n）
^	匹配字符串的開頭
$	匹配字符串的結尾
*	匹配前面的字符0次或多次
+	匹配前面的字符1次或多次
?	匹配前面的字符0次或1次
{n}	匹配前面的字符恰好n次
{n,}	匹配前面的字符至少n次
{n,m}	匹配前面的字符n到m次
[...]	匹配括號內的任意一個字符（字符類）
[^...]	匹配不在括號內的任意字符
`	`	或（匹配左邊或右邊的模式）
\d	匹配數字（等價于?[0-9]）
\D	匹配非數字（等價于?[^0-9]）
\w	匹配字母、數字、下劃線（等價于?[a-zA-Z0-9_]）
\W	匹配非字母、數字、下劃線
\s	匹配空白字符（空格、制表符、換行符等）
\S	匹配非空白字符
\b	匹配單詞邊界
\B	匹配非單詞邊界

---

3. 正則表達式示例

(1) 匹配數字

正則表達式	說明	匹配示例
\d+	匹配1個或多個數字	123,?0,?456
\d{3}	匹配3位數字	123,?456
\d{2,4}	匹配2~4位數字	12,?123,?1234

?