一、P11041 [藍橋杯 2024 省 Java B] 報數游戲 - 洛谷

算法代碼：

#include<bits/stdc++.h>
using namespace std;// 計算第 n 個滿足條件的數
long long findNthNumber(long long n) {long long low = 1, high = 1e18; // 二分查找范圍while (low < high) {long long mid = (low + high) / 2;// 計算 mid 以內 20 或 24 的倍數的個數long long count = mid / 20 + mid / 24 - mid / 120;if (count < n) {low = mid + 1;} else {high = mid;}}return low;
}int main() {long long n = 202420242024;long long result = findNthNumber(n);cout << result << endl;return 0;
}

代碼說明

1. 二分查找：

   • 通過二分查找確定第 n 個滿足條件的數。

   • 查找范圍從 1 到 1e18（足夠大的數）。

2. 容斥原理：

   • mid / 20：計算 mid 以內 20 的倍數的個數。

   • mid / 24：計算 mid 以內 24 的倍數的個數。

   • mid / 120：減去 20 和 24 的最小公倍數的個數（避免重復計算）。

3. 時間復雜度：

   • 二分查找的時間復雜度為 O(log N)，效率非常高。

二、P8792 [藍橋杯 2022 國 A] 最大公約數 - 洛谷

算法代碼：?

#include<bits/stdc++.h>
#define int long long
#define lc 2*k
#define rc 2*k+1
using namespace std;
int n,a[1234567],cnt;
struct nord{int l,r,mx;
}t[1234567];
void build(int k,int l,int r){//建樹t[k].l=l,t[k].r=r;if (l==r){t[k].mx=a[l];return ;}int mid=(l+r)/2;build(lc,l,mid);build(rc,mid+1,r);t[k].mx=__gcd(t[lc].mx,t[rc].mx);
}
int ask(int k,int l,int r){//求區間gcdif (l<=t[k].l&&r>=t[k].r) return t[k].mx;int ans=0;int mid=(t[k].l+t[k].r)/2;if (l<=mid) ans=__gcd(ans,ask(lc,l,r));if (r>mid) ans=__gcd(ans,ask(rc,l,r));return ans;
}
main(){cin>>n;for (int i=1;i<=n;i++) cin>>a[i],cnt+=(a[i]==1?1:0);build(1,1,n);if (cnt){//特殊情況cout <<n-cnt;return 0;}int ans=1e9;int i=1;for (int j=1;j<=n;j++){//枚舉while (i<j&&ask(1,i+1,j)==1) i++;//一直往前走if (ask(1,i,j)==1) ans=min(ans,j-i);//成功了}if (ans==1e9) cout <<-1;//不合法else cout <<n+ans-1;return 0;
}

????????這段代碼的主要功能是解決一個與區間 GCD（最大公約數）相關的問題。以下是代碼的思路和邏輯分析：

---

代碼思路

1.?問題描述

• 給定一個長度為?n?的數組?a。

• 目標是找到一個最短的區間?[i, j]，使得該區間內所有元素的 GCD 為 1。

• 如果存在這樣的區間，輸出將整個數組變為全 1 的最小操作次數；否則輸出 -1。

2.?核心邏輯

• 特殊情況處理：

  • 如果數組中已經有?cnt?個 1，則直接輸出?n - cnt，因為只需要將其他元素變為 1 即可。

• 區間 GCD 計算：

  • 使用線段樹維護區間 GCD，支持快速查詢任意區間的 GCD。

• 滑動窗口枚舉：

  • 使用雙指針?i?和?j?枚舉區間?[i, j]。

  • 如果區間?[i, j]?的 GCD 為 1，則嘗試縮小窗口（移動?i）以找到更短的區間。

  • 記錄滿足條件的最短區間長度。

• 結果計算：

  • 如果找到滿足條件的區間，輸出?n + ans - 1（將整個數組變為全 1 的最小操作次數）。

  • 否則輸出 -1。

---

代碼邏輯分析

1.?線段樹構建

• build?函數用于構建線段樹，每個節點存儲區間的左右邊界和區間 GCD。

• 遞歸地將數組劃分為左右子區間，直到區間長度為 1。

• 區間 GCD 通過?__gcd?函數計算。

2.?區間 GCD 查詢

• ask?函數用于查詢區間?[l, r]?的 GCD。

• 如果當前節點區間完全包含在查詢區間內，則直接返回節點值。

• 否則遞歸查詢左右子區間，并計算 GCD。

3.?滑動窗口枚舉

• 使用雙指針?i?和?j?枚舉區間。

• 如果區間?[i, j]?的 GCD 為 1，則嘗試縮小窗口（移動?i）。

• 記錄滿足條件的最短區間長度?ans。

4.?結果計算

• 如果找到滿足條件的區間，輸出?n + ans - 1。

• 否則輸出 -1。

---

代碼優化建議

1. 變量命名：

   • 變量名如?lc、rc、nord?等不夠直觀，建議改為更具描述性的名稱，如?left_child、right_child、Node?等。

2. 代碼可讀性：

   • 添加注釋，解釋關鍵邏輯和變量的含義。

   • 使用空格和換行符提高代碼的可讀性。

3. 邊界條件處理：

   • 確保數組下標從 1 開始，避免越界問題。

   • 在滑動窗口枚舉時，注意?i?和?j?的移動條件。

4. 時間復雜度：

   • 線段樹構建的時間復雜度為 O(n)。

   • 區間查詢的時間復雜度為 O(log n)。

   • 滑動窗口枚舉的時間復雜度為 O(n log n)。

   • 總體時間復雜度為 O(n log n)，效率較高。

---

修正后的代碼

#include<bits/stdc++.h>
#define int long long
using namespace std;const int MAXN = 1234567;
int n, a[MAXN], cnt;struct Node {int l, r, mx;
} t[MAXN * 4];// 構建線段樹
void build(int k, int l, int r) {t[k].l = l, t[k].r = r;if (l == r) {t[k].mx = a[l];return;}int mid = (l + r) / 2;build(2 * k, l, mid);build(2 * k + 1, mid + 1, r);t[k].mx = __gcd(t[2 * k].mx, t[2 * k + 1].mx);
}// 查詢區間 GCD
int ask(int k, int l, int r) {if (l <= t[k].l && r >= t[k].r) return t[k].mx;int ans = 0;int mid = (t[k].l + t[k].r) / 2;if (l <= mid) ans = __gcd(ans, ask(2 * k, l, r));if (r > mid) ans = __gcd(ans, ask(2 * k + 1, l, r));return ans;
}signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];cnt += (a[i] == 1 ? 1 : 0);}build(1, 1, n);// 特殊情況：數組中已經有 1if (cnt) {cout << n - cnt << endl;return 0;}int ans = 1e9;int i = 1;// 滑動窗口枚舉for (int j = 1; j <= n; j++) {while (i < j && ask(1, i + 1, j) == 1) i++;if (ask(1, i, j) == 1) ans = min(ans, j - i + 1);}// 輸出結果if (ans == 1e9) cout << -1 << endl;else cout << n + ans - 1 << endl;return 0;
}

---

總結

????????這段代碼通過線段樹和滑動窗口的結合，高效地解決了區間 GCD 問題。修正后的代碼提高了可讀性和健壯性，同時保留了原有的高效邏輯。