UVA13075 题解

· · 题解

简要题意

给定 a 和 b，构造一个 (a+b) 长的字符串，其中包含 a 个 'C' 和 b 个 'V'，按字典序输出所有满足要求的字符串。

题目思路

通过 DFS 来枚举出每一位，当所有 (a+b) 位都填完，直接输出，再回溯。

这里有个问题，如何实现字典序，题目中提到这个字符串只会存在 'C' 和 'V' 两个字符，很明显，'C' 的字典序先于 'V'，所以只需要在每层递归时先填 'C'，再填 'V' 即可。

注：UVA 格式都很恶心，这题格式需要注意行末无空格，具体实现看代码。

代码实现

通过记录

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
bool is_first;
void dfs(int left_a,int left_b,string str){
    if(left_a==0 && left_b==0){
        if(is_first){ // 判断字符串不为第一个
            cout<<' '; // 否：输出前一个字符串的空格
        }else{
            is_first=1;
        }
        cout<<str; // 避免如果是最后一个，不用输出空格
        return;
    }
    if(left_a>0){ // 如果还能放C，就优先放C
        dfs(left_a-1,left_b,str+'C');
    }
    if(left_b>0){ //注意不要加else
        dfs(left_a,left_b-1,str+'V');
    }
}
int main(){
    int T;
    cin>>T;
    int a,b;
    while(T--){ // 多组数据记得清空
        cin>>a>>b;
        is_first=0;
        string ss="";
        dfs(a,b,ss);
        cout<<endl;
    }
    return 0;
}