、

目录

一、概念

1.1相关概念

1.2应用场景

1.3局限性

二、相关问题

2.1例题1:统计

2.2例题二 二倍的问题

2.3例题3 奶牛碑文

2.4例四网友年龄

2.5例五生日年龄数

2.6数学题例六

三、二进制枚举

3.1相关概念

3.2问题

3.2例题1：何以包邮？  

3.2例题2：诗仙李白的郁闷事

3.2林大OJ：1205和为K--二进制枚举

3.2林大OJ：1505陈老师加油-二进制枚举

3.2林大OJ：1665四糸乃买花-二进制枚举

3.3位运算

一、概念

1.1相关概念

暴力枚举是一种简单朴素的算法思想，也称为穷举算法。其基本思想是对问题的所有可能情况进行逐一尝试，并从中找到符合条件的解决方案。

暴力枚举算法通常通过循环或递归实现，其时间复杂度与问题规模成指数级关系，因此对于较大规模的问题不适用，但对于一些小规模问题，暴力枚举算法往往是可行的。

在实现上，暴力枚举算法通常采用循环或递归的方式来实现。循环实现通常是嵌套多层循环，逐个枚举每个可能的情况，并在内层循环中对每种情况进行检查；递归实现则是将问题分解为更小的子问题，逐层递归求解，直到找到符合条件的解。

1.2应用场景

1. 排列组合问题：如求解从 n 个元素中选取 k 个元素的所有可能组合，可以使用暴力枚举算法逐个枚举所有组合。

2. 搜索问题：如迷宫问题、八皇后问题等，可以使用暴力枚举算法枚举所有可能的状态，然后检查每个状态是否满足问题要求。

3. 子序列问题：如求解一个序列的最长递增子序列、最长公共子序列等，可以使用暴力枚举算法枚举所有子序列，并检查每个子序列是否满足要求。

4. 数值计算问题：如求解多项式函数的值、求解复合函数的值等，可以使用暴力枚举算法枚举函数的参数，并计算函数的值。

5. 基础算法问题：如素数判断、最大公约数、最小公倍数等，可以使用暴力枚举算法逐个枚举可能的解，然后检查是否满足问题要求。

1.3局限性

简单的枚举一般只适用于解决简单的问题

难以求出或范围特别大，明显超时（数论等）

二、相关问题

2.1例题1:统计

高数考试结果已经出来了，如果不及格就惨了，如果不及格，那开学还得补考，那这个春节就郁闷了！现在老师想知道有几名同学高数考试没及格，假设1个班级有N名同学！ Input：输入数据有多组，每组1行,第1个数是N，（1<=N<=1000）接下来有N个数，这N个数都是0到100之间的整数。 Output：请输出每组的N个数中有多少个是小于60的？记得输出结果后要换行啊！

Sample Input 10 1 2 3 4 5 6 7 8 9 99

                       8 80 70 60 90 100 75 65 55

Sample Output 9

                         1

#include int main() {int n;while (~scanf("%d", &n)) {int cnt = 0;for (int i = 0; i < n; i++) {int x;scanf("%d", &x);if (x < 60) cnt++;}printf("%d\n", cnt);}return 0;
}

优化

#include inline int read() { // 快读int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }return x * f;
}inline void write(int x) { // 快写if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');
}int main() {int i, n;while (~scanf("%d", &n)) {int cnt = 0;for (i = 0; i < n; i++) {int x = read();if (x < 60) cnt++;}write(cnt); putchar('\n');}return 0;
}

1.快读

快读是一种优化输入效率的技巧，它通过尽可能地减少读取输入流的次数来提高输入效率。在 C/C++ 中，通常使用 scanf 或者 getchar 来读入数据，但是这些函数的效率相对较低。因此，我们可以使用快读来替代这些函数，以提高输入效率。

快读的基本原理是：一次读入多个字符，然后通过位运算和加法等操作将这些字符转换为一个整数。快读通常会用到 getchar 函数来读入字符，因为 getchar 的效率比 scanf 更高。在读入数字的过程中，我们需要将读入的字符转换成数字。这个过程可以通过将读入的字符与 '0' 的 ASCII 码进行运算来实现。

2.快写

快写是一种优化输出效率的技巧，它通过尽可能地减少输出流的次数来提高输出效率。在 C/C++ 中，通常使用 printf 或者 putchar 来输出数据，但是这些函数的效率相对较低。因此，我们可以使用快写来替代这些函数，以提高输出效率。

快写的基本原理是：将一个整数拆分成若干个位数，然后将每个位数转换成字符并输出。在输出字符的过程中，我们需要使用 putchar 函数来输出字符。由于 putchar 的效率比 printf 更高，因此可以提高输出效率。

2.2例题二 二倍的问题

描述：给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。

输入：输入包括n组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。 输出：对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。

#include 
#include 
using namespace std;int main() {int n;while (cin >> n&&n) {vector nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}int cnt = 0;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (nums[i] == 2 * nums[j] || nums[j] == 2 * nums[i]) {cnt++;}}}cout << cnt << endl;}return 0;
}

优化

#include 
#include 
using namespace std;inline int read() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * f;
}inline void write(int x) {if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');
}int main() {int n;while ((n = read()) != 0) {vector nums(n);for (int i = 0; i < n; i++) {nums[i] = read();}int cnt = 0;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (nums[i] == 2 * nums[j] || nums[j] == 2 * nums[i]) {cnt++;}}}write(cnt);putchar('\n');}return 0;
}

2.3例题3 奶牛碑文

小伟暑假期间到大草原旅游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C、O 和 W。尽管小伟看不懂，但是令他高兴的是，C、O、W的顺序形式构成了一句他最喜欢的奶牛单词“COW”。现在，他想知道有多少次 COW 出现在文本中。 如果 COW 内穿插了其他字符，只要 COW 字符出现在正确的顺序，小伟也不介意。甚至，他也不介意出现不同的 COW 共享一些字母。例如，CWOW 出现了 1 次 COW，CCOW 算出现了2 次 COW，CCOOWW 算出现了 8 次 COW。 输入：第 1 行为 1 个整数 N，第 2 行为 N 个字符的字符串，每个字符是一个 C、O 或 W。 输出：输出COW 作为输入字符串的子串出现的次数（不一定是连续的）。 提示：答案会很大，建议用 64 位整数（long long）。         Sample Input                        Sample Output          

                                                  6                                       6            COOWWW    

#include 
#include 
using namespace std;int main() {int n;cin >> n;string s;cin >> s;long long cnt = 0;int c = 0, co = 0, cow = 0;for (int i = 0; i < n; i++) {if (s[i] == 'C') {c++;} else if (s[i] == 'O') {co += c;} else if (s[i] == 'W') {cow += co;}}cout << cow << endl;return 0;
}

我们可以通过遍历字符串，统计出在当前位置之前出现的'C'的个数，以及'C'和'O'组成'C'-'O'的个数，以及'C'-'O'-'W'的个数，也就是'COW'的个数。遍历时，如果当前字符是'C'，就将'C'的计数器加1；如果当前字符是'O'，就将'C'-'O'的计数器加上当前'C'的计数器，因为'O'只有在'C'的后面才能构成'C'-'O'；如果当前字符是'W'，就将'C'-'O'-'W'的计数器加上当前'C'-'O'的计数器，因为'W'只有在'C'-'O'的后面才能构成'COW'。

最后输出'COW'的计数器即可。

对于输入6CCOOWW，程序会执行以下操作：

1. 读入整数6，表示接下来输入的字符串长度为6。
2. 读入字符串CCOOWW。
3. 定义三个计数器c、co、cow，初始值均为0。
4. 进入for循环，i从0到5依次遍历字符串中的每一个字符。
5. 当i=0时，s[i]='C'，将c计数器加1，c=1。
6. 当i=1时，s[i]='C'，将c计数器加1，c=2。
7. 当i=2时，s[i]='O'，将co计数器加上c计数器，co=2。
8. 当i=3时，s[i]='O'，将co计数器加上c计数器，co=4。
9. 当i=4时，s[i]='W'，将cow计数器加上co计数器，cow=4。
10. 当i=5时，s[i]='W'，将cow计数器加上co计数器，cow=8。
11. 完成循环，输出cow计数器的值8，表示字符串CCOOWW中共出现了8次COW。

2.4例四网友年龄

问题描述：
某君新认识一网友。当问及年龄时，他的网友说：“我的年龄是个2位数，我比儿子大27岁,

如果把我的年龄的两位数字交换位置，刚好就是我儿子的年龄”

请你计算：网友的年龄一共有多少种可能情况？

提示：30岁就是其中一种可能哦.

请填写表示可能情况的种数。

#include 
using namespace std;int main() {for (int i = 10; i <= 99; i++) {int son = i - 27;int reverse_i = (i % 10) * 10 + (i / 10);if (son >= 0 && son <= 99 && son == reverse_i) {cout << "网友的年龄是：" << i << endl;}}return 0;
}

2.5例五生日年龄数

问题描述：
某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来，他一共吹熄了210根蜡烛。

请问，他从多少岁开始过生日party的？

请输出他开始过生日party的年龄数。

注意：你输出的应该是一个整数，不要输出任何多余的内容或说明性文字。

输入

没有输入。

输出

输出一个整数，即某君开始过生日party的年龄数

#include 
using namespace std;int main() {int sum = 0; // 记录吹熄蜡烛的总数int age = 0; // 记录从多少岁开始过生日partywhile (sum < 210) { // 只要蜡烛总数还不足236根，就继续加上下一个年龄需要吹熄的蜡烛数age++;sum += age;}cout << age << endl; // 输出某君开始过生日party的年龄数return 0;
}

2.6数学题例六

问题描述： 有限五位数 个位数为6且能被3整除的五位数有多少个？

#include using namespace std;int main()
{int count = 0;  // 记录符合条件的五位数个数for (int A = 1; A <= 9; A++){for (int B = 0; B <= 9; B++){for (int C = 0; C <= 9; C++){for (int D = 0; D <= 9; D++){int sum = A + B + C + D + 6;  // 计算ABCDE6的各位数字之和if (sum % 3 == 0)  // 如果能被3整除{count++;  // 计数器加1long num = 10000*A+1000*B+100*C+10*D+6;cout <

#include 
using namespace std;int main() {int n, i, j, x, a[30], sum = 0, minsum = 0;cin >> n >> x;for (i = 0; i < n; i++) {cin >> a[i];minsum += a[i]; // 用各位和表示最大值.}for (i = 1; i < 1< x && sum < minsum) {minsum = sum;}}cout << minsum << endl;return 0;
}

#include using namespace std;int main() {int cnt = 0; // 统计方案数for (int i = 0; i < (1 << 14); i++) { // 枚举所有14位二进制数int shop_cnt = 0, wine_cnt = 2; // 分别表示店铺数量和酒量string s = ""; // 用来存储每种情况的遍历结果for (int j = 0; j < 14; j++) {if (i & (1 << j)) { // 该位为1，遇到店铺shop_cnt++;wine_cnt *= 2;s += '1';} else { // 该位为0，遇到花wine_cnt--;s += '0';}if (wine_cnt == 1 && shop_cnt == 5 && j == 13) {// 满足条件，方案数加1，并输出该种情况cnt++;cout << s << endl;}}}cout << "Total: " << cnt << endl;return 0;
}

#include 
using namespace std;const int MAXN = 21;
int a[MAXN];int main() {int n, k;while(cin >> n >> k){for (int i = 0; i < n; i++) {cin >> a[i];}bool found = false;for (int i = 0; i < (1 << n); i++) {  // 枚举所有子集int sum = 0;for (int j = 0; j < n; j++) {if (i & (1 << j)) {  // 如果第 j 个元素被选中sum += a[j];}}if (sum == k) {found = true;break;}}if (found) {cout << "Yes" << endl;} else {cout << "No" << endl;}}return 0;
}

#include 
using namespace std;int main() {int T;while(cin >> T){int cnt = 0;for(int i = 0; i < (1 << 15); i++){int cross = 0;int gas = T;int shop = 0;bool flag = true;for(int j = 0;j < 15;j++){if(i & (1 << j)){shop++;gas *= 2;}else{cross++;gas--;}if(gas == 0)break;}if (gas==0&& shop == 5 && cross == 10)cnt++;}cout<

#include 
#include using namespace std;int main() {int n, w;cin >> n;vector flowers(n);for (int i = 0; i < n; i++) {cin >> flowers[i];}cin >> w;int ans = 0;// 枚举选花操作的状态for (int s = 1; s < (1 << n); s++) {int sum = 0; // 已选花的总价值int count = 0; // 已选花的数量for (int i = 0; i < n; i++) {if (s & (1 << i)) {sum += flowers[i];count++;}}if (count == n) {break; // 不能将所有花都买走}if (sum > w) {continue; // 不能超过总钱数}if (count % 4 == 0 && (w - sum) % 4 == 0) {ans++; // 符合要求的方案数+1}}cout << ans << endl;return 0;
}