AKSZ-枚举算法
2024-03-17 18:33:06
发布于：广东
重要干货
1.计算运行时间
#include<bits/stdc++.h>
using namespace std;
const int maxn=15;
int a[maxn];
int main(){
int n;cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
}
do{
for(int i=0;i<n;++i)cout<<a[i]<<" ";
cout<<endl;
}while(next_permutation(a,a+n));
return 0;
}
2.枚举子集
#include<bits/stdc++.h>
using namespace std;
const int maxn=25;
int a[maxn];int n;
void solve(int x){
for(int i=0;i<n;++i){
if((1<<i)&x){
cout<<a[i]<<" ";
}
}
puts("");
}
int main(){
cin>>n;
for(int i=0;i<=n;++i){
cin>>a[i];
}
for(int i=0;i<=(1<<n)-1;++i){
solve(i);
}
return 0;
}
进制数
-
10转2
逢2取余，逆序排列
十进制小数转换成二进制小数采用”乘2取整，顺序排列“ -
10转8
逢8取余，逆序排列
十进制小数转换成八进制小数采用”乘8取整，顺序排列“
枚举算法
三要素：枚举对象、枚举范围、判定条件
特点：简单粗暴
三位偶数
题目描述
给出一个正整数 n 和一个长度为 n 的数组 a。其中每个元素是一个数字（0−9）。数组中可能存在重复元素。
你需要找出 所有 满足下述条件且 互不相同 的整数：
① 该整数由 a 中的三个元素按 任意 顺序 依次连接 组成。
② 该整数不含 前导零
③ 该整数是一个 偶数
你需要输出所有 互不相同 的整数按 递增顺序 排列。
输入格式
第一行输入一个整数 n ，(3<=n<=100)
第二行输入n个整数到数组 a 中。(0<=a[i]<=9)
输出格式
输出所有互不相同的整数按 递增顺序 排列，每个数字之间使用空格分隔。
样例组输入#1
3
2 0 1样例组输出#1
102 120 210
枚举元组
题目描述
元组是指由 个元素组成的序列。例如 是一个三元组、 是一个四元组。
给定 和 ，请按字典序输出全体 元组，其中元组内的元素是在 之间的整数。
「字典序」是指：优先按照第一个元素从小到大的顺序，若第一个元素相同，则按第二个元素从小到大……依此类推。详情参考样例数据。
输入格式
仅一行，两个正整数 。
输出格式
若干行，每行表示一个元组。元组内的元素用空格隔开。
样例 #1
样例输入 #1
2 3
样例输出 #1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
样例 #2
样例输入 #2
3 3
样例输出 #2
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3
提示
对于 的数据，有 。
代码如下:
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[18];
void dfs(int x){
//当前在第x层循环
if(x==n){
for(int i=1;i<=n;++i){
cout<<a[i]<<" ";
}
puts("");
return;
}
for(int i=1;i<=k;++i){
a[x+1]=i;
dfs(x+1);
}
}
int main(){
cin>>n>>k;
dfs(0);
return 0;
}
全排列
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int maxn=15;
int a[maxn];
int main(){
int n;cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
}
do{
for(int i=0;i<n;++i)cout<<a[i]<<" ";
cout<<endl;
}while(next_permutation(a,a+n));
return 0;
}
重难点：二进制枚举
#include<bits/stdc++.h>
using namespace std;
const int maxn=25;
int a[maxn];int n;
void solve(int x){
for(int i=0;i<n;++i){
if((1<<i)&x){
cout<<a[i]<<" ";
}
}
puts("");
}
int main(){
cin>>n;
for(int i=0;i<=n;++i){
cin>>a[i];
}
for(int i=0;i<=(1<<n)-1;++i){
solve(i);
}
return 0;
}
埃氏
时间复杂度：
经典例题
01.最长山脉
题目描述
给出一个正整数 n 和一个长度为 n 的数组 a。
如果满足下面条件，我们称之为山脉：
存在下标 ，满足 并且 。
换句话说：这个位置是最大值，两侧依次递减。比如 就是一个长度为 5 的山脉。
请你找出最长的山脉，如果不存在输出 0。
输入格式
第一行输入一个整数 ，
第二行输入n个整数，。
输出格式
输出最长的山脉，如果不存在输出 0。
样例组输入#1
7
2 1 4 7 3 2 5
样例组输出#1
5
接下来是正解：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],l[N],ar[N],maxn=0;
void findHill(int i){
int cnt=0,flag=0;
for(int j=i;j>0;--j){
if(a[j-1]<a[j]){
++cnt;
flag=1;
}
else{
break;
}
}
if(!flag) return;
flag=0;
for(int j=i;j<n-1;++j){
if(a[j]>a[j+1]){
++cnt;
flag=2;
}
else{
break;
}
}
if(!flag) return;
maxn=max(maxn,cnt);
}
int main(){
//freopen("data.in","r",stdin);
cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
}
// for(int i=1;i<n-1;++i) findHill(i);
// if(maxn) cout<<maxn+1;
// else cout<<"0";
// i l最长到哪里 ，r 开头最长到哪里
l[0] = 0;
for(int i = 1;i<n;i++){
if(a[i]>a[i-1])l[i] = l[i-1]+1;
else l[i] = 0;
}
ar[n-1] = 0;
for(int i = n-2;i>=0;i--){
if(a[i]>a[i+1])ar[i] = ar[i+1]+1;
else ar[i] = 0;
}
int ma=0;
for(int i = 0 ;i < n;i++){
if(l[i]>0 && ar[i]>0){
ma=max(ma,l[i]+ar[i]+1);
}
}
cout<<ma;
return 0;
}
02.# [COCI2008-2009 #2] PERKET
题目描述
Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 和苦度 。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。
输入格式
第一行一个整数 ，表示可供选用的食材种类数。
接下来 行，每行 个整数 和 ，表示第 种食材的酸度和苦度。
输出格式
一行一个整数，表示可能的总酸度和总苦度的最小绝对差。
样例 #1
样例输入 #1
1
3 10
样例输出 #1
7
样例 #2
样例输入 #2
2
3 8
5 8
样例输出 #2
1
样例 #3
样例输入 #3
4
1 7
2 6
3 8
4 9
样例输出 #3
1
提示
数据规模与约定
对于 的数据，有 ，且将所有可用食材全部使用产生的总酸度和总苦度小于 ，酸度和苦度不同时为 和 。
说明
- 本题满分 分。
- 题目译自 COCI2008-2009 CONTEST #2 PERKET，译者 @mnesia。
03.水仙花数
【模拟枚举】水仙花数
题目描述
水仙花数是指一个 3 位数，它的每个位上的数字的 3次幂之和等于它本身。例如：
，小码君对水仙花数很感兴趣，他想知道100至999范围内的所有水仙花数，从小到大输出所有的水仙花数
提示
数据范围：
找出100至999范围内的所有水仙花数
样例说明：
100至999范围内的水仙花数依次输出，每一个数占一行，第一个数为153
输入格式
无输入
输出格式
从小到大输出所有的水仙花数，每一个水仙花数占一行
04.找钱
题目描述
将 n 元人民币换成 1 元、2 元、5 元的零钱，编程计算共有多少种方法？
输入格式
输入一行，包含一个整数 n。(0<n<1000)
输出格式
输出一行，包含一个整数。
样例组输入
5
样例组输出
4
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,cnt=0;
int main(){
cin>>n;
for(int i=0;i<=n;i+=5){
for(int j=0;j<=n;j+=2){
int z=n-i-j;
if(z>=0) ++cnt;
}
}
cout<<cnt;
return 0;
}
05.统计质数个数
#include<bits/stdc++.h>
using namespace std;
long long n,cnt=0;
int main(){
cin>>n;
for(long long i=2;i<n;++i){
for(long long j=2;j*j<=i;++j){
if(i%j==0) ++cnt;
}
}
cout<<cnt;
return 0;
}
06.统计三元组数量
题目描述
给出一个长度为 n 的数组，以及 a，b ，c 三个整数。请你统计满足下面条件的三元组数量。
三元组 (arr[i]，arr[j]，arr[k]) 需要满足下列全部条件:
0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
注意：其中 |x| 表示 x 的绝对值。
输入格式
第一行输入四个整数，n，a，b，c 。n ≤ 100，0 ≤ a，b，c ≤ 1000。
第二行输入 n 个整数，0 ≤ arr[i] ≤ 1000。
输出格式
输出一个整数，满足条件的三元组数量。
样例组输入
5 7 2 3
3 0 1 1 9 7
样例组输出
4
全部评论 1
计算运行时间的代码是
clock_t start , end;
start = clock(); // 记录开始时间
solve();//需要计算时间的代码
end = clock();// 记录结束时间
printf("%.2lf MS",double(end-start) / CLOCKS_PER_SEC * 1000 ); // 转换成小数模式2024-03-20 来自 广东
0
有帮助，赞一个