CSP集训笔记-Day 2

༺ཌༀ我要上南开ༀད༻

2026-08-11 13:50:29

发布于：天津

11阅读

0回复

0点赞

递归

#include<bits/stdc++.h>
using namespace std;
//递归(复杂度O(2^n)
//记忆化搜索剪枝：加记忆数组，计算过的不再重复分化
//----------------------
//递归全排列，复杂度O(n!)
int n,a[100],vis[100];
void dfs(int x){//枚举当前可以选择的数
    if(x>n){
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]!=1){
            a[x]=i;
            vis[i]=1;//标记已选过这个数
            dfs(x+1);//下一个位置
            vis[i]=0;//返回时撤回标记
        }
    }
}
//n个数中选k个
//----------------------
int k,ans;
void choose(int x){
    if(x>k){
        ans++;
        for(int i=1;i<=k;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]!=1){
            a[x]=i;
            vis[i]=1;//标记已选过这个数
            choose(x+1);//下一个位置
            vis[i]=0;//返回时撤回标记
        }
    }   
}
//只要升序排列的
void choose_up(int x,int p){
    if(x>k){
        ans++;
        for(int i=1;i<=k;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=p+1;i<=n;i++){
        if(vis[i]!=1){
            a[x]=i;
            vis[i]=1;//标记已选过这个数
            choose(x+1,i);//下一个位置
            vis[i]=0;//返回时撤回标记
        }
    }   
}
int main(){
    cin>>n;
    //dfs(1);
    cin>>n>>k;
    //choose(1);
    //choose_up(1,0);
	return 0;
}