前言

简介：涉及枚举法（暴力法），题目源于洛谷
建议大家先自行尝试解题，同时阿鑫的水平不高，所以题解也通常并不算好，建议大家可以在洛谷相关题目的题解处查看其他大佬的题解，阿鑫的题解简单看看就好。

所谓枚举法，枚举所有的可能，从而得到答案的方法。但由于其简单粗暴，常常有多余运算，所以通常只适合运算量不算大的题目。

练习

洛谷P2089 烤鸡

题目链接：洛谷P2089 烤鸡

题目描述
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10 种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。
现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 10 种配料的所有搭配方案。
输入格式
一个正整数 n，表示美味程度。
输出格式
第一行，方案总数。
第二行至结束，10 个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个 0。
输入输出样例
输入
11
输出
10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
说明/提示
对于100% 的数据， n≤5000。

解题思路

首先虽然数据范围给到了5000，但是我们不难想到实际上只有n为10到30才有解，所以不在这个范围内的可以直接输出0。

而由于总共只有10种调料，每种调料的取值范围只有1到3，所以即使我们一层一层逐个枚举（时间复杂度为n¹⁰）,也就3¹⁰=9⁵<10⁵。可以时间方面说是非常安全的，而且按顺序枚举，也恰好符合字典序。</sup>

所以该题只需要按顺序枚举，如果各个调料之和等于n，则输出当前各调料的值。

ac题解

#include <bits/stdc++.h> 
using namespace std;  
int main()
{
    int n,i[10],sum,ans=0;
    string s;    //存储答案
    cin>>n;
    if(n<10||n>30) cout<<0<<endl;
    else{
        //十种调料依次枚举
        for(i[0]=1;i[0]<=3;i[0]++)
        for(i[1]=1;i[1]<=3;i[1]++)
        for(i[2]=1;i[2]<=3;i[2]++)
        for(i[3]=1;i[3]<=3;i[3]++)
        for(i[4]=1;i[4]<=3;i[4]++)
        for(i[5]=1;i[5]<=3;i[5]++)
        for(i[6]=1;i[6]<=3;i[6]++)
        for(i[7]=1;i[7]<=3;i[7]++)
        for(i[8]=1;i[8]<=3;i[8]++)
        for(i[9]=1;i[9]<=3;i[9]++){
            int sum=0;
            for(int j=0;j<10;j++){
                sum+=i[j];
            }
            if(sum==n){//如果符合
                ans++;
                for(int j=0,sum=0;j<10;j++){
                    s+=(i[j]+'0');    //答案用字符串存
                    s+=+" ";
                }        
                s+='\n';
            }    
        }
        cout<<ans<<endl<<s;
    }
    return 0; 
}

洛谷P1036NOIP2002 普及组

题目链接:洛谷P1036NOIP2002 普及组

题目描述
已知 n个整数 x₁,x₂,...,x_n,，以及 1个整数 k（k 3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=29。
输入格式
第一行两个空格隔开的整数 n,k（1 ≤ n ≤ 20，k 第二行 n 个整数，分别为 x₁,x₂,...,x_n,（1 ≤ x_i≤ 5*10⁶）。
输出格式
输出一个整数，表示种类数。
样例
样例输入
4 3
3 7 12 19
样例输出
1
提示
题目来源
NOIP 2002 普及组第二题

解题思路

首先这道题目的n取值范围很小（n ≤ 20），最大排列组合下也就C₂₀¹⁰=184756<10⁶,所以暴力枚举是可行的。</sup>

那么这题主要分为两步，一是深搜找到所有可能解，二是判断可能解中的质数。

ac代码

//用时：19ms 内存：812.00kb
#include <bits/stdc++.h>
using namespace std;

vector<int> v;    //存储可能解    
int n,k,ans; 
int a[25],b[25];

//判断是否是质数
bool isprime(int x){
    int i;
    for(i=2;i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}

//x当前是第几位数字，step在取第几位数字，k总共要取多少位数字，sum当前总和
void dfs(int x,int step,int k,int sum){
    int i;
    if(step == k) {        //如果找到了K个数字即可结束当次
        v.push_back(sum);    //保存结果
        return;
    } 
    if(n-x<k-step) return;    //如果后面的数字已经不够了，则直接结束
    for(i=x+1;i<=n;i++){    //枚举选取下一位数字的每种可能
        dfs(i,step+1,k,a[i]+sum);
    }
}

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

    for(i=1;i<=n-k+1;i++){  //枚举选取第一位数字的每种可能
        dfs(i,1,k,a[i]);
    }

    //遍历其中为质数的
    for(i=0;i<v.size();i++){
        if(isprime(v[i])) ans++;
    }

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

洛谷P3799 妖梦拼木棒

题目链接:洛谷P3799 妖梦拼木棒

题目描述
有 n根木棒，现在从中选 4 根，想要组成一个正三角形，问有几种选法？
答案对 10⁹+7 取模。
输入格式
第一行一个整数 n。
第二行往下 n 行，每行 1 个整数，第 i 个整数 a_i 代表第 i 根木棒的长度。
输出格式
一行一个整数代表答案。
样例
样例输入
4
1
1
2
2
样例输出
1
提示
数据规模与约定
对于 30% 的数据，保证 n ≤ 5 10³。
对于 100% 的数据，保证 1 ≤ n ≤ 10⁵，0 ≤ a_i ≤ 5 10³。

解题思路

首先这道题目的a_i 取值范围不是很大（0 ≤ a_i ≤ 5 * 10³），所有我们可以考虑用数组a[i]来存有 a[i] 个长度为 i 的木棍。

四条木棍组成一个正三角形，即两个一样长度为x的木棍加上两根长度加起来和为x的木棍。

所以只需要依次枚举数量大于等于2的木棍，再去寻找有无两根木棍加起来长度可与其组成正三角形。

需要注意的点:同一长度的木棒不代表是同一根木棒。所以对于选的两根一样的木棒我们需要排列组合C²_a[i]=a[i]*(a[i]-1)/2。其余的亦然。

ac代码

//时间：197ms（O2：113ms） 内存：808.00KB
#include <bits/stdc++.h> 
using namespace std;  
const int MO=1000000007;
int a[5005],n;
long long ans=0;
int main()
{
    int i,j,tmax=0,t;
    cin>>n;
    for(i=0;i<n;i++){
        scanf("%d",&j);
        a[j]++;
        tmax=max(tmax,j);
    } 

    //核心代码
    for(i=1;i<=tmax;i++){
        if(a[i]>=2){
            t=a[i]*(a[i]-1)/2;
            for(j=1;j*2<i;j++){
                if(a[j]&&a[i-j]) ans+=a[j]*a[i-j]*t;
            }
            if((i%2==0)&&a[i/2]>=2){
                ans+=a[i/2]*(a[i/2]-1)/2*t;
                ans%=MO; 
            }
        }
    }


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