C/C++蓝桥杯算法真题打卡（Day4）
一、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;
}代码说明
-
二分查找：
-
通过二分查找确定第 n 个满足条件的数。
-
查找范围从 1 到 1e18（足够大的数）。
-
-
容斥原理：
-
mid / 20：计算 mid 以内 20 的倍数的个数。 -
mid / 24：计算 mid 以内 24 的倍数的个数。 -
mid / 120：减去 20 和 24 的最小公倍数的个数（避免重复计算）。
-
-
时间复杂度：
-
二分查找的时间复杂度为 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){//求区间gcd
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(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。
代码优化建议
-
变量命名：
-
变量名如
lc、rc、nord等不够直观，建议改为更具描述性的名称，如left_child、right_child、Node等。
-
-
代码可读性：
-
添加注释，解释关键逻辑和变量的含义。
-
使用空格和换行符提高代码的可读性。
-
-
边界条件处理：
-
确保数组下标从 1 开始，避免越界问题。
-
在滑动窗口枚举时，注意
i和j的移动条件。
-
-
时间复杂度：
-
线段树构建的时间复杂度为 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);
// 特殊情况：数组中已经有 1
if (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 问题。修正后的代码提高了可读性和健壮性，同时保留了原有的高效逻辑。