完全搜索DFS
递归实现指数型枚举（dfs深搜）
思路
直接按照模板枚举子集，然后输出。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
void dfs(int cnt){
if(cnt==n+1){
for(int i=0;i<a.size();i++){
cout <<a[i]<<" ";
}
cout <<endl;
}else{
dfs(cnt+1);
a.push_back(cnt);
dfs(cnt+1);
a.pop_back();
}
}
int main(){
cin >>n;
dfs(1);
return 0;
}
递归实现组合型枚举（dfs深搜）
思路
跟上一题很像，只要在输出时和枚举时稍稍改一下即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int tt=110;
int n,m;
int a[tt];
void dfs(int x,int y){
if(x==m+1){
for(int i=1;i<=m;i++){
cout <<a[i]<<" ";
}
cout <<endl;
}else{
for(int i=y;i<=n;i++){
a[x]=i;
dfs(x+1,i+1);
a[x]=0;
}
}
}
int main(){
cin >>n>>m;
dfs(1,1);
return 0;
}
递归实现排列型枚举（dfs深搜）
思路
按照全排列的模板就可以了，直接套模板。
代码
#include <bits/stdc++.h>
using namespace std;
const int tt=110;
int n;
vector<int> a;
int flag[tt];
void dfs(){
if(a.size()==n){
for(int i=0;i<a.size();i++){
cout <<a[i]<<" ";
}
cout <<endl;
}else{
for(int i=1;i<=n;i++){
if(flag[i]) continue;
a.push_back(i);
flag[i]=1;
dfs();
flag[i]=0;
a.pop_back();
}
}
}
int main(){
cin >>n;
dfs();
return 0;
}
Apple Division（dfs深搜）
思路
维护一个递归函数 dfs(idx,x,y,cnt)，如果我们当前在索引idx上，它返回两组之间的最小权重差。
检查我们是否遍历了整个数组，即idx==cnt，然后返回两组之间的差值。
否则，请探索在第一组中选择索引idx处的元素和在第二组中选择索引idx处的元素时的情况。
在搜索了所有的可能性之后，返回两组之间可能的最小权重差值。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int tt=110;
int a[tt];
int dfs(int idx,int x,int y,int cnt){
if(idx==cnt){
return abs(x-y);
}else{
int res_1=dfs(idx+1,x+a[idx],y,cnt);
int res_2=dfs(idx+1,x,y+a[idx],cnt);
return min(res_1,res_2);
}
}
signed main(){
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
int n;
cin >>n;
for(int i=0;i<n;i++){
cin >>a[i];
}
int ans=dfs(0,0,0,n);
cout <<ans;
return 0;
}
Creating Strings（dfs深搜）
思路
首先，用C++内置函数next_permutation判断是否还有下一个全排列。如果有，就cnt++。
否则，先输出cnt，然后再次使用next_permutation，如果有下一个全排列，就输出这一个全排列。
否则，结束。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int tt=110;
int a[tt];
bool cmp(int a,int b){
return char(a)<char(b);
}
signed main(){
freopen("create.in","r",stdin);
freopen("create.out","w",stdout);
string s;
cin >>s;
for(int i=0;i<s.size();i++){
a[i+1]=s[i];
}
int cnt=0;
sort(a+1,a+1+s.size(),cmp);
do{
cnt++;
}while(next_permutation(a+1,a+1+s.size()));
cout <<cnt<<endl;
sort(a+1,a+1+s.size(),cmp);
do{
for(int i=1;i<=s.size();i++){
cout <<char(a[i]);
}
cout <<endl;
}while(next_permutation(a+1,a+1+s.size()));
return 0;
}
内置数据结构应用
Distinct Numbers（set）
思路
因为中的元素不能重复，所以每次输入，都把元素丢进里，最后输出的长度就可以了。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
set<int> s;
signed main(){
freopen("dis.in","r",stdin);
freopen("dis.out","w",stdout);
int n;
cin >>n;
for(int i=1;i<=n;i++){
int op;
cin >>op;
s.insert(op);
}
cout <<s.size();
return 0;
}
Apartments（vector）
思路
这个问题可以通过对两个数组进行排序然后比较它们的第一个元素来解决。如果它们的差值小于或等于 ，则增加计数并移动到两个数组的下一个元素k。
否则，如果差异大于并且公寓大小大于所需大小，那么我们将继续执行申请人数组中的下一个元素，因为该申请人将永远无法拥有他想要的公寓k。
如果公寓大小小于所需大小，那么我们将继续处理数组中的下一个元素，因为有可能有一个与申请人所需大小的公寓匹配。
只需重复该过程，直到我们到达其中一个数组的末尾。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
freopen("apartments.in","r",stdin);
freopen("apartments.out","w",stdout);
int n,m,k;
cin >>n>>m>>k;
vector<int> a(n);
vector<int> b(m);
for(int i=0;i<n;i++){
cin >>a[i];
}
for(int i=0;i<m;i++){
cin >>b[i];
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
int cnt=0;
for(int i=0,j=0;i<n&&j<m;){
if(abs(a[i]-b[j])<=k){
cnt++;
i++,j++;
}else if(a[i]<b[j]){
i++;
}else{
j++;
}
}
cout <<cnt;
return 0;
}
Concert Tickets（set&multiset）
思路
对于每个客户，我们希望找到他们可能的最高票价从可用票证中接受。
如果客户的最高价格过低， 这样就不会有低于它的，我们可以输出。
如果没有，我们会找到最高机票价格小于或等于最高价格，然后删除问题指定的价格。为此，我们使用multiset。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
set<pair<int,int>> s;
signed main(){
freopen("tickets.in","r",stdin);
freopen("tickets.out","w",stdout);
int n,m;
cin >>n>>m;
for(int i=0;i<n;i++){
int op;
cin >>op;
s.insert({op,i});
}
for(int i=0;i<m;i++){
int op;
cin >>op;
auto it=s.lower_bound({op+1,0});
if(it!=s.begin()){
it--;
cout <<(*it).first<<endl;
s.erase(it);
}else{
cout <<"-1"<<endl;
}
}
return 0;
}
Traffic Lights（set&multiset）
思路
这题我们要开一个和来维护。 一个是维护现在有的红绿灯，另一个用来维护红绿灯之间的距离。 每次加入一个新的红绿灯时，先找到那个位置左右的红绿灯是谁，把他们的距离从中移除，换上新的距离 （有一个新的在中间）。
操作完再把新的灯也加入就好。 每次输出答案就是输出中的最后一个数字 （最大）。
代码
#include <bits/stdc++.h>
using namespace std;
set<int> s;
multiset<int> jl;//距离
int main(){
freopen("lights.in","r",stdin);
freopen("lights.out","w",stdout);
int x,n;
cin >>x>>n;
s.insert(0);
s.insert(x);
jl.insert(x);
for(int i=1;i<=n;i++){
int op;
cin >>op;
auto it_1=s.upper_bound(op);
auto it_2=it_1;
it_2--;
s.insert(op);
jl.erase(jl.find(*it_1-*it_2));
jl.insert(op-*it_2);
jl.insert(*it_1-op);
cout <<*--jl.end()<<" ";
}
return 0;
}
Room Allocation（小根堆）
思路
首先，要算出所需的最小房间数，就是遇上要退房的人，；否则，。然后每次求一次最大值。最大值就是所需的最小房间数。
然后，循环判断是否是某个客人到达的时间。如果是，那就判断还有没有房间给他，如果有，就把房号最小的给他；没有，就重新开一间放给他。如果是某个客人离开的时间，就把这个房间存入小根堆。
再在数组里记录当前的房号。
最后输出数组。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int tt=4e5+10;
priority_queue<int,vector<int>,greater<int>> q;
int ans[tt];
struct node{
int day;
int flag;
int idx;
}a[tt];
bool cmp(node a,node b){
if(a.day!=b.day){
return a.day<b.day;
}else{
return a.flag<b.flag;
}
}
signed main(){
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
int n;
cin >>n;
int res=1;
for(int i=1;i<=2*n;i++){
cin >>a[i].day;
if(i%2!=0){
a[i].flag=1;
a[i].idx=res;
}else{
a[i].flag=2;
a[i].idx=res;
res++;
}
}
sort(a+1,a+1+2*n,cmp);
int cnt=0;
int max_n=0;
for(int i=1;i<=2*n;i++){
if(i==1){
cnt++;
continue;
}
if(a[i].flag==2){
cnt--;
}else{
cnt++;
}
max_n=max(max_n,cnt);
}
cout <<max_n<<endl;
int sum=1;
for(int i=1;i<=2*n;i++){
int r;
if(a[i].flag==1){
if(q.empty()){
r=sum++;
}else{
r=q.top();
q.pop();
}
ans[a[i].idx]=r;
}else{
q.push(ans[a[i].idx]);
}
}
for(int i=1;i<=n;i++){
cout <<ans[i]<<" ";
}
return 0;
}
谢谢
