一道很难的算法题

只想到一种暴力方法,就是找到一个最短的+串进行枚举所有的匹配可能,由于长度最多是8,2^8不是很大还可以接受.然后对所有的+串进行一次改进,每当发现一个匹配串不符合某个+串,则进行添加,若无论如何都无法匹配,则否决.然后再对所有的-串进行一次检查,若匹配则否决,最后剩下的匹配串里面输出最短那个.

时间复杂度在O(2^m*n*m)级别,还算在接受范围之内.

不过的确不优美,最好是能找到更优的做法.

/*

*将环拆成0到n的直线，0和n都表示该苦逼学生，以0为球的出发点

*/

#include<stdio.h>

int a[31][31]//a[i][j]表示球经过j步走到节点i的走法数量

main()

{

    int m,n

    scanf("%d %d",&n,&m)

    for(int i=0i<=n++i)

    {

        if(i==1) a[i][1]=1

        else a[i][1]=0

    }

    for(int j=2j<=m++j)

    {

        for(int i=0i<=n++i)

        {

            if(i<=1) a[i][j]=a[i+1][j-1]//0，1只接受从右边传来的球

     局春尘       森升else if(i>=n-1) a[i][j]=a[i-1][j-1]//n-1，n只接受从左边传来的球

     桐禅       else a[i][j]=a[i-1][j-1]+a[i+1][j-1]//其他情况则把两种可能性相加

        }

    }

    //只考虑初始从左边出发的情况（0为出发点），所以最终结果要乘2

    printf("%d\n",2*(a[0][m]+a[n][m]))

}

出题人的表达能力太差，题目叙述得很糟糕，最后两个例子也错了

比较好的叙述是，输入n，输出从0到32中取6项按字典序排序下的第n个组合（从第0个组合0,1,2,3,4,5开始计）

这种谈不上什么难题，只不过是入门级的问题

在给定前k项梁郑备的（记第k项为m）情况下余下的项共有C(32-m,6-k)种情况，这里C(x,y)表示x取y的组合数，以此编程即可

给你一个例子

#include <stdio.h>

int binom(int n, int m)

{

    int i, c = 1

    if (2*m > n)

        n = n-m

    for (i = 1 i <= m i++)

        c = c*(n+1-i)/i

    return c

}

int main()

{

    int i, n

    int A[6] = {-1}

    while (scanf("%d", &n) != EOF)

    {

        n++

   丛兄     if (n <= 0 || n > binom(33, 6))

        {

            printf("Invalid input\n")

            continue

        }

        for (i = 1 i <= 5 i++)

        {

            for (A[i] = A[i-1] + 1  A[i]++)

            {

                int t = binom(32 - A[i], 6 - i)

    橡毁            if (n > t)

                    n -= t

                else

                    break

            }

            printf("%d,", A[i])

        }

        printf("%d\n", A[i-1] + n)

    }

    return 0

}

---