藍橋杯題型分類

語法基礎

藝術與籃球（日期問題）

#include <bits/stdc++.h>
using namespace std;map<char,int>myMap;
int basketball,calligraphy;//日期是否合法模板
int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int date)
{int year=date/10000,month=date%10000/100,day=date%100;if(!month||month>=13||!day)return false;if(month!=2&&day>months[month])return false;if(month==2){int leap=(year%100!=0&&year%4==0)||year%400==0;if(day>28+leap)return false;}return true;
}int main() 
{// 插入數字與筆畫數myMap['0'] = 13;myMap['1'] = 1;myMap['2'] = 2;myMap['3'] = 3;myMap['4'] = 5;myMap['5'] = 4;myMap['6'] = 4;myMap['7'] = 2;myMap['8'] = 2;myMap['9'] = 2;// 遍歷日期范圍，從2000年1月1日到2024年4月13日for(int i=20000101;i<=20240413;i++){if(check(i)){string s=to_string(i);int num=0;for(auto j:s){num+=myMap[j];}if(num>50){basketball++;}}}cout<<basketball;return 0;
}

時間顯示（時間問題）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main() 
{ll x;cin >> x;// 計算小時、分鐘、秒數ll hh = (x / 3600000) % 24;  // 小時數，取 24 小時制ll mm = (x / 60000) % 60;     // 分鐘數，取 60 分鐘ll ss = (x / 1000) % 60;      // 秒數，取 60 秒// 輸出時間格式printf("%02lld:%02lld:%02lld", hh, mm, ss);return 0;
}

跑步計劃（日期問題）

#include <bits/stdc++.h>
using namespace std;int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  // 每個月的天數// 檢查數字是否包含1
bool check(int x) {while (x) {if (x % 10 == 1) {return true;  // 如果數字中包含1，返回true}x /= 10;  // 去除最后一位}return false;  // 如果沒有1，返回false
}int main() {int ans = 0;  // 總跑步的千米數int week = 6;  // 2023年1月1日是星期天，所以初始化為6（星期天）// 遍歷每個月for (int i = 1; i <= 12; i++) {// 遍歷每個月的每一天for (int j = 1; j <= months[i]; j++) {week = (week % 7) + 1;  // 更新星期幾，確保在1到7之間循環（星期天為7）// 如果日期、月份或星期幾包含1，跑5千米if (check(i) || check(j) || check(week)) {ans += 5;} else {ans += 1;  // 否則跑1千米}}}cout << ans;  // 輸出小藍總共跑的千米數return 0;
}

偶串(字符）

使用 Map 或者 unordered_map。
遍歷字符串中的每個字符。對每個字符，檢查它是否已經在你的數據結構中。如果是，增加它的計數。

#include <iostream>
#include <unordered_map>
using namespace std;int main() {string str;cin >> str;  // 輸入字符串unordered_map<char, int> char_count;  // 用哈希表存儲每個字符的出現次數// 遍歷字符串并統計每個字符的出現次數for (char c : str) {char_count[c]++;}// 檢查是否每個字符出現次數為偶數bool is_even = true;for (auto& pair : char_count) {if (pair.second % 2 != 0) {  // 如果出現次數是奇數is_even = false;break;}}// 輸出結果if (is_even) {cout << "YES" << endl;} else {cout << "NO" << endl;}return 0;
}

創建一個大小為26的整數數組（假設為 cnt），用于存儲每個小寫字母的出現次數。數組的索引 
0?25 分別對應字母 a-z。
遍歷字符串的每一個字符（假設為 c）：
將字符 c 轉為其 ASCII 值。
通過計算 c - 'a' 來得到一個從 0
0 到 25 的索引，這個索引對應于字符 c。
使用這個索引來增加 cnt 數組中對應元素的值。
遍歷結束后，cnt 數組中的每個元素就存儲了對應字母在字符串中的出現次數。

#include <iostream>
#include <vector>using namespace std;int main()
{string s;vector<int> cnt(26);cin >> s;for (auto c : s){cnt[c - 'a']++;}for (int i = 0; i < 26; ++i){if (cnt[i] % 2){cout << "NO" << '\n';return 0;}}cout << "YES" << '\n';return 0;
}

最長子序列（字符）

#include <iostream>
#include <string>
using namespace std;int main() {string s, t;int num = 0;cin >> s >> t;for (char ch : t) {// 查找當前字符ch在s中的位置size_t pos = s.find(ch);if (pos == string::npos) {// 如果找不到字符，直接輸出已找到的匹配數并結束程序cout << num;return 0;} else {// 如果找到了字符，更新字符串s并增加計數num++;s = s.substr(pos + 1);  // 從pos+1開始截取s}}// 輸出最終匹配的字符數cout << num;return 0;
}

字母數（進制轉換）

#include <bits/stdc++.h>
using namespace std;using ll=long long;
int a[1000];
char ch[] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };bool solve(int x)//十進制轉換為16進制
{string ans;while(x){if(ch[x%16]>='A'){ans+=ch[x%16];x/=16;}else{return false;}}reverse(ans.begin(),ans.end());return true;
}
int main() 
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int i=2022;while(true){i++;if( solve(i)){cout<<i;return 0;}}return 0;
}

6個0（進制轉換）

#include <bits/stdc++.h>
using namespace std;bool check(int x)
{// 檢查最低的 5 位是否都為 0for(int i = 0; i < 5; i++){if(((x >> i) & 1) != 0) // 如果第 i 位不為 0，返回 false{return false;}}return true;
}int main() 
{int x = 2022; // 從 2022 開始查找while(true){x++; // 從 2023 開始檢查if(check(x)) // 如果 x 的最低 5 位全為 0{cout << x;return 0;}}return 0;
}

優秀的拆分（位運算）

• 輸入輸出樣例
  示例 1
  輸入

6

輸出

4 2

示例 2
輸入

7

輸出

-1

7的二進制數為（0111），6的二進制數為（0110），可以發現7的二進制位的最低位（第0位）為1，值為
$2^0$ ,所以只要最低位為1，就不是優秀的拆分。我的從最高位開始遍歷，只要第i位為1，我們就輸出 1<<i ,即為$2^i$

#include <bits/stdc++.h>
using namespace std;int main() {int num;cin >> num;// 如果最低位為 1，輸出 -1if (((num >> 0) & 1) == 1) {cout << -1 << endl;return 0;}// 從最高位開始遍歷，檢查每一位for (int i = 30; i >= 0; i--) {// 如果當前位為 1，輸出 2^iif (((num >> i) & 1) == 1) {cout << (1 << i) << " ";}}return 0;
}

異或數列(位運算)

示例 1

輸入
4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

輸出
1
0
1
1

解題思路

我們設在游戲結束后 Alice 的數變為 c，Bob 的數變為 d。

我們先來解決平局的情況：

根據異或性質可得：若 c = d，則 c ⊕ d = 0。

而 c ⊕ d = X1 ⊕ X2 ⊕ ? ⊕ Xn，所以要使 c = d，當且僅當 X1 ⊕ X2 ⊕ ? ⊕ Xn = 0。

接下來定輸贏：

我們將 c, d 轉換成二進制數。對于二進制數的比較，我們是從高位往低位開始的。所以要使自己的數最大，就需要從高位開始。

設當前枚舉到二進制的第 i 位。設 X1, X2, X3, ..., Xn 中一共有 cnt1 個數在該位的值為 1，cnt2 個數在該位的值為 0。（cnt1 + cnt2 = n）

結論一：

如果 cnt1 為偶數，則 Alice 和 Bob 無法在該位分出勝負。

證明方法和上述平局情況相同。 或者也可以這么想：cnt1 為偶數，那么 Alice 和 Bob 要么都從這 cnt1 個數中分到偶數個，要么 Alice 和 Bob 都在這 cnt1 個數中分到奇數個；所以無論怎么分配，c, d 在該位的異或值都必然相同。

反之當 cnt1 為奇數時，必然能決出勝負。證明方法和上述類似，就不再給出。

那么 cnt1 為奇數時如何判斷誰輸誰贏呢？

我們先定義，對于當前第 i 位，如果能讓自己的數值從 0 → 1，或者能讓對手的數值從 1 → 0，則自己的勝率 +1；如果讓自己的數值從 1 → 0，或者讓對手的數值從 0 → 1，則自己的勝率 -1；如果既不改變自己的數值，也不改變對手的數值，則自己的勝率不變。顯然，游戲結束時，勝率越高的一方獲勝。

結論二：

當 cnt1 為奇數，cnt2 = 0 時，先手必勝。

證明：

模擬一下可以發現先手后手走的每一步都必然是讓自己勝率增加的一步。由于 cnt1 為奇數，所以先手可以比后手多走一步，所以先手的勝率必然會比后手高。

那么什么情況下必然會使自己的勝率減少呢？即當自己的數值為 1，且對手的數值為 0，且公共數列中只有 1 可以選取時。

結論三：

誰的勝率率先減少，則誰必敗。

證明： 由于一方勝率減少了，所以可得公共數列中只有 1 可以選取，沒有 0 可以選取。

設勝率率先減少的 Alice，那么此時 Alice 和 Bob 的數值只有兩種可能：

1. Alice 的數值為 0，Bob 的數值為 0；
2. Alice 的數值為 1，Bob 的數值為 1。

由于 Alice 和 Bob 的數值相同，所以公共序列中使用的 1 的個數必然為偶數，剩余的 1 的個數必然為奇數。且此時是 Bob 先手，根據結論二，Bob 必勝，Alice 必敗，證明完畢。

那么誰的勝率會先減少的呢？

結論四：

當 cnt1、cnt2 為奇數時且 cnt1 > 1 時，先手的勝率會率先減少。

證明： 當 cnt2 為奇數時，先手第一步只能選取 0 或是 1：

• 若先手先取 1 則后手取 0。此時先手的數值為 1，后手的數值為 0。為了不讓自己的勝率降低，先手只能取 0，而后手也接著取 0。由于 0 個為奇數，所以先手將率先無法取 0，只能取 1，使得自己的勝率降低。
• 若先手取 0 則后手也取 0。此時場面還是 1 的個數為奇數，0 的個數為奇數的情況。若先手率先取了 1，則就回到了上述的情況，先手必敗。所以先手只能不斷取 0，而后手也跟著不斷取 0。最后先手取完 0，將剩余奇數個 1，回到了結論三的情況。由于此時到了后手的輪次，所以先手必敗。

結論五：

當 cnt1 = 1 時，先手必勝。

證明略。

根據上述五個結論，模擬一遍即可。

復雜度為 O(22 ∑ i=1 Tni)。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];signed main() {int T = 1;cin >> T;while(T--) {int n, sum = 0, ans = 0;cin >> n;// 讀取輸入并計算異或和for(int i = 1; i <= n; i++) {cin >> a[i];sum ^= a[i];}// 結論1:如果異或和為 0，則平局if (!sum) {cout << 0 << '\n';continue;}// 對每一位進行分析for (int j = 20; j >= 0; j--) {int one = 0, zero = 0;// 統計當前位上的1和0的數量for (int i = 1; i <= n; i++) {if (a[i] >> j & 1) one++;else zero++;}// 結論2 如果當前位有奇數個1，則確定勝負if (one & 1) {if (zero % 2 && one != 1) ans = -1;  //結論4 不滿足條件，Bob 獲勝else ans = 1;  // 滿足條件，Alice 獲勝break;}}cout << ans << '\n';  // 輸出結果}return 0;
}

幸運數字的個數(預計算）

樣例輸入
6
1 10
1 16
1 17
10 100
100 1000
1000 10000

樣例輸出
10
15
16
11
13
14

說明
對于所有評測數據：

$1\le T\le 10^5,1\le l_i\le r_i\le 10^{12}。$

要用到的思想是先“離線”預計算所有可能的幸運數字，再用二分查找快速計算每個查詢區間內的幸運數字數量。具體做法如下：

先枚舉所有“十六進制中由同一字符重復”的數字，排除超過 10^12 的值，并將這些數字存儲到一個數組并排序；
對每次給定的范圍 [l, r]，使用二分查找定位區間上下界，從而快速統計落在該區間內的幸運數字個數。

#include <bits/stdc++.h>
using namespace std;static const long long MAX_VAL = 1000000000000LL; // 1e12// 預先生成所有在 [1, 1e12] 范圍內 "十六進制由同一數字重復" 的幸運數字
// 注意：digit 取值范圍是 [0..15]，長度取值范圍適當即可（1~16足夠覆蓋1e12）
vector<long long> generateLuckyNumbers() {vector<long long> luckyNums;// 十六進制最大可用字符：0~f (共16個)for (int digit = 0; digit < 16; ++digit) {for (int length = 1; length <= 16; ++length) {// 構建長度為 length 的重復字符// 例如若 digit = 12 (十六進制 c)，length = 4，則是"cccc"// 然后轉為十進制，判斷是否 <= 1e12// digit 轉成對應的16進制字符char hexDigit;if (digit < 10) {hexDigit = char(digit + '0');} else {hexDigit = char(digit - 10 + 'a');}// 構建重復串string hexStr(length, hexDigit);// 轉成十進制// stoll(hexStr, nullptr, 16) 有可能超范圍，用更安全方式// 這里用 64位整型計算long long num = 0;for (char c : hexStr) {// digitVal 可以用 c - '0' 或 c - 'a' + 10// 但我們已經知道是同一個字符int val;if (isdigit(c))val = c - '0';elseval = c - 'a' + 10;num = num * 16 + val;// 若已經超過范圍就中斷if (num > MAX_VAL) break;}if (num > 0 && num <= MAX_VAL) {luckyNums.push_back(num);}}}// 去重并排序sort(luckyNums.begin(), luckyNums.end());luckyNums.erase(unique(luckyNums.begin(), luckyNums.end()), luckyNums.end());return luckyNums;
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);// 預先生成所有可能的幸運數字static vector<long long> luckyNumbers = generateLuckyNumbers();int T;cin >> T;while (T--) {long long l, r;cin >> l >> r;// 在 luckyNumbers 中，用二分查找統計區間 [l, r] 內的元素個數auto leftIt = lower_bound(luckyNumbers.begin(), luckyNumbers.end(), l);auto rightIt = upper_bound(luckyNumbers.begin(), luckyNumbers.end(), r);cout << (rightIt - leftIt) << "\n";}return 0;
}

填空

握手問題

對于第一個人來說 除了自己以外要跟其他49人握手 所以第一個是49 ，對于第二個人來說 第一個人主動跟我握手了 有一次不算 所以第二個是48.。 以此類推 第43個人就是7 到了最后七個人呢 因為互相都沒有握手 并且7個人都被前面的人握過手了 所以都是0

#include <iostream>
using namespace std;
int main(){int sum=0;for(int i=7;i<=49;i++) sum+=i;cout<<sum;return 0;
}

報數問題

第1-10個： 20 24 40 48 60 72 80 96 100 120第11-20個：140 144 160 168 180 192 200 216 220 240第21-30個：260 264 280 288 300 312 320 336 340 360第31-40個：380 384 400 408 420 432 440 456 460 480思路一：發現第10個數，第20個數，第30個數，第40個數......（每十個數為一輪）等等都是120的倍數，既然題目要求第202420242024個數，那我們不妨先求第202420242020個數，然后再往后再多求4個數就行。也就是202420242020/10*120=202429042904240，找它之后的四個能被20或24整除的數，也就是2429042904288思路二：通過觀察發現，第奇數位個數是20的倍數，第偶數位個數是24的倍數。所以第202420242024個數就是24的倍數，那我們直接除以2（判斷是這個數是第幾個24的倍數)，然后再乘24就行。也就是202420242024÷2×24=2429042904288

雜題

游戲專家（零和博弈）

輸入格式
一行一個字符串
s（1≤∣s∣≤1000）由小寫英文字母組成。
樣例輸入
bazabyakslfd

樣例輸出
zbybzazazaza

分治思想（交替處理策略）先行者和后行者對應偶數和奇數
我們輪流讓小藍和小橋修改字符串，小藍盡量將字符變成字典序最大的字母 z，小橋盡量將字符變成字典序最小的字母 a。

#include <bits/stdc++.h>
using namespace std;int main()
{string s;cin >> s;int n = s.size();// 輪流修改字符串for (int i = 0; i < n; i++){if (i % 2 == 0)  // 小藍的回合，盡量使字典序最大{if (s[i] != 'z')  // 如果當前字符不是'z'，則將其改為'z'{s[i] = 'z';}}else  // 小橋的回合，盡量使字典序最小{if (s[i] != 'a')  // 如果當前字符不是'a'，則將其改為'a'{s[i] = 'a';}}}cout << s;  // 輸出最終字符串return 0;
}

大衣的異或回文對（回文判斷）

樣例輸入1
4
13 27 12 26

樣例輸出1
8

樣例輸入2
3
2 2 2

樣例輸出2
6

使用字符判斷回文

// 判斷整數 x 是否是回文
bool isPalindrome(int x) {string s = to_string(x);string rev_s(s.rbegin(), s.rend());return s == rev_s;
}

使用數字判斷回文

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 2e4 + 10;ll a[N];
ll ans;// 判斷是否是回文數
bool hw(ll n) {ll sum = 0;ll k = n;while (n != 0) {sum = (sum * 10) + (n % 10);  // 反轉數字n /= 10;}return sum == k;  // 如果反轉的數字等于原數字，則為回文數
}int main() {ll n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}// 遍歷所有對 (i, j) 計算異或并判斷是否是回文數for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {if (hw(a[i] ^ a[j])) {ans++;}}}cout << ans << endl;return 0;
}

尋找至寶的奧秘（數學）

最大公因數的基本概念：
最大公因數（GCD）是指兩個數的最大共有因子。比如，gcd(12, 15) = 3，因為 12 和 15 都能被 3 整除，而沒有比 3 更大的共同因子。

思路分析：

1. 最大公因數的性質：

   • 假設我們有兩個正整數 a 和 b，如果它們的 GCD 很大，那么這兩個數的因子也應該盡量重合。
   • 如果我們選取 a = n 和 b = n / 2，那么它們的 GCD 通常會比較大。具體來說，gcd(n, n/2) 總是 n/2（這是因為 n/2 是 n 的因子，并且它們共享 n/2 作為共同因子）。

2. 為什么選擇 n 和 n / 2：

   • 選擇 n 和 n / 2 作為候選：

     • 如果我們選擇兩個數 a = n 和 b = n / 2，這兩個數之間的最大公因數是 n / 2。這是因為：
       • n 是 n / 2 的倍數，n 和 n / 2 的最大公因數就是 n / 2。
     • 例如，當 n = 10 時，n = 10 和 n / 2 = 5，這兩個數的 GCD 是 5。

   • 為什么 n / 2 會是最大值：

     • 當我們選擇兩個數時，我們希望它們的最大公因數盡可能大。n / 2 是 n 最大的因子之一，所以選擇 n 和 n / 2 總是能得到最大的 GCD。

3. 其他可能的組合：

   • 如果選擇 a = n 和 b = n - 1，它們的最大公因數一般會較小，因為相鄰的整數的 GCD 總是 1。
   • 同理，其他的一些數對，如 a = n 和 b = n - 2 等，都會比 n / 2 和 n 的 GCD 小。

例子：

• 例子 1：
  輸入：n = 10

  • 我們選擇 a = 10 和 b = 10 / 2 = 5，計算 gcd(10, 5)，結果是 5。
  • 因為 10 和 5 的最大公因數是 5，這是最大的 GCD。

• 例子 2：
  輸入：n = 12

  • 我們選擇 a = 12 和 b = 12 / 2 = 6，計算 gcd(12, 6)，結果是 6。
  • 因為 12 和 6 的最大公因數是 6，這是最大的 GCD。

#include <iostream>
using namespace std;int main() {int n;cin >> n;// 輸出 n / 2 即可得到最大公因數cout << n / 2 << endl;return 0;
}

小藍的戰斗計劃

1. 優先嘗試消滅需要 2 個單位時間的怪物：遍歷排序后的所有時間段 b[i]，如果 b[i] ≥ 2，就盡可能使用該時間段來消滅“需要 2 個單位時間”的怪物（min(cnt2, b[i]/2)）。在此操作中，消滅多少頭怪物，就從 cnt2 和 b[i] 各自對應的“數量”中減去相應數值。
2. 然后嘗試消滅需要 1 個單位時間的怪物：再次遍歷同一個排序后的時間段數組，如果 b[i] ≥ 1，就用這個時間段去消滅盡量多的 cnt1 怪物（min(cnt1, b[i])）。
3. 最后檢查 cnt1 和 cnt2 是否都被消滅（即 cnt1 == 0 && cnt2 == 0）。若全部消滅則輸出 “Y”，否則輸出 “N”。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;int n, m;
int cnt1 = 0, cnt2 = 0;
int a[N], b[N];int main() {cin >> n >> m;// 輸入怪物的戰斗時間，并統計需要時間1和時間2的怪物數量for (int i = 1; i <= n; i++) {int x;cin >> x;if (x == 1) {cnt1++;} else {cnt2++;}}// 輸入時間段的長度for (int i = 1; i <= m; i++) {cin >> b[i];}// 對時間段進行降序排序sort(b + 1, b + 1 + m, [](int u, int v) { return u > v; });// 優先使用時間段消滅需要時間2的怪物for (int i = 1; i <= m && cnt2 > 0; i++) {if (b[i] >= 2) {  // 如果時間段長度>=2，可以消滅一個需要時間2的怪物int x = min(cnt2, b[i] / 2);  // 計算能消滅多少個怪物cnt2 -= x;  // 更新需要消滅時間2的怪物數量}}// 使用剩余的時間段消滅需要時間1的怪物for (int i = 1; i <= m && cnt1 > 0; i++) {if (b[i] >= 1) {  // 如果時間段長度>=1，可以消滅一個需要時間1的怪物int x = min(cnt1, b[i]);  // 計算能消滅多少個怪物cnt1 -= x;  // 更新需要消滅時間1的怪物數量}}// 判斷是否所有怪物都被消滅if (cnt1 == 0 && cnt2 == 0) {cout << "Y" << endl;} else {cout << "N" << endl;}return 0;
}

公司名稱（字符串）

樣例輸入
5
7
Lqaaoin
7
Lanqiao
8
Lanqiaoo
2
ac
7
niLaqqa

樣例輸出
YES
YES
NO
NO
NO

#include <bits/stdc++.h>
using namespace std;int main() {string name = "Lanqiao";int t;cin >> t;while (t--) {int n;cin >> n;string s;cin >> s;if (name.length() == s.length()) {for (char j : name) {int pos = s.find(j);if (pos != string::npos) {s.erase(pos, 1); // 從pos開始刪除一個字符}}if (s.empty()) cout << "YES" << endl;else cout << "NO" << endl;} else {cout << "NO" << endl;}}return 0;
}

航班時間（字符串讀取+方程式）

傳送門

輸出描述
對于每一組數據輸出一行一個時間 hh:mm:ss，表示飛行時間為 hh 小時 mm 分 ss 秒。
注意，當時間為一位數時，要補齊前導零。如三小時四分五秒應寫 03:04:05。

輸入輸出樣例
示例

輸入
3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)

輸出
04:09:05
12:10:39
14:22:05

#include<bits/stdc++.h>
using namespace std;
int getTime(void)
{int h1,m1,s1,h2,m2,s2,d=0;scanf("%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);int time=d*24*3600+h2*3600+m2*60+s2-(h1*3600+m1*60+s1);return time;
}
int main()
{int t;scanf("%d",&t);for(int i = 0; i < t; i++){int time1=getTime();int time2=getTime();int t=(time1+time2)/2;printf("%02d:%02d:%02d\n", t/3600, t/60%60, t%60);}return 0;
}

也可以使用sscanf,關于具體用法，可見傳送門

#include <bits/stdc++.h>
using namespace std;// get_time 函數用于計算時間差（單位為秒）
int get_time() 
{string line;getline(cin, line); // 讀一行時間字符串// 如果時間字符串沒有以 ")" 結尾，則添加 "(+0)"if (line.back() != ')')  line += " (+0)";// 定義起飛時間和到達時間的各個組件int h1, m1, s1, h2, m2, s2, day;// 解析時間字符串，提取小時、分鐘、秒和天數sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &day);// 將時間轉為秒數，起飛時間和到達時間int S = h1 * 3600 + m1 * 60 + s1; // 起飛時間：轉為秒int E = h2 * 3600 + m2 * 60 + s2; // 到達時間：轉為秒// 返回時間差，考慮到天數影響return E - S + day * 24 * 3600;
}int main() 
{string line;getline(cin, line); // 讀取第一行int n;// 解析第一行，獲取組數 nsscanf(line.c_str(), "%d", &n);// 循環處理每組數據while (n--) {// 計算兩次時間差的平均值int ans = (get_time() + get_time()) / 2;// 輸出結果，格式化為時:分:秒printf("%02d:%02d:%02d\n", ans / 3600, ans / 60 % 60, ans % 60);}
}

藍橋村的神秘信件（字符串）

#include <iostream>
#include <unordered_map>
using namespace std;int main() {int N;string S;cin >> N;cin >> S;// 用哈希表來統計每個字符的頻率unordered_map<char, int> freq;// 統計字符頻率for (int i = 0; i < N; i++) {freq[S[i]]++;}// 查找第一個只出現一次的字符for (int i = 0; i < N; i++) {if (freq[S[i]] == 1) {cout << S[i] << endl;return 0; // 找到第一個只出現一次的字符后，直接返回}}// 如果沒有找到，只出現一次的字符cout << -1 << endl;return 0;
}

打開石門

傳送門

#include <bits/stdc++.h>
using namespace std;int main(){string s; cin >> s;  // 讀取輸入字符串int a = 0, b = 0;  // 初始化兩個計數器：a用于統計LL對數，b用于統計QQ對數// 遍歷字符串，檢查相鄰的字符對for (int i = 1; i < s.size(); i++) {if (s[i-1] == 'L' && s[i] == 'L') a++;  // 如果是LL相鄰，a加1if (s[i-1] == 'Q' && s[i] == 'Q') b++;  // 如果是QQ相鄰，b加1}// 輸出最終能縮短到的最小長度cout << s.size() - max(a, b);  // 減去最大合并次數，得到最小長度return 0;
}

諾伊的神秘密碼(字符串切割）

傳送門

#include <bits/stdc++.h>
using namespace std;// 左旋操作：將第一個字符移動到末尾
string left(string s)
{return s.substr(1, s.size() - 1) + s[0];
}// 右旋操作：將最后一個字符移動到開頭
string right(string s)
{return s[s.size() - 1] + s.substr(0, s.size() - 1);
}int main()
{string s;cin >> s;  // 輸入字符串 S// 分別計算左旋和右旋后的結果string lefts = left(s);string rights = right(s);// 判斷左旋和右旋后的結果是否相同if (lefts == rights){cout << "YES";  // 如果相同，則輸出 YES}else{cout << "NO";  // 如果不同，則輸出 NO}return 0;
}

超級的大串 （字符組合）

傳送門

假設我們正在處理字符串 str = "abz", 且我們正在處理第 1 個字符 'b'。

• 如果我們選擇一個字符 'c' 或更大的字符來替代 'b'，那么在 'b' 后面的位置（即位置 2）可以選擇任意的字符，直到字符串的結尾。假設右邊的部分是 'z'，可以替換成 'a'、'b'、'c' … 'z'，所以右側的字符部分可以有 26 種可能。

為什么要用 26 的冪：

• 字符串的每個位置有 26 個可能的字符（從 'a' 到 'z'）。
• 對于當前字符，如果我們選擇了一個字典序大于當前字符的字符，那么剩下的字符都可以是任意的（即它們有 26 種可能）。

例如：

• 如果我們選擇 'c' 代替 'b'，那么 'z' 后面的字符可以是任何字母，因此可能的組合數就是 26。
• 如果字符串中還有更多字符，那么我們可以繼續這樣選擇。

對應的代碼：

for (int j = 0; j < str.size() - i - 1; j++) res = res * 26 % mod;

• str.size() - i - 1：這表示當前字符右邊的字符數，i 是當前字符的索引。所以我們知道在 str[i] 后面有 str.size() - i - 1 個字符需要考慮。

• res = res * 26 % mod：表示對于每一個后續位置，都會有 26 種可能的選擇。所以我們用 26 來乘上當前的結果 res，并且對 mod 取模，確保結果不會溢出。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int MOD = 998244353;int n;
string s;
ll ans = 0;  // 結果變量需要初始化int main() 
{cin >> n >> s;// 從字符串的每個字符開始遍歷for (int i = 0; i < s.size(); i++) {ll res = 1;// 計算當前字符 's[i]' 在字母表中的位置int t = s[i] - 'a' + 1;  // 字母 'a' 的位置是 1，'b' 是 2，以此類推if (t == 26) {continue;  // 如果當前字符是 'z'，跳過，因為沒有比 'z' 更大的字符} else {// 對于當前位置后面的字符，每個字符有 26 種可能for (int j = 0; j < s.size() - i - 1; j++) {res = res * 26 % MOD;  // 計算后續字符的所有組合}// 計算比當前字符大的字符數res = res * (26 - t) % MOD;// 累加結果ans = (ans + res) % MOD;}}// 輸出結果并對 998244353 取模cout << ans << endl;return 0;
}

食堂活動 （哈希字符）

傳送門

#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;// 用數組或 map 存儲每種菜的價格// 字符是小寫字母，所以我們可以用 char -> int 下標vector<long long> price(26, 0);for(int i = 0; i < n; i++){char c;long long p;cin >> c >> p;price[c - 'a'] = p;}// 讀取點餐字符串string order;cin >> order;// 統計每種菜的點餐數量vector<long long> count(26, 0);for(char c : order){count[c - 'a']++;}// 計算總價// 活動：每點兩份同種菜，就送一份同種菜，即3份只需付2份錢long long ans = 0;for(int i = 0; i < 26; i++){if(count[i] > 0 && price[i] > 0){long long x = count[i];long long fullSets = x / 3;         // 每3份只付2份錢long long remainder = x % 3;        long long costForDish = price[i] * (2LL * fullSets + remainder);ans += costForDish;}}cout << ans << "\n";return 0;
}

特殊日期

#include <iostream>
using namespace std;long long months[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(long long year)
{return (year%4==0&&year%100!=0)||year%400==0;
}
long long ans;
int main()
{for(int i=2000;i<2000000;i++){// 判斷是否為閏年，并更新2月天數if(check(i)){months[2]=29;}else{months[2]=28;}for(int j=1;j<=12;j++) {if(i%j==0)  // 如果年份是該月份的倍數{for(int k=1;k<=months[j];k++)// 遍歷該月的每一天{if(i%k==0) // 如果年份是該天數的倍數{ans++;}  }}}}ans++;// 2000000.1.1 不要忘記這個日期cout<<ans;return 0;
}

高斯日記（日期差值）

傳送門

#include <iostream>
using namespace std;int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 判斷是否為閏年
bool check(int year) {return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}int main() {int d = 8113 - 5343 - 16;  // 天數差int year = 1792, month, day;// 逐年遞減，找到目標日期所在的年份while (d > 365) {d -= (365 + check(year));  // 減去每年天數，閏年則為366天year++;}// 判斷目標年份是否是閏年，更新2月天數if (check(year)) {months[2] = 29;  // 閏年2月29天} else {months[2] = 28;  // 非閏年2月28天}// 逐月遞減，找到目標月份和日期for (month = 1; d > months[month]; month++) {d -= months[month];  // 減去當前月的天數}day = d;  // 剩余的天數就是目標日期// 輸出結果，確保格式為 yyyy-mm-ddprintf("%04d-%02d-%02d", year, month, day);return 0;
}

跑步鍛煉（日期問題）

傳送門

我們用 (sum + 6) % 7 來計算當前日期是星期幾。為什么要加6呢？因為我們假設 2000年1月1日 是星期六，所以要調整到星期六作為起點。

#include <iostream>
using namespace std;int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};// check函數用于驗證日期是否合法
bool check(int date)
{int year = date / 10000;        // 提取年份int month = date % 10000 / 100; // 提取月份int day = date % 100;           // 提取日期if (!month || month > 12 || !day) return false;if (month != 2 && day > months[month]) return false;if (month == 2){int leap = year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);if (day > 28 + leap) return false;}/return true;
}int main()
{int ans = 0;   // 記錄符合條件的日期數int sum = 0;   // 記錄當前日期的星期幾（從2000年1月1日開始）// 從2000年1月1日到2020年10月1日逐日檢查for (int i = 20000101; i <= 20201001; i++){// 檢查當前日期是否有效if (check(i)){ans++; // 如果是有效日期，增加答案計數int month = i % 10000 / 100; // 提取當前日期的月份int day = i % 100;           // 提取當前日期的日期// 如果是1號或者當前是星期一，增加答案計數if (day == 1 || (sum + 6) % 7 == 1){ans++; // 1號或者星期一時，計數加1}sum++; // 增加天數，更新星期幾}}// 輸出符合條件的日期數cout << ans;return 0;
}

回文日期

傳送門

#include <iostream>
using namespace std;int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// check函數用于判斷日期是否合法
bool check(int n)
{// 分解年份、月份和日期int y = n / 10000;       int m = n % 10000 / 100;  int d = n % 100;          if (!m || !d || m >= 13) return false;if (m != 2 && d > month[m]) return false;if (m == 2){int leap = y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);  if (d > 28 + leap) return false;  }return true;
}// check_abab函數用于檢查日期是否符合"abab"格式
bool check_abab(int n)
{int a = n / 10000000;       // 提取第一個數字int b = n / 1000000 % 10;   // 提取第二個數字int c = n / 100000 % 10;    // 提取第三個數字int d = n / 10000 % 10;     // 提取第四個數字// 檢查是否符合"abab"格式且a與b不相等if (a == c && b == d && a != b) return true;return false;
}int main()
{int n;cin >> n;  // 輸入日期（格式為YYYYMMDD）int flag = 1;  // 用于標記是否已找到滿足條件的日期// 從輸入日期的年份開始逐年遍歷for (int i = n / 10000; i <= 10000; i++){int date = i, x = i;// 構造出該年份的“abab”格式日期for (int j = 0; j < 4; j++){date = date * 10 + x % 10;  // 將當前年份的最后一個數字逐個加到日期中x /= 10;  // 去除最后一位數字}// 如果構造的日期有效，且大于輸入日期，并且flag為1，則輸出該日期if (check(date) && flag && date > n){cout << date << endl;flag = 0;  // 找到第一個符合條件的日期后，設flag為0，防止再次輸出}// 如果構造的日期有效，并且符合"abab"格式，且大于輸入日期，則輸出并結束程序if (check(date) && check_abab(date) && date > n){cout << date;return 0;  }}return 0;  
}

特殊時間（枚舉日期）

傳送門

#include <bits/stdc++.h>
using namespace std;// 定義每個月所包含的天數（下標 0 未用）
int day_per_month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};/*** @brief 檢查傳入的四位數 D（形如 MMDD）是否是一個合法日期* @param D 整數表示月日，如 0229、1231* @return 若是有效的月/日則返回 true，否則返回 false*/
bool check_D(int D){// 月份放在高兩位int month = D / 100;// 天數放在低兩位int day = D % 100;// 月份合法區間為 [1, 12]if(month < 1 || month > 12) return false;// 日數合法區間根據當月天數判定if(day < 1 || day > day_per_month[month]) return false;return true;
}/*** @brief 檢查傳入的四位數 H（形如 HHMM）是否是一個合法時間* @param H 整數表示小時分鐘，如 0020、2359* @return 若是有效的小時/分鐘則返回 true，否則返回 false*/
bool check_H(int H){// 小時放在高兩位int h = H / 100;// 分鐘放在低兩位int m = H % 100;// 小時合法區間為 [0, 23]if(h < 0 || h > 23) return false;// 分鐘合法區間為 [0, 59]if(m < 0 || m > 59) return false;return true;
}/*** @brief 主函數：通過枚舉方式，統計由兩個不同數字 (a, b) 組合成*  “3個相同 + 1個不同” 的4位數（用于表示年份、月日、時分）的有效組合*/
int main(){int ans = 0; // 統計符合要求的時間個數// 外層循環枚舉第一個數字 afor(int a = 0; a <= 9; a++){// 內層循環枚舉第二個數字 b，確保 a 與 b 不同for(int b = 0; b <= 9; b++){if(a != b){// 年份寫成 4 位時全部使用 a，因此年份可以看作 aaaa// 程序中將其視作 "有 4 種情況"（N_Y=4），只是為了乘法計算便捷int N_Y = 4;  // 在本題理解為“年份 aaaa”時的簡單做法int N_D = 0;  // 用來統計"3a + 1b" 所構造的四位數在日期上的合法個數int N_H = 0;  // 用來統計"3a + 1b" 所構造的四位數在時刻上的合法個數// 先把數組 A 初始化為 [a, a, a, a]int A[4] = {a, a, a, a};// 通過把 b 放在 4 個位置之一，枚舉出 4 種排列：aaab, aaba, abaa, baaafor(int i = 0; i < 4; i++){A[i] = b;  // 將 b 放在第 i 個位置int number = 0;// 將 A[0..3] 拼接成一個四位數for(int j = 0; j < 4; j++){number = number * 10 + A[j];}// 檢查該四位數是否能表示一個合法的 日期（月日）N_D += check_D(number);// 檢查該四位數是否能表示一個合法的 時刻（小時分鐘）N_H += check_H(number);A[i] = a; // 恢復現場，繼續處理下一個位置}// ans += 年份的 4 種可能 * 合法日期數 * 合法時刻數ans += N_Y * N_D * N_H;}}}// 輸出結果cout << ans << endl;return 0;
}

二分

123

傳送門

1. 小區間的構成

假設數列的構成是如下形式：

• 第 1 個區間包含 1 個元素（1）。
• 第 2 個區間包含 2 個元素（1 2）。
• 第 3 個區間包含 3 個元素（1 2 3）。
• 第 4 個區間包含 4 個元素（1 2 3 4）。
• …

第 i 個小區間包含 i 個元素。我們將這些小區間連起來形成整個數列。

2. 數組 a[j] 的定義

數組 a[j] 表示前 j 個小區間的總元素數，同時也能表示每個小區間的和。例如：

• a[1] = 1 （表示前 1 個小區間有 1 個元素）
• a[2] = 1 + 2 = 3 （表示前 2 個小區間共有 3 個元素）
• a[3] = 1 + 2 + 3 = 6 （表示前 3 個小區間共有 6 個元素）
• a[4] = 1 + 2 + 3 + 4 = 10 （表示前 4 個小區間共有 10 個元素）

注意，數組 a[j] 是單調遞增的，因為每個小區間的元素個數都在增加。

關鍵點：k = i - a[j]

• 數列中的位置 i 是在第 j+1 個區間中的某個元素。
• 前 j 個區間包含了 a[j] 個元素，也就是說，第 j+1 個區間的第一個元素出現在位置 a[j] + 1。

因此，位置 i 在第 j+1 個區間的具體位置是：

• 第 j+1 個區間的第 k 個元素：k 就是位置 i 相對于第 j+1 個區間開始位置的偏移量。

由于前 j 個區間包含了 a[j] 個元素，第 j+1 個區間從位置 a[j] + 1 開始。所以位置 i 在第 j+1 個區間中的具體位置是：

k = i - a[j]

#include <iostream>
using namespace std;
using ll=long long;
const int N=1414215;ll a[N],s[N];ll persum(ll i)
{ll l=0,r=N;while(l<r){ll mid=(l+r+1)>>1;if(a[mid]<i)l=mid;else r=mid-1;}return  s[l]+a[i-a[l]];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);for(int i=1;i<N;i++){a[i]=a[i-1]+i;s[i]=s[i-1]+a[i];}int t;cin>>t;while(t--){ll l,r;cin>>l>>r;cout<<persum(r)-persum(l-1)<<endl;}return 0;
}

雙指針

小齊的奶牛配對擠奶計劃

樣例輸入
3
1 8
2 5
1 2

樣例輸出
10

評測數據規模
$$1\le M\le 1,000,000,000，M為偶數，1\le N\le 100,000$$

#include <bits/stdc++.h>
using namespace std;/*問題描述：給定若干組輸入 (x, y)，表示有 x 頭奶牛，其擠奶產量為 y。這些 input 的 x 之和為 M（總奶牛數，且 M 為偶數）。將所有 M 頭奶牛分成 M/2 對，并行擠奶時的總耗時，取決于所有配對 (A, B) 的擠奶時間 A+B 的最大值。目標是找到所有可能配對中，使 max(A+B) 最小的方案，并輸出這個值。解決思路（雙指針）：1. 將每種產量 y 與其數量 x 記錄下來，并按照 y 升序排序。2. 設置兩端指針：left 指向最小產量，right 指向最大產量。3. 每次取盡可能多的奶牛對，數量為 min(左側剩余奶牛數, 右側剩余奶牛數)。4. 該批次配對的時間為 left 產量 + right 產量，用其更新全局最大值。5. 逐步減少兩側數量并移動指針，直至全部奶牛被配對完成。時間復雜度主要在對產量排序上，為 O(N log N)，其中 N 最多為 100000（不按單頭奶牛數量計）。
*/int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;// 記錄 (y, x)vector<pair<long long, long long>> cows;cows.reserve(N);long long totalCount = 0; // 用于計算奶牛總數 Mfor (int i = 0; i < N; ++i) {long long x, y;cin >> x >> y;cows.push_back({y, x});totalCount += x;}// 按產量升序排序sort(cows.begin(), cows.end(), [](auto &a, auto &b){return a.first < b.first;});// 雙指針：l 指向產量最小，r 指向產量最大int l = 0, r = (int)cows.size() - 1;long long res = 0;while (l <= r) {if (l == r) {// 剩余都在同一個產量上// 這時必然剩余的奶牛數為偶數，可以兩兩配對// 配對時間為 2 * cows[l].first// 但實際只需要一次就能給出最終答案res = max(res, 2LL * cows[l].first);break;}// 本輪可以配對的奶牛數long long num = min(cows[l].second, cows[r].second);// 對應配對時間long long sumTime = cows[l].first + cows[r].first;res = max(res, sumTime);// 扣除配對過的奶牛數cows[l].second -= num;cows[r].second -= num;// 如果左側產量用完，則左指針右移if (cows[l].second == 0) {++l;}// 如果右側產量用完，則右指針左移if (cows[r].second == 0) {--r;}}cout << res << "\n";return 0;
}

卓兒探尋全球變暖

樣例輸入
5 3
1 3 5 1 3
0 2 4

樣例輸出
1 2 1

$$1\le n,d\le 10^5,1\le h_i\le 10^9$$

暴力做法
變量含義：
? n 表示大樓數量，d 表示要查詢的天數。
? 數組 h 存儲每棟大樓的高度，數組 t 存儲每個查詢日對應的海平面高度。
? 布爾數組 st 標記某天是否“未被淹沒”（true 為未淹沒）。

對每個查詢日的處理：
(1) 將大樓中高 <= 當前海平面的全部標記為 false（表示已淹沒）。
(2) 隨后掃描所有大樓，累積計算未淹沒大樓所形成的連續“區域”數量：

• 如果遇到一段連續的 true（未淹沒大樓），則算作一個區域；
• 當連續的 true 被一個 false（淹沒大樓）打斷時，再出現下一段 true 時，就會有一個新的區域。
  (3) 將最終區域數輸出。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;// h[] 用于存儲每棟大樓的高度
// t[] 用于存儲不同查詢日的海平面高度
// st[] 用于標記某棟大樓今日是否仍未被淹沒
vector<int> h(N);
vector<int> t(N);
bool st[N];int main() {int n, d;// 輸入 n（大樓數量）和 d（查詢天數）cin >> n >> d;// 讀取大樓高度for (int i = 1; i <= n; i++) {cin >> h[i];}// 讀取查詢海平面天數數組for (int i = 1; i <= d; i++) {cin >> t[i];}// 將 st[] 初始化為 true，表示初始默認所有大樓都未被淹沒memset(st, true, sizeof(st));// 對每個查詢天數分別進行處理int region = 0;  // 表示當前查詢日下，未淹沒大樓所形成的區域數量for (int i = 1; i <= d; i++) {int day = t[i];    // 當前海平面高度region = 0;        // 每次查詢前重置區域數bool flag = false; // 標記是否在掃描大樓時已經遇到一個“連續未淹沒區域”// 1) 更新 st[j]: 若大樓高度 <= 當前海平面，則標記為已被淹沒 (false)for (int j = 1; j <= n; j++) {if (h[j] <= day) {st[j] = false;}}// 2) 統計當前未淹沒樓形成的連續區域數for (int j = 1; j <= n; j++) {if (st[j]) {// 如果此樓未淹沒并且尚未記錄一個新區域，則區域數加一if (!flag) {region++;flag = true;  // 進入新區域}} else {// 如果此樓已被淹沒，則結束之前的未淹沒區域標記flag = false;}}// 輸出當日的區域數cout << region << " ";}return 0;
}

雙指針+排序

1. 首先，將所有大樓 (高度, 下標) 按高度從小到大排序，便于后續根據海平面高度逐步淹沒。
2. 隨后，有一個雙指針循環：當海平面上升到 t[i] 時，就把所有高度 ≤ t[i] 的大樓“標記”為淹沒（分別存儲到 drown[i] 列表）。
3. 利用一個布爾數組 st[] 來標記下標為 x 的大樓是否已被淹沒；給 0 與 n+1 這兩個“邊界”強制設為已淹沒狀態（true），方便識別某大樓左右是否都是淹沒狀態。
4. 遍歷 drown[i]，對于每一個新淹沒的大樓 x：
   ? 若 x 左右均尚未淹沒，則此次淹沒會把原來的一個區域分割成兩個，因此區域計數 ans 增加 1。
   ? 若 x 左右均已經淹沒，則原先的兩個淹沒區在 x 處“連接”為一個區，區域計數 ans 減少 1。
   ? 最后將 x 標記為已淹沒。
5. 每次處理完后，輸出當前 ans 值，即此刻剩余未淹沒大樓的整體區域數量。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;bool st[N];
int main() {int n, d;cin >> n >> d;vector<pair<int,int>>h(n+1);// h[]數組存儲(大樓高度, 其原始下標)，下標從1開始使用for (int i = 1; i <= n; i++) {cin>>h[i].first;// 讀入大樓高度h[i].second=i; // 存儲對應的原始位置}// t[]數組存儲每個查詢的海平面高度(總共有d次查詢)vector<int> t(d);for (int i = 0; i < d; i++) {cin >> t[i]; // 讀入第i次查詢的海平面高度}// 將 h 中的大樓數據按高度升序進行排序sort(h.begin() + 1, h.end());// drown[i]存儲在第i次查詢中「新被淹沒」的大樓下標vector<vector<int>>drown(d);// 雙指針：i遍歷查詢，j遍歷大樓列表// 若 h[j+1].first <= t[i] => 說明該樓在第i次查詢時已經被淹沒// 則記錄其位置到drown[i]中表示本輪新增被淹沒的樓for (int i = 0, j = 0; i < d; i++) {while (j + 1 <= n && h[j + 1].first <= t[i]) {j++;drown[i].emplace_back(h[j].second);}}// st[x]用于標記下標為x的樓是否已被淹沒// 在邊界0和n+1處設置為true，方便判斷左右是否淹沒st[0] = true;      // 邊界視為已淹沒st[n + 1] = true;  // 邊界視為已淹沒int ans = 1;        // 當前未淹沒的大樓形成的區域數，初始設為1// 遍歷每個查詢，將在該日新增被淹沒的樓進行處理for(auto &u:drown){// u中存儲了本次查詢“剛好在海平面下”的大樓索引for(auto x:u){// 情況1：若左右都未被淹，則淹沒x會把一個連續區域分成兩部分 => 區域數 +1if(!st[x-1]&&!st[x+1]){ans+=1;}// 情況2：若左右都已淹，則淹沒x會將兩個淹沒區“連接”，相當于減少一個區域 => 區域數 -1if (st[x - 1] && st[x + 1]) {ans -= 1;}st[x]=true;}cout<<ans<<" ";}return 0;
}