【洛谷题单】暴力枚举（上）
【前情提要】
此文章包含洛谷题单的枚举题单，共14题，本篇7道题，主要分析思路，并通过这几道题目，进行总结有关枚举的内容。所以内容比较多，可以先收藏起来，慢慢看。
题单链接：暴力枚举
https://www.luogu.com.cn/training/108
题目1
分析1
在一个n行m列的棋盘里，找一共有多少正方形和长方形。
而正方形和长方形都属于矩形，区别只有长宽长度的问题，那么可以一并按照矩形分析，当长宽相等时是正方形，否则是长方形。
再接着想，该如何算出棋盘里有多少矩形呢？
首先假设是一个1x2的矩形，把它当作一块积木，放入棋盘中，那么它可以横着放，也可以竖着放。
1. 当它横着放，一共有多少种可能性？（假设棋盘长为n，宽为m）
- 当我们只关注宽时——发现一共有m-1个长度为2的地方，
- 当只关注长时——一共有n个长度为1的地方
最终结果为n*m-1
2. 而竖着放同理。
我们可以大胆猜测，长为a宽为b的矩形一共有（n-a+1）*（m-b+1）
那么我们为了更保险一些，再举个例子，假设求3x3矩形的个数
1. 当它横着放，一共有多少种可能性？（假设棋盘长为n，宽为m）
- 当我们只关注宽时——发现一共有m-2个长度为3的地方，
- 当只关注长时——一共有n-2个长度为3的地方
最终结果为(n-2)*(m-2)
2. 由于是正方形，不需要看竖着的情况
基本正确，为了更严谨一些，可以再尝试举出类似例子。
那根据这个思路，我们可以进一步写出代码，注意范围，那么谈到范围时，我们就要想到假如横着竖着去考虑的话，从横着的1x2到竖着的2x1,假设长方向的设为i，宽方向的设为j
那么对应着i=1,j=2和i=2,j=1,两种情况
而i的范围为从1到n，j的范围为1到m，只需要在里面遍历就可以出现上面这两种情况，所以不需要再多考虑。
代码1
#include<bits/stdc++.h>
using namespace std;
long long ans,res;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==j)//正方形
{
ans+=(n-i+1)*(m-i+1);
}else{
res+=(n-i+1)*(m-j+1);//求长方形，长宽方向已固定，所以不需要看纵向和横向结果
}
}
}
cout << ans << " " << res << endl;
return 0;
}总结1
这题的核心点在于如何求出矩形数量，通常情况下可以多多列举几个例子，去分析，然后推出整体的公式。
题目2
对于 100% 的数据，n≤5000。
分析2
题目意思是给你一个数字m，把10个数字（每个数字范围为1到3）的加和变成这个数字，并输出方案数和具体方案内容。
显而易见10个循环是不行的，超出时间复杂度了。
所以只能另辟蹊径。
用dfs（也就是深度优先遍历）
不懂的可以先看这篇（觉得麻烦也可以不看，下面会简单说明）——dp_背包问题(涉及dfs分析，记忆化搜索)_固定背包体积装物品总价值最大,运筹学问题-CSDN博客
只需要看dfs的部分即可
简单来说，就是先假设第一个数字为1，在这个基础上有三种选择，第二个数字有可能是1，2，3，我们先选择1再进行考虑第三个数字，直到考虑完10个数字.
假设最后结果为m则算是一种方案（然后遍历输入？），回溯到考虑第十个数字，这里我们选择2。
如果结果不为m，则这种方案不算，要去考虑第十个数字，选择2。
理论成立，下面就是代码了。
代码2
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int a[N][11],s[11];
int n;
int res;
void dfs(int x,int p){
if(x==10){
if(p!=n){
return;
}
for(int i=0;i<10;i++)
{
a[res][i]=s[i];
}
res+=1;
return;
}
s[x]=1;
dfs(x+1,p+1);
s[x]=2;
dfs(x+1,p+2);
s[x]=3;
dfs(x+1,p+3);
return;
}
int main(){
scanf("%d",&n);
dfs(0,0);//0表示调料的总克数
cout<<res<<endl;
for(int i=0;i<res;i++){
for(int j=0;j<10;j++){
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}总结2
这是一道简单的dfs题，按照正常递归思路思考回溯即可
题目3
分析
9个数字，组合成三个数A,B,C，满足一定的比例关系。
那么假如我们已经知道了A，则可以根据比例求出B和C，再去判断满足不满足每个数字只在A,B,C,中出现且仅出现一次的条件。
那么怎么去实现呢？
1. A是怎么遍历的
2. 怎么判断每个数字在A,B,C中有且仅出现一次
首先，A是由1到9这几位数字中抽出三个数字组合而成的。
A的第一位有9种可能性，第二位有除了第一位以外的其余8种可能性，第三位有7种可能性
假设我们嵌套遍历——A的每一位数字，把A弄出来之后，再计算B和C,再设置变量存储B和C的每一位数字，确保每一位都不相等——则输出A,B,C
假如没有输出（可以借用bool变量判断，刚开始定义为false如果输出了则该变量等于true，最后根据这个看是否输出No!!!）则输出No!!!
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
double a,b,c;
bool f=false;
cin>>a>>b>>c;
if(a==b||a==c||b==c)
{
cout<<"No!!!";
return 0;
}
b/=a;
c/=a;
for(int i=1;i<10;i++)
{
for(int j=1;j<10;j++)
{
for(int k=1;k<10;k++)
{
if(i!=j&&i!=k&&j!=k)
{
int n1=i*100+j*10+k;
int n2=n1*b;
int s1=n2%10;
int s2=n2%100/10;
int s3=n2/100;
if(s1!=s2&&s1!=s3&&s2!=s3&&s1!=i&&s1!=j&&s1!=k&&s2!=i&&s2!=j&&s2!=k&&s3!=i&&s3!=j&&s3!=k&&n2<1000&&s1!=0&&s2!=0&&s3!=0)
{
int n3=n1*c;
int p1=n3%10;
int p2=n3%100/10;
int p3=n3/100;
if(p1!=p2&&p1!=p3&&p2!=p3&&p1!=i&&p1!=j&&p1!=k&&p1!=s1&&p1!=s2&&p1!=s3&& p2!=i&&p2!=j&&p2!=k&&p2!=s1&&p2!=s2&&p2!=s3&& p3!=i&&p3!=j&&p3!=k&&p3!=s1&&p3!=s2&&p3!=s3&&n3<1000&&p1!=0&&p2!=0&&p3!=0)
{
cout<<n1<<" "<<n2<<" "<<n3<<endl;
f=true;
}
}
}
}
}
}
if(!f)
{
cout<<"No!!!";
}
return 0;
}总结
这题主要是分析，分析出来如何做的写代码就简单了
题目4
分析
题目意思是给你n个数，从中选k个，加和，判断和是否为素数，如果是则种类加1
那么这题代码主要点在于——1. 从n个数中选k个，2 判断和是否为素数
分别考虑如何实现
1. 从n个数中选则k个，首先可以用for循环遍历取得k位数字，也可以用dfs函数，把n个数填在k个格子里面，每个数只能用一次。
2. 判断是否为素数，单开一个函数即可，从素数的定义入手，素数是指从1到本身，它只能%1和它本身时==0，为了简便，可以把范围从sum缩小到sqrt(sum)
理论上我们已经分析出做法了，那么下面就是具体的实施了
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int a[21];
int k,res,n,flag;
//bool s[21];
int startid;
bool issu(int p)
{
if (p < 2) return false;
for (int i = 2; i <= sqrt(p); i++) {
if (p % i == 0) return false;
}
return true;
}
void dfs(int x)
{
if(x==k)
{
if(issu(res))
{
flag++;
}
return;
}else
{
int start=startid;
for(int i=start;i<n;i++)
{
res+=a[i];
startid=i+1;
dfs(x+1);
res-=a[i];
startid=start;
}
}
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
dfs(0);
cout<<flag<<endl;
return 0;
}总结
代码中有个重要的点——》就是在dfs中如何防止元素重复，也就是这个元素用过了，如何防止下次不再用。我们把这部分的代码拿出来分析
首先定义了
int start=startid;
for(int i=start;i<n;i++)
{
res+=a[i];
startid=i+1;
dfs(x+1);
res-=a[i];
startid=start;
}
//把dfs函数参数设置为三个
void dfs(int e,int sum,int x)//x表示下一回的开始
{
if(e==k)
{
if(isPrime(sum))
{
res++;
}
return;
}
for(int i=x;i<n;i++)
{
dfs(e+1,sum+s[i],i+1);//下一回从i+1开始
}
return;
}这个部分建议记忆，在很多题目中也可能会用到。
题目5
分析
这个题说的是从n个元素中抽出r个元素，输出所有组合，（格式是每个组合数字要占三个字符，用到setw()，或者直接用printf格式化输出）
我们来看如何去写，
依旧是假设有r个位置，要把n个元素不重复的填入进去，每个位置有多种选择，可以用dfs来实现
代码（dfs）
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
const int N=21;
int s[N];
int n,r;
void dfs(int e,int f,int x)
{
if(e==r)
{
for(int i=0;i<r;i++)
{
cout<<setw(3)<<s[i];
}
cout<<endl;
return;
}
for(int i=f;i<r;i++)
{
for(int j=x;j<=n;j++)
{
s[i]=j;
if(s[i-1]<s[i])
{
dfs(e+1,f+1,j+1);
//s[i]=0;//为什么不用还原？因为下一次会被覆盖
}
}
}
}
int main()
{
scanf("%d%d",&n,&r);
dfs(0,0,1);
return 0;
}总结
这个依旧用到了上个问题的不重复写入的方法，但这道题目和上一题不一样的是它需要把每次的结果存入数组中，所以需要再加一个for循环，但是为了不让数组每次遍历都从头开始，再设置一个参数，表示数组的位置。
题目6
分析
这题就是直接给你一共数，输出1到这个数的全排列。
有两种方法
1. 调用库函数next_permutation
2. 自己手写全排列函数
根据这个方法，我们依次分析一下
1. 库函数next_permutation()，里面传入两个参数，第一个是数组的首地址，第二个是数组的末地址，和sort函数差不多，它返回这个数组的下一个全排列
2. 假如自己手写全排列函数，相当于有n个位置，要把n个数填入这几个位置上，每个位置有不止一种选择，用dfs来实现，和上一题差不多，但比那个要简单一些
注意，输出时的元素要占5个位置，用上一题的setw()函数，记得写头文件#include<iomanip>
代码(next_permutation)
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int main()
{
int n,l=1;
scanf("%d",&n);
int s[n];
for(int i=1;i<=n;i++)
{
s[i]=i;
l*=i;
}//全排列一共n！种
for(int i=1;i<=l;i++)
{
for(int j=1;j<=n;j++)
{
cout<<setw(5)<<s[j];
}
cout<<endl;
next_permutation(s+1,s+n+1);
}
return 0;
}
代码（dfs)
#include<bits/stdc++.h>
using namespace std;
int s[10];
bool a[10];
int n;
int res=1,ans;
void dfs(int e)
{
if(e>n)
{
for(int i=1;i<=n;i++)
{
cout<<setw(5)<<s[i];
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++)
{
if(!a[i])
{
a[i]=true;
s[e]=i;
dfs(e+1);
a[i]=false;
}
}
}
int main()
{
scanf("%d",&n);
int m=n;
while(m!=1)
{
res*=m;
m--;
}
dfs(1);
return 0;
}总结
这里用了另一种防止填入数字重复的方法，只需要定义一个长度和int数组一样大的布尔数组，初始值为false，如果没用过了则可以把它存入int数组并，并更新为true,遍历下一个dfs，同时回溯把刚才的true变为false
题目7
分析
这个题目稍微有些复杂，就是说会给你n个数字，以及要在这个数字组合成的外星文上加的数
主要问题在于如何把这n个数字加m后变成另外n个数字，这个过程是怎样运作的
我们主要观察这个部分：
这是只有三个手指的时候，相当于123的全排列，而且是按照顺序的，所以很自然地想到了用全排列那题的方法，next_permutation（）
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
scanf("%d",&n);
scanf("%d",&m);
int a[n];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
next_permutation(a,a+n);
}
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}总结
这题主要是刚开始不太好想到，要善于观察那手指的数字，从中发现规律。