中石大第41次CSP培训Week3题解

作业链接：https://www.luogu.com.cn/contest/311112

邀请码：微信群通知

知识点：

前缀和
差分
二分
双指针

难度：普及-

赛时答疑与赛后题解：视频讲解，周六答疑

A.【深进1.例1】求区间和

【深进1.例1】求区间和

思路

一维前缀和

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, a, l, r;
int sum[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a;
        sum[i] = sum[i - 1] + a;
    }

    cin >> m;
    while(m --) {
        cin >> l >> r;
        cout << sum[r] - sum[l - 1] << endl;
    }

    return 0;
}

B. 第25次CSP认证第二题：出行计划

第25次CSP认证第二题：出行计划（洛谷团队比赛）

第25次CSP认证第二题：出行计划（AcWing）

思路

一维差分

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
const int C = 2e5 + 5;

int n, m, k, t, c, q;
long long diff[N], ans[N];

int main() {
    cin >> n >> m >> k;
    
    while(n --) {
        cin >> t >> c;
        diff[C + t - c] ++;
        diff[C + t] --;
    }

    for(int i = 1; i <= N; i ++)
        ans[i] = ans[i - 1] + diff[i];

    while(m --) {
        cin >> q;
        cout << ans[C + q + k - 1] << endl;
    }

    return 0;
}

C. 第22次CSP认证第二题：邻域均值

第22次CSP认证第二题：邻域均值（洛谷团队比赛）

第22次CSP认证第二题：邻域均值（AcWing）

思路

二维前缀和

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int n, L, r, t, ans, a;
int b[N][N];

int main() {
    cin >> n >> L >> r >> t;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            cin >> a;
            b[i][j] = a + b[i-1][j] + b[i][j-1] - b[i-1][j-1];
        }
    }
    int xl, xr, yl, yr;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            xl = (i > r) ? i - r - 1 : 0;
            xr = (i < n - r + 1) ? i + r : n;
            yl = (j > r) ? j - r - 1 : 0;
            yr = (j < n - r + 1) ? j + r : n;
            if(b[xr][yr] - b[xl][yr] - b[xr][yl] + b[xl][yl] <= t * (xr - xl) * (yr - yl)) 
                ans ++;
        }
    }

    cout << ans << endl;
    return 0;
}

D. 银行贷款

银行贷款

思路

二分答案

P (Principal)：贷款原值（期初本金，例如样例 1000 元）。

A (Annuity)：每期等额还款额（例如样例每月 100 元）。

i (Interest rate)：每期固定利率（即要求解的月利率）。

n (Number of periods)：总还款期数（例如样例 12 个月）。

F_n (Future value)：第 n 期期末还款后的剩余欠款余额。

周期 (n)	期初欠款	本期产生利息	本期还款	期末剩余欠款 (F_n)
1	P	P ⋅ i	A	P(1 + i) − A
2	P(1 + i) − A	[P(1 + i) − A] ⋅ i	A	P(1 + i)² − A(1 + i) − A
3	P(1 + i)² − A(1 + i) − A	F₂ ⋅ i	A	P(1 + i)³ − A(1 + i)² − A(1 + i) − A
…	…	…	…	…
n	F_n − 1	F_n − 1 ⋅ i	A	P(1 + i)ⁿ − [A(1 + i)^n − 1 + … + A(1 + i) + A]

易得年金现值公式：

$$ P = A \frac{(1+i)^n - 1}{i(1+i)^n} $$

浮点数比较需要设定精度
建议开long double类型

代码

#include <bits/stdc++.h>

using namespace std;

long double w0, w;
int m;

const long double eps = 1e-6;

// (1+i)^n
long double f(long double i, int n) {
    long double ret = 1;
    while(n --) 
        ret *= (1 + i);
    return ret;
}

// P/A = [(1+i)^n - 1] / [i * (1+i)^n]
long double P_Div_A(long double i, int m) {
    long double fim = f(i, m);
    return (fim - 1) / (i * fim);
}

int main() {
    cin >> w0 >> w >> m;

    long double t = w0 / w;

    long double l = 0, r = 3;
    while(r - l > eps) {
        long double mid = (l + r) / 2;
        if(t - P_Div_A(mid, m) > eps) r = mid;
        else l = mid;
    }

    printf("%.1Lf\n", roundl(l * 1000) / 10);

    return 0;
}

E. 第29次CSP认证第二题：垦田计划

第29次CSP认证第二题：垦田计划（洛谷团队比赛）

第29次CSP认证第二题：垦田计划（AcWing）

方法一

思路

二分答案

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

long long n, m, k;
long long t[N], c[N];

bool check(long long x) {
    long long v = 0;
    for(int i = 0; i < n; i ++)
        if(t[i] > x)
            v += c[i] * (t[i] - x);
    return v <= m;
}

int main() {
    cin >> n >> m >> k;

    for(int i = 0; i < n; i ++)
        cin >> t[i] >> c[i];

    long long l, r, mid;
    l = k;
    r = N;

    while(l < r) {
        mid = (l + r) >> 1;

        if(check(mid))
            r = mid;
        else
            l = mid + 1;
    }

    cout << r << endl;
    return 0;
}

方法二

思路

贪心算法+桶排序的思想。

核心是 “削峰填谷”。

数组 m[t] 作为“桶”：耗时为 t 天的所有田地，如果想集体缩减 1 天，需要的总资源。

天数递减顺序枚举，直到资源不够。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, k, t, c, maxt, ans;   // maxt 代表最大的完工时长
int p[N];

int main() {
    cin >> n >> m >> k;

    for(int i = 0; i < n; i ++) {
        cin >> t >> c;
        p[t] += c;        // p[i] 代表相同完工时长所需的总费用
        maxt = max(maxt, t);
    }

    for(int i = maxt; i > 0; i --)
        p[i - 1] += p[i]; // p[i] 代表不大于 i 的完工时长所需的总费用

    for(int i = maxt; i > k; i --) {
        if(m < p[i]) {    // 如果预算不足以支付完工时长不大于 i 的费用
            ans = i;      // 那么答案就是 i
            break;
        }
        m -= p[i];        // m 代表剩余的预算
    }
    ans = max(ans, k);    // 如果预算足以支付完工时长不大于 k 的费用，那么答案就是 k
    cout << ans << endl;
    return 0;
}

F. [蓝桥杯 2025 省 A/Python B 第二场] 消消乐

[蓝桥杯 2025 省 A/Python B 第二场] 消消乐

思路

双指针

代码

#include <bits/stdc++.h>

using namespace std;

string s;
int n, ans;

int main() {
    cin >> s;
    n = s.size();
    int i = 0, j = n - 1;
    ans = n;
    while(i < j) {
        while(i < n && s[i] != 'A') i ++;
        while(j >= 0 && s[j] != 'B') j --;
        if(i >= j) break;
        ans -= 2;
        i ++;
        j --;
    }
    cout << ans << endl;
    return 0;
}

G. 第21次CSP认证第二题：期末预测之最佳阈值

第21次CSP认证第二题：期末预测之最佳阈值（洛谷团队比赛）

第21次CSP认证第二题：期末预测之最佳阈值（AcWing）

思路

排序+前缀和

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

struct Node {
    int y, result;
} arr[N];

bool cmp(Node a, Node b) {
    return a.y < b.y;
}

int m, ans, max_res;
int sum1[N], sum0[N], num[N];

int main() {
    cin >> m;
    for(int i = 0; i < m; i ++)
        cin >> arr[i].y >> arr[i].result;
    sort(arr, arr + m, cmp);

    int prev_num = -1;
    int cnt = 0;
    for(int i = 0; i < m; i ++) {
        if(arr[i].y != prev_num) {
            cnt ++;
            prev_num = arr[i].y;
            sum0[cnt] = sum0[cnt - 1];
            sum1[cnt] = sum1[cnt - 1];
            num[cnt] = arr[i].y;
        }
        sum1[cnt] += (arr[i].result == 1);
        sum0[cnt] += (arr[i].result == 0);
    }

    for(int i = 1; i <= cnt; i ++) {
        int res = sum0[i - 1] + sum1[cnt] - sum1[i - 1];
        if(res >= max_res) {
            max_res = res;
            ans = num[i];
        }
    }

    cout << ans << endl;
    return 0;
}

H. A-B 数对

A-B 数对

方法一：二分查找

思路

问题变为a = b + c

先排序，循环遍历b，对应每个b查找有几个a

排序：O(nlogn)

循环遍历b，同时查找每个b对应几个a：n重循环，每重循环内二分查找O(logn)；总计O(nlogn)

所以，总复杂度为O(nlogn)

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n;
long long c, ans;
long long a[N];

int main() {
    cin >> n >> c;
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    sort(a, a + n);

    // a = b + c
    for(int i = 0; i < n; i ++) // 循环遍历b
        ans += upper_bound(a, a + n, a[i] + c) - lower_bound(a, a + n, a[i] + c);
    // upper_bound(a, a + n, a[i] + c) 找到第一个大于a[i] + c的元素
    // lower_bound(a, a + n, a[i] + c) 找到第一个大于等于a[i] + c的元素

    cout << ans << endl;
    return 0;
}

方法二：双指针

思路

a[j]指向a
a[i]指向b

找到符合要求的ab数对后，跳过和ab相同的数字

指向a的j指针永远不会往前，双指针时间复杂度为O(n)

而排序的时间复杂度为O(nlogn)

所以总时间复杂度为O(nlogn)

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

unsigned long long n, c, ans;
unsigned long long a[N];

int main() {
    cin >> n >> c;
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    sort(a, a + n);
    int j = 1;
    for(int i = 0; i < n; i ++) {
        while(j < n && a[j] < a[i] + c) j ++;
        if(j == n) break;
        if(a[j] > a[i] + c) continue;
        long long cnt1 = 0, cnt2 = 1;
        while(j < n && a[j] == a[i] + c) {
            j ++;
            cnt1 ++;
        }
        while(a[j - 1] == a[i + 1] + c) {
            i ++;
            cnt2 ++;
        }
        ans += cnt1 * cnt2;
    }
    cout << ans << endl;
    return 0;
}

方法三：STL

思路

本质上，我们一直在遍历b，然后找有几个对应的a

正好，STL里面的map、set等容器可以实现功能，且时间复杂度很低

单次查找时间复杂度为O(logn)

总时间复杂度为O(nlogn)

代码

#include <bits/stdc++.h>

using namespace std;

int n;
long long c, ans, num;

map<long long, long long> mp;

int main() {
    cin >> n >> c;
    for(int i = 0; i < n; i ++) {
        cin >> num;
        mp[num] ++;
    }
    // a = b + c
    // 遍历map中的每个元素，得到b
    for(auto &p : mp) {
        long long b = p.first;
        long long a = b + c;
        // 计算b + c的个数
        if(mp.count(a))
            ans += mp[a] * p.second;    // b值的数的个数 * （b+c）值的个数
    }

    cout << ans << endl;

#ifdef LOCAL
    system("pause");
#endif
    return 0;
}

中石大CSP培训 > 第41次

#CSP #题解 #算法 #前缀和 #差分 #二分 #双指针

中石大第41次CSP培训Week3题解

https://blog.yanjz.top/CUP-CSP41-week3/

作者

严嘉哲

发布于

2026年3月1日

许可协议

中石大第41次CSP培训Week4题解上一篇

51单片机流式混合运算计算器下一篇