枚举
枚举的思想是不断地猜测,从可能的集合中一一尝试,然后再判断题目的条件是否成立。但是并非所有的情况都要枚举,有时要适当的进行一些剪枝。(如枚举 \(a + b = c\) 且 \(b > a\) 的个数那么 \(b\) 要从 \(a + 1\) 开始枚举)。
通常来说,我们可以限定枚举的范围让它的复杂度更高。虽然这是一种非常基础的算法,但是后面的很多算法都是基于枚举来实现的。
例题 1:
给出 \(n\) 个数 \(a_1, a_2, \cdots, a_n\) 和 \(x\),求有多少对 \(i, j\) 满足 \(a_i + a_j = x\) 且 \(j > i\)。(\(1 \le n \le 10^3\),\(1 \le a_i \le 10^9\))。
我们可以先枚举 \(i\),从 \(1\) 枚举到 \(n\)。每次枚举到一个 \(i\) 时枚举 \(j\),从 \(i + 1\) 枚举到 \(n\)(因为 \(j > i\))。每枚举到一个 \(i, j\) 时判断条件 \(a_i + a_j = x\),如果满足把答案 \(+1\)。时间复杂度 \(O(n^2)\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 1010, kInf = (((1 << 30) - 1) << 1) + 1;
int n, x, a[kMaxN], ans = 0; // ans 是满足条件的个数
const ll kLInf = 9.22e18;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> x; // 输入 n, x
for (int i = 1; i <= n; ++ i) {
cin >> a[i]; // 输入 ai
}
for (int i = 1; i <= n; ++ i) { // 枚举 i,范围 1 至 n
for (int j = i + 1; j <= n; ++ j) { // 枚举 j,范围 i + 1 至 n
(a[i] + a[j] == x) && (++ ans); // 如果 ai + aj = x,那么答案 +1(if 压缩)
}
}
cout << ans << '\n'; // 输出答案
return 0;
}
例题 2:
猪猪 Hanke 特别喜欢吃烤鸡(本是同畜牲,相煎何太急!)Hanke 吃鸡很特别,为什么特别呢?因为他有 \(10\) 种配料(芥末、孜然等),每种配料可以放 \(1\) 到 \(3\) 克,任意烤鸡的美味程度为所有配料质量之和。现在, Hanke 想要知道,如果给你一个美味程度 \(n\) ,请输出这 \(10\) 种配料的所有搭配方案。(\(1 \le n \le 5000\))
我们可以枚举每一种调料放多少克,最后如果加起来正好等于 \(n\) 就把答案 \(+1\)。输出答案后再枚举一遍,输出每种调料放多少克。
代码:
for (int i = 1; i <= 3; ++ i) {
for (int j = 1; j <= 3; ++ j) {
for (int k = 1; k <= 3; ++ k) {
for (int l = 1; l <= 3; ++ l) {
for (int p = 1; p <= 3; ++ p) {
for (int o = 1; o <= 3; ++ o) {
for (int u = 1; u <= 3; ++ u) {
for (int m = 1; m <= 3; ++ m) {
for (int y = 1; y <= 3; ++ y) {
for (int t = 1; t <= 3; ++ t) {
if (i + j + k + l + p + o + u + m + y + t == n) {
++ ans;
}
}
}
}
}
}
}
}
}
}
}
for (int i = 1; i <= 3; ++ i) {
for (int j = 1; j <= 3; ++ j) {
for (int k = 1; k <= 3; ++ k) {
for (int l = 1; l <= 3; ++ l) {
for (int p = 1; p <= 3; ++ p) {
for (int o = 1; o <= 3; ++ o) {
for (int u = 1; u <= 3; ++ u) {
for (int m = 1; m <= 3; ++ m) {
for (int y = 1; y <= 3; ++ y) {
for (int t = 1; t <= 3; ++ t) {
if (i + j + k + l + p + o + u + m + y + t == n) {
cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << p << ' ' << o << ' ' << u << ' ' << m << ' ' << y << ' ' << t << '\n';
}
}
}
}
}
}
}
}
}
}
}
标签:10,le,int,算法,枚举,include,配料
From: https://www.cnblogs.com/bc2qwq/p/17999669/enumeration