网站空间和云服务器,制作网站公司 英语网站首页,济南网站建设免费,网站开发3687474企鹅目录
组合型枚举#xff08;排列组合模板#xff08;#xff09;#xff09;:
排列型枚举#xff08;全排列#xff09;模板#xff1a;
题目一#xff08;公平抽签 排列组合#xff09;#xff1a;
编辑 代码#xff1a;
题目二#xff08;座次问题 全排…目录
组合型枚举排列组合模板:
排列型枚举全排列模板
题目一公平抽签 排列组合
编辑 代码
题目二座次问题 全排列
代码
题目三排列序数
代码
题目四 美丽的区间 尺取法
代码 题目五奇怪的动物园 尺取法
代码
组合型枚举排列组合模板:
#include iostream//排列组合
#include vector
using namespace std;
int n, m;
vectorint chosen;
void calc(int k)
{if ((chosen.size() m) || (chosen.size() n - k 1) m)//选太多了选太少了chosen.size()表示选了几个return;if (k n 1)//最后一个数都已经选完了{for (int i 0; i chosen.size(); i)cout chosen[i] ;//输出第i个为几cout endl;return;}chosen.push_back(k);//选数字kcalc(k 1);//继续往深度遍历chosen.pop_back();//不选数字kcalc(k 1);//继续往深度遍历
}
int main()
{cin n m;calc(1);//从一开始
} 排列型枚举全排列模板
#include iostream//排列型枚举全排列
#include vector
using namespace std;
int n;
int chosen[20];
int book[20] { 0 };
void calc(int k)
{if (k n 1)//最后一个数都已经选完了{for (int i 1; i n; i)cout chosen[i] ;//输出第i个为几cout endl;return;}for (int i 1; i n; i){if (book[i])//标记是否用过continue;book[i] 1;//标记为用了chosen[k] i;//第k个为数字icalc(k 1);//继续往深度遍历book[i] 0;//回溯没访问过ichosen[k] 0;}
}
int main()
{cin n;calc(1);//从一开始
} 题目一公平抽签 排列组合 代码
#includeiostream
#includevector
using namespace std;
int n, m;
vectorint chosen;
vectorstring name;
void calc(int k)
{if (chosen.size() m || chosen.size() (n - k 1) m)//选多了或者选少了chosen.size()表示选了几个return;if (k n 1)//最后一个也已经选完了{for (int i 0; i chosen.size(); i)cout name[chosen[i]-1] ;cout endl;}chosen.push_back(k);//选数字kcalc(k 1);//继续往深度遍历chosen.pop_back();//不选数字kcalc(k 1);//继续往深度遍历
}
int main()
{cin n m;for (int i 0; i n; i){string s;cin s;name.push_back(s);}calc(1);
}
题目二座次问题 全排列 代码
#includeiostream
#includevector
using namespace std;
int n;
int chosen[15];
int book[15];//标记是否访问过
string name[15];
void calc(int k)
{if (k n 1)//最后一个数都已经选完了{for (int i 1; i n; i)//输出该排列{cout name[chosen[i] - 1] ;//name下标从0开始}cout endl;return;}for (int i 1; i n; i){if (book[i])//标记是否用过continue;book[i] 1;//标记为用了chosen[k] i;//第k个为数字icalc(k 1);//继续往深度遍历book[i] 0;//回溯没访问过ichosen[k] 0;}
}
int main()
{cin n;for (int i 0; i n; i){cin name[i];}calc(1);//从第一个开始
}
题目三排列序数 代码 #include iostream//用next_permutation函数进行全排列
#include algorithm
using namespace std;
int main()
{long long cnt0;//记录个数string s;string s1;cin s;s1 s;sort(s.begin(), s.end());//从大到小排序do {if (s s1)//相等的时候跳出break;cnt;} while (next_permutation(s.begin(), s.end()));//开始遍历cout cnt;} 尺取法是一种线性的高效率算法。记L,R为一个序列内以L为起点的最短合法区间如果R随L的增大而增大的就可以使用尺取法。具体的做法是不断的枚举L同时求出R。因为R随L增大而增大所以总时间复杂度为O(n) 题目四 美丽的区间 尺取法 代码
#include iostream
using namespace std;
int n, s;
int ans 1e8, sum 0;
int a[100010];
int main()
{cin n s;for (int i 1; i n; i)cin a[i];for (int l 1, r 1; r n; ){if(sums)//不大于s则加上往右遍历{suma[r],r;}else{ansmin(r-l,ans);//取小的sum-a[l];//减掉最左边l;//往下遍历}}if (ans 1e8)//不存在cout 0;elsecout ans;
} 题目五奇怪的动物园 尺取法 代码
#includeiostream
using namespace std;
int n, m, cnt,ans,ansl0,ansr0;//ans记录票价
int a[1010];
int b[1010];//记录x类动物的数量
void In(int x)
{if (b[x] 0) cnt;//之前没有x类动物现在加入了种类cntb[x];//x类动物数量加一
}
void De(int x)
{if (b[x] 1) cnt--;//之前有一个x类动物现在删掉种类cnt--b[x]--;//x类动物数量减一
}
int main()
{cin n m;for (int i 1; i n; i){cin a[i];}ans n;//最大为一共有的动物数量for (int l 1, r 1; r n; r){In(a[r]);//a[r]这类动物加入while (1){De(a[l]);//删掉最左边类动物if (cnt m) l;//删了cnt等于m所有种类都选到了则lelse//删了这类动物不满足cnt等于m还是要把这类动物加入{In(a[l]);break;}}if (cnt m r - l 1 ans)//满足所有动物都能看票价更低了更新左区间和右区间{ans r - l 1;ansl l, ansr r;}}if (ansl ! 0)cout ansl ansr;elsecout 1 n;
}
