Group C++B of the 5th Blue Bridge Cup in 2014

Title:

Li Bai drinks

Li Bai, the great poet, has a good life to drink. Fortunately, he never drives.
One day, he came out from home with a wine pot. There were two cups of wine in the pot. As he walked, he sang:
Walk on the street and pick up the pot to get the wine.
Double the price in every shop, and drink when meeting flowers.
Along the way, he met the store 5 times in total and Hua 10 times. He knew that the last time he met Hua, he just drank up the wine. 
Please calculate the order in which Li Bai meets the store and flowers. You can record the meeting store as a and the meeting flower as b. Then: babaabbbabbabbb is a reasonable order. How many answers are there like this? Please work out the number of all possible solutions (including those given in the title).

Idea 1:0 for store, 1 for flower, full arrangement and judgment. (Note: in 14 numbers of full arrangement, the general full arrangement function written by oneself may not be calculated. You can use the built-in next "permutation, which will not be repeated, and it can be calculated soon.)

Code 1:
// Li Bai drinks
#include <bits/stdc++.h>
using namespace std;

int an[15]={0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};
long res(0);

bool judge()
{
    long sta = 2;
    for(int i=0;i<15;++i) {
        if(an[i]==0) sta *= 2;
        else if(an[i]==1) sta -= 1;
    }
    if(sta==0) return true;
    return false;
}

void print()
{
    for(int i=0;i<15;++i) {
        if(an[i]==0) cout << "a";
        if(an[i]==1) cout << "b";
    }
    cout << endl;
}

int main()
{
    do {
        print();
        if(judge()){
            res += 1;   
        } 
    }while(next_permutation(an,an+14));

    cout << res << endl;
    return 0;
} 

Train of thought 2: dfs,15 empty, store or flower, go all the way, and judge at the end.

Code 2: (learn from big brother's code - >https://blog.csdn.net/u014552756/article/details/50573956)
// Li Bai drinks 
#include <bits/stdc++.h>
using namespace std;

char ac[15];
long res(0);

void print()
{
    printf("%s\n",ac);
}

void dfs(int i, int store, int flower, int wine)
{
    if(store>5||flower>10||wine<0) return;
    else if(store==5&&flower==10&&i==15) {
        if(ac[14]=='b'&&wine==0) {
            print();
            res += 1;
        }
        return;
    }

    // Double in store 
    ac[i] = 'a'; 
    dfs(i+1,store+1,flower,wine*2);

    // Have a drink with flowers 
    ac[i] = 'b';
    dfs(i+1,store,flower+1,wine-1);

}


int main()
{
    dfs(0,0,0,2);
    cout << res << endl;
    return 0;
}

Posted on Sun, 05 Apr 2020 07:59:57 -0700 by vbnullchar