「QFOI R1」貼貼

題目描述

小 R 是一個可愛的女孩子，她希望通過給洛谷題目寫題解的方式跟出題人貼貼。

她發現，如果從題解界面點擊“提交題解”按鈕，博客中會自動生成 URL 標識符，也就是文章的鏈接。

其中，標識符的生成規則如下：

• 將題號的所有大寫字母轉為小寫。
• 將上一步結果的所有下劃線轉為減號。
• 在上一步結果前面加上 solution-。

她準備給一道題目寫題解，已知這道題的題號，你能求出 URL 標識符嗎？

輸入格式

一行，一個字符串 $s$，表示題號。

輸出格式

一行，一個字符串，表示 URL 標識符。

樣例 #1

樣例輸入 #1

P9202

樣例輸出 #1

solution-p9202

樣例 #2

樣例輸入 #2

CF1797F

樣例輸出 #2

solution-cf1797f

樣例 #3

樣例輸入 #3

AT_abc312_h

樣例輸出 #3

solution-at-abc312-h

提示

樣例 $3$ 解釋

根據生成規則：

• 將題號的所有大寫字母轉為小寫：at_abc312_h。
• 將上一步結果的所有下劃線轉為減號：at-abc312-h。
• 在上一步結果前面加上 solution-：solution-at-abc312-h。

---

數據范圍

本題共 $10$ 個測試點，每個測試點 $10$ 分。

對于全部數據，保證題號僅包含大寫字母（ASCII $65～90$）、小寫字母（ASCII $97～122$）、數字（ASCII $48～57$）、下劃線（ASCII $95$），且長度不超過 $20$。

對于全部數據，答案中應當僅包含小寫字母（ASCII $97～122$）、數字（ASCII $48～57$）、減號（ASCII $45$）。

• 對于測試點 $1$：保證為主題庫題目。
• 對于測試點 $2$：保證為入門與面試題目。
• 對于測試點 $3～4$：保證為 CodeForces 題目。
• 對于測試點 $5～6$：保證為 SPOJ 題目。
• 對于測試點 $7～8$：保證為 AtCoder 題目。
• 對于測試點 $9～10$：保證為 UVA 題目。

方法1

解題思路:

1. 將題號的所有大寫字母轉為小寫。
2. 將上一步結果的所有下劃線轉為減號。
3. 在上一步結果前面加上 solution-。

我們可以按照這個步驟依次處理題號字符串,最終得到 URL 標識符。

C++代碼實現:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;string generateURLIdentifier(string s) {// 將題號的所有大寫字母轉為小寫transform(s.begin(), s.end(), s.begin(), ::tolower);// 將所有下劃線轉為減號replace(s.begin(), s.end(), '_', '-');// 在結果前面加上 "solution-"s = "solution-" + s;return s;
}int main() {string s;cin >> s;string urlIdentifier = generateURLIdentifier(s);cout << urlIdentifier << endl;return 0;
}

代碼解釋:

1. 定義了一個函數 generateURLIdentifier,用于根據題號生成 URL 標識符。函數接受一個字符串 s 作為參數,表示題號,并返回生成的 URL 標識符。

2. 在函數內部,首先使用 transform 函數將題號的所有大寫字母轉為小寫。::tolower 是一個函數指針,指向 tolower 函數,用于將大寫字母轉為小寫字母。

3. 接下來,使用 replace 函數將所有下劃線替換為減號。

4. 最后,在結果字符串的前面加上 "solution-" 前綴,得到最終的 URL 標識符。

5. 函數返回生成的 URL 標識符。

6. 在 main 函數中,首先使用 cin 讀取題號字符串 s。

7. 調用 generateURLIdentifier 函數,將題號字符串 s 作為參數傳入,得到生成的 URL 標識符,并將其存儲在變量 urlIdentifier 中。

8. 輸出 urlIdentifier,即為生成的 URL 標識符。

復雜度分析:

• 時間復雜度:$O(n)$,其中 $n$ 是題號字符串的長度。我們需要遍歷題號字符串一次,對每個字符進行轉換操作。
• 空間復雜度:$O(n)$。我們需要存儲題號字符串和生成的 URL 標識符,所需的空間與題號字符串的長度成正比。

這個解決方案利用了C++標準庫中的算法函數 transform 和 replace,可以方便地對字符串進行轉換和替換操作。通過按照題目要求的規則依次處理題號字符串,我們可以得到最終的 URL 標識符。

知識點補充

好的,讓我詳細解釋一下 transform 函數,并給出幾個使用案例。

transform 函數是C++標準庫中的一個算法函數,定義在 <algorithm> 頭文件中。它用于對一個范圍內的元素進行轉換,并將結果存儲到另一個范圍內。

transform 函數有兩種常用的形式:

1. transform(first, last, result, unary_op)

   • first 和 last 是輸入范圍的迭代器,指定要轉換的元素范圍。
   • result 是輸出范圍的迭代器,指定轉換結果存儲的位置。
   • unary_op 是一個一元函數對象或函數指針,用于對輸入范圍內的每個元素進行轉換操作。

2. transform(first1, last1, first2, result, binary_op)

   • first1 和 last1 是第一個輸入范圍的迭代器,指定要轉換的元素范圍。
   • first2 是第二個輸入范圍的迭代器,指定第二個輸入序列的起始位置。
   • result 是輸出范圍的迭代器,指定轉換結果存儲的位置。
   • binary_op 是一個二元函數對象或函數指針,用于對兩個輸入范圍內的對應元素進行轉換操作。

下面給出幾個使用 transform 函數的案例:

案例1:將字符串中的字符轉為大寫

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;int main() {string str = "hello, world!";transform(str.begin(), str.end(), str.begin(), ::toupper);cout << str << endl;return 0;
}

輸出結果:

HELLO, WORLD!

在這個案例中,我們使用 transform 函數將字符串 str 中的每個字符轉為大寫。::toupper 是一個函數指針,指向 toupper 函數,用于將字符轉為大寫。

案例2:將容器中的元素乘以2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {vector<int> nums = {1, 2, 3, 4, 5};transform(nums.begin(), nums.end(), nums.begin(), [](int x) { return x * 2; });for (int num : nums) {cout << num << " ";}cout << endl;return 0;
}

輸出結果:

2 4 6 8 10

在這個案例中,我們使用 transform 函數將容器 nums 中的每個元素乘以2。這里使用了一個匿名函數(lambda表達式)作為轉換操作,將每個元素乘以2。

案例3:將兩個容器中的對應元素相加

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {vector<int> nums1 = {1, 2, 3};vector<int> nums2 = {4, 5, 6};vector<int> result(3);transform(nums1.begin(), nums1.end(), nums2.begin(), result.begin(), plus<int>());for (int num : result) {cout << num << " ";}cout << endl;return 0;
}

輸出結果:

5 7 9

在這個案例中,我們使用 transform 函數將兩個容器 nums1 和 nums2 中的對應元素相加,并將結果存儲到 result 容器中。plus<int>() 是一個函數對象,用于執行