CSP-J & GESP【课程4】算法

更新中

陈远龙老师主讲 & 答疑

课程题单 - T1004

未购买 · 可先试学8节课

课程目录展开/折叠

2.5 枚举法【05】

视频时长：01:01:01

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

播放快捷键

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

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

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

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

本节课讲解到的源代码

源代码下载：2.5 枚举法【05】-源代码下载

1. 【例题2-4】C1099 - 三角形个数-1 - 枚举 - 80分

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

int n;
const int N = 2e5 + 10;
int a[N]; // vector也可以 

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

    int ans = 0;
    // 枚举所有的可能的组合（三个角度）
    // 枚举的是索引 
    for (int i = 0; i < n; i ++)
    {
        for (int j = i + 1; j < n; j ++)
        {
            if (a[i] == a[j]) continue;
            for (int k = j + 1; k < n; k ++)
            {
                // a[i]、a[j]、a[k]
                if (a[k] == a[i] || a[k] == a[j]) continue;
                if (a[i] + a[j] + a[k] == 180)
                    ans ++;
            }
        }   
    } 
    cout << ans;

    return 0;
}

2. 【例题2-4】C1099 - 三角形个数-2 - 枚举 + 乘法原理 - 80分 - 数据类型不对

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

int n;
// const int N = 2e5 + 10;
// int a[N]; // vector也可以 
int t[200]; // 180

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int tmp;
        cin >> tmp;
        t[tmp] ++;
    }

    int ans = 0;
    // 枚举的是三个角度(j1 < j2 < j3)
    for (int j1 = 1; j1 < 180; j1 ++)
    {
        for (int j2 = j1 + 1; j2 < 180; j2 ++)
        {
            for (int j3 = j2 + 1; j3 < 180; j3 ++)
            {
                if (j1 + j2 + j3 == 180)
                {
                    ans += t[j1] * t[j2] * t[j3];
                }
            }
        }
    }
    cout << ans;

    return 0;
}

3. 【例题2-4】C1099 - 三角形个数-3 - 枚举 + 乘法原理 - 100分 - 3层循环

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

int n;
// const int N = 2e5 + 10;
// int a[N]; // vector也可以 
int t[200]; // 180

typedef long long ll;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int tmp;
        cin >> tmp;
        t[tmp] ++;
    }

    ll ans = 0;
    // 枚举的是三个角度(j1 < j2 < j3)
    for (int j1 = 1; j1 < 180; j1 ++)
    {
        for (int j2 = j1 + 1; j2 < 180; j2 ++)
        {
            for (int j3 = j2 + 1; j3 < 180; j3 ++)
            {
                if (j1 + j2 + j3 == 180)
                {
                    // 3000 * 4000 * 5000
                    ans += (ll)t[j1] * t[j2] * t[j3]; // int * int * int
                }
            }
        }
    }
    cout << ans;

    return 0;
}

4. 【例题2-4】C1099 - 三角形个数-4 - 枚举 + 乘法原理 - 100分 - 优化成2层循环

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

int n;
// const int N = 2e5 + 10;
// int a[N]; // vector也可以 
int t[200]; // 180

typedef long long ll;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int tmp;
        cin >> tmp;
        t[tmp] ++;
    }

    ll ans = 0;
    // 枚举的是三个角度(j1 < j2 < j3)
    for (int j1 = 1; j1 < 180; j1 ++)
    {
        for (int j2 = j1 + 1; j2 < 180; j2 ++)
        {
            int j3 = 180 - j1 - j2;
            if (j3 > j2)
            {
                ans += (ll)t[j1] * t[j2] * t[j3];
            } 
        }
    }
    cout << ans;

    return 0;
}

本节课课后练习题

详见题单 - T1004 - CSP-J & GESP【课程4】算法 - 第2章入门算法

本节课答疑

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

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

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