Categories

HOJ 1442 Lotto

生成组合数.

借用了prev_permutation(),对字符串s进行全排列

s中有6个’1′,其余均为零

打印的时候,当s对应的位是’1′,就输出对应位的数字.

My code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
 
int main()
{
    unsigned k,num[13];
    unsigned i;
    bool flag,flag2=false;
 
    while (cin>>k,k)
    {
        if (flag2) cout<<endl;
        else flag2=true;
        for (i=0;i<k;i++) cin>>num[i];
        string s("111111");
        s.insert(s.end(),k-6,’0);
 
        do
        {
            flag=false;
            for (i=0;i<s.size();i++)
            {
                if (s[i]==1)
                {
                    if (flag) cout<<" ";
                    else flag=true;
                    cout<<num[i];
                }
            }
            cout<<endl;
        }
        while (prev_permutation(s.begin(),s.end()));
    }
 
    return 0;
}

用prev_permutation()只是一种投机取巧的办法,

Edelweiss 大牛的代码才真正体现了题目的用意.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
 
int a[20], b[10];
 
void Perm(int top, int n)
{
    if (top >= 6)
    {
        printf("%d", b[0]);
        for (int i = 1; i < 6; ++ i) printf(" %d", b[i]);
        putchar(’\n’);
        return;
    }
 
    for (int j = top; j < n; ++ j)
    {
        if (!top || a[j] > b[top - 1])
        {
            b[top ++] = a[j];
            Perm(top, n);
            – top;
        }
    }
}
 
int main()
{
    int n, i, t = 0;
 
    while ( scanf("%d", &n) == 1 && n )
    {
        for (i = 0; i < n; ++ i)     scanf("%d", &a[i]);
        if (t ++ > 0)    putchar(’\n’);
        Perm(0, n);
    }
 
    return 0;
}

1 comment to HOJ 1442 Lotto

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

*