B3622<枚举子集>题解

· · 个人记录

B3622 题解

题目传送门

分析：

1.纯dfs题

今有 n 位同学，可以从中选出任意名同学参加合唱。

请输出所有可能的选择方案。

说明是全排列问题，直接 dfs即可；

2.因为要记录每个人合不合唱的情况，所以定义bool数组，若为0，则不参加，为“N”；否则为1，则表示参加，为“Y”；

3.答案有 2^n 个，当当前枚举的数大于 n 时，开始输出，输出完 n 个数时，换行。

实现：

主函数部分：

int main()
{
    cin>>n; // 输入将要选择的人数
    dfs(1); // 从第一位同学开始选起 
    return 0; // 结束代码 
}

很简单的三行，关键的是 dfs 函数部分


void dfs(int cur) // 枚举当前需要选择的同学 
{
    if(cur == n + 1) // 如果已经超出了边界，则开始输出 
    {
        print(); // 输出 
        return ;
    }
    dfs(cur+1); // 填下一个格子，即选择下一位同学 
    vis[cur] = 1; // 这位同学去参加合唱，vis数组设为 1 
    dfs(cur+1); // 当序号为cur的同学去参加合唱时，再次选择第cur+1位同学 
    vis[cur] = 0; //  回溯 
    return ;
}

标记好了之后，就需要输出了

print部分


void print()
{
    for(int i=1;i<=n;i++)
        if(vis[i] == 0) // 若第i位同学不去参加，则输出'N' 
            cout<<'N';
        else // 去参加，输出'Y' 
            cout<<'Y';
    cout<<"\n"; //枚举完之后，输出换行 
    return ;
}

CODE

#include<bits/stdc++.h>
using namespace std;
int n,vis[15]; // 定义bool数组，标记每位同学参加合唱的情况 
void print()
{
    for(int i=1;i<=n;i++)
        if(vis[i] == 0) // 若第i位同学不去参加，则输出'N' 
            cout<<'N';
        else // 去参加，输出'Y' 
            cout<<'Y';
    cout<<"\n"; //枚举完之后，输出换行 
    return ;
}
void dfs(int cur) // 枚举当前需要选择的同学 
{
    if(cur == n + 1) // 如果已经超出了边界，则开始输出 
    {
        print(); // 输出 
        return ;
    }
    dfs(cur+1); // 填下一个格子，即选择下一位同学 
    vis[cur] = 1; // 这位同学去参加合唱，vis数组设为 1 
    dfs(cur+1); // 当序号为cur的同学去参加合唱时，再次选择第cur+1位同学 
    vis[cur] = 0; //  回溯 
    return ;
}
int main()
{
    cin>>n; // 输入将要选择的人数 
    dfs(1); // 从第一位同学开始选起 
    return 0; // 结束代码 
}

完结，撒花！