第18课 CSP-J大纲知识专题&初赛真题精讲

全面备考2025 CSP-J 初赛 & 复赛直播课

更新中

陈远龙老师主讲 & 答疑

课程题单 - T1005

未购买 · 可先试学24节课

课程目录展开/折叠

视频时长：56:44

视频 PPT&板书讲课代码课后练习

播放快捷键

播放/暂停：空格（或鼠标单击）全屏：F（或鼠标双击）退出全屏：Esc

快进10 / 30 / 60秒：方向键→ / Ctrl + 方向键→ / Shift + 方向键→

快退10 / 30 / 60秒：方向键← / Ctrl + 方向键← / Shift + 方向键←

本节课讲解配套PPT&板书：

本节课讲解到的源代码

源代码下载：第18课 CSP-J大纲知识专题&初赛真题精讲-源代码下载

1. 根号n的下界-1

#include <bits/stdc++.h>
using namespace std;

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

    // O(sqrt(n))
    /*
    int x;
    for (x = 1; x * x <= n; x ++);
    */
    int x;
    while (x * x <= n)
        x ++;
    cout << x - 1;

    return 0;
}

2. 根号n的下界-2

#include <bits/stdc++.h>
using namespace std;

// x * x <= n 符合条件的最大值
// x : [1, n] 解空间里二分查找 
// x具有单调性（可以把答案砍半）

int bSearch(int n)
{
    int l = 0, r = n;
    int ans;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (m * m <= n)
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    return ans;
}

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

    cout << bSearch(n) << endl;

    return 0;
}

3. 二分答案-模板-1

#include <bits/stdc++.h>
using namespace std;

// 找符合要求的最大值 
int bSearch(int n)
{
    int l = 0, r = n;
    int ans;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (check(m)) // 判定函数（判别是否符合要求） true false
        {
            ans = m;
            l = m + 1; // 需要找更大的解 
        }
        else
            r = m - 1; // 在左区间找可行解 
    }
    return ans;
}

int bSearch(int n)
{
    int l = 0, r = n;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (check(m)) // 判定函数（判别是否符合要求） true false
            l = m + 1; // 需要找更大的解 
        else
            r = m - 1; // 在左区间找可行解 
    }
    // return l; return r;
}

// 找符合要求的最小值 
int bSearch(int n)
{
    int l = 0, r = n;
    int ans;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (check(m)) // 判定函数（判别是否符合要求） true false
        {
            ans = m;
            r = m - 1; // 需要找更小的解 
        }
        else
            l = m + 1; // 在左区间找可行解 
    }
    return ans;
}

int bSearch(int n)
{
    int l = 0, r = n;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (check(m)) // 判定函数（判别是否符合要求） true false
            r = m - 1; // 需要找更小的解 
        else
            l = m + 1; // 在左区间找可行解 
    }
    // return l; return r;
}

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

    cout << bSearch(n) << endl;

    return 0;
}

本节课无课后练习

本节课答疑

建议大家有问题先通过AI答疑（比如：DeepSeek 等），AI时代需要学会使用AI辅助学习

陈远龙老师视频讲解：如何使用DeepSeek进行答疑？

通过AI未能获得满意解答的，可以联系陈远龙老师答疑