1.循环枚举
使用多重循环来枚举题目中涉及的所有情况
例1:
统计方形加强版(洛谷p2241)
题目描述
有一个 n×m 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。
输入格式
一行，两个正整数 n,m（n≤5000,m≤5000）
输出格式
一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。
输入输出样例
输入
2 3
输出
8 10
题目分析:
任设一点坐标(x，y)，将该点作为正方形的右上角顶点，连接右上角点与正方形的左下角点并将线延伸至棋盘的边界，可知以该点为右上角顶点的正方形的个数就是x与y中小的那一个，而以该点为右上角点的方形个数为x*y，所以以该点为右上角点的长方形个数为
x*y-min(x，y)，对于每一个点都是如此(注:当x=0或y=0时，够不成方形)
据上述分析写出代码:
#include
using namespace std;
int main()
{
long long x,y,n,m,t,squ=0,rec=0;
cin>>n>>m;
for(x=0;x<=n;x++)
for(y=0;y<=m;y++)
{
t=min(x,y);
squ+=t;
rec+=x*y-t;
}
cout<
}
例2.
烤鸡(洛谷p2089)
题目描述
猪猪Hanke特别喜欢吃烤鸡，Hanke吃鸡很特别，为什么特别呢？因为他有10种配料（芥末、孜然等），每种配料可以放1—3克，任意烤鸡的美味程度为所有配料质量之和
现在，Hanke想要知道，如果给你一个美味程度，请输出这10种配料的所有搭配方案
输入输出格式
输入格式：
一行,n<=20
输出格式：
第一行，方案总数
第二行至结束，10个数，表示每种配料所放的质量
按字典序排列。
输入输出样例
输入样例#1：
11
输出样例#1：
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
题目分析:
对此题进行枚举剪枝，即限定每个变量的范围，设十种配料分别为a,b,c,d,e,f,g,h,i,j，拿e举例，首先，1<=e<=3这是肯定的，然后如果我们假设e之后的配料都取3g，则e最小值为
n-15-a-b-c-d，同时要满足这个最小值一定不能小于1，如果假设e之后的配料都取1，则最大值为n-5-a-b-c-d，同时满足该最大值不超过3
按照这个思路，可写出下面代码: #include
using namespace std;
#define rep(i,a,b) for(int i=max(1,a);i<=min(3,b);i++)
//用宏定义来代替for循环，减少代码书写量
int main()
{
int ch[60000][10],n,s=0;
cin>>n;
rep(a,n-27,n-9)
rep(b,n-24-a,n-8-a)
rep(c,n-21-a-b,n-7-a-b)
rep(d,n-18-a-b-c,n-6-a-b-c)
rep(e,n-15-a-b-c-d,n-5-a-b-c-d)
rep(f,n-12-a-b-c-d-e,n-4-a-b-c-d-e)
rep(g,n-9-a-b-c-d-e-f,n-3-a-b-c-d-e-f)
rep(h,n-6-a-b-c-d-e-f-g,n-2-a-b-c-d-e-f-g)
rep(i,n-3-a-b-c-d-e-f-g-h,n-1-a-b-c-d-e-f-g-h)
rep(j,n-a-b-c-d-e-f-g-h-i,n-a-b-c-d-e-f-g-h-i)
{
ch[s][0]=a;
ch[s][1]=b;
ch[s][2]=c;
ch[s][3]=d;
ch[s][4]=e;
ch[s][5]=f;
ch[s][6]=g;
ch[s][7]=h;
ch[s][8]=i;
ch[s][9]=j;
s++;
}
cout< for(int i=0;i { for(int j=0;j<10;j++) cout< cout< } return 0; } 2.子集枚举 从一个集合中找出所有的子集，集合中每个元素都可以被选或不选，含有n个元素的集合总共有2^n个子集(包括全集和空集) 例: 选数(洛谷p1036) 题目分析: 此题用到了进制之间的转换的思想，把k个整数相加得到的数用二进制来表示，这样就可以更直观的看出集合中的各个元素在子集中的出现情况(将n个数看成一个集合，取出的k个数代表集合的子集)，由于此题涉及二进制，所以需要用到位运算 了解位运算请看: https://blog.csdn.net/wx2306/article/details/79346694?utm_source=app&app_version=5.2.1&code=app_1562916241&ulinkId=usr1mkqgl919blen 据上述提示编写代码: #include //__builtin_popcount()函数可以直接返回二进制下1的个数 3.排列枚举 枚举所有元素的排列，常用到next_permutation函数 例: 火星人(洛谷p1088) 题目: https://www.luogu.com.cn/problem/P1088 题目分析: 该题可以看成输入第一个排列，往后找到第m个排列，此题用next_permutation可以轻松的实现题目要求 #include using namespace std; int main() { int a[10010],n,m,i; cin>>n>>m; for(i=0;i cin>>a[i]; while(m--) next_permutation(a,a+n); for(i=0;i { if(i==0) cout<
else cout<<" "<
} return 0; }
using namespace std;
bool f(int n)
{
int i;
for(i=2;i*i<=n;i++)
if(n%i==0)
return 0;
return 1;
}
int main()
{
int n,k,a[20],b=0,i,U,S;
cin>>n>>k;
for(i=0;i
U=1<
if(__builtin_popcount(S)==k)
{
int s=0;
for(i=0;i
if(f(s))
b++;
}
}
cout<
}
