astar2006百度之星参考源程序.txt

06百度之星题目和解答!

    if( side == A )
    {
        a += score;
        if( Win(a,b) )
        {
            if( Win(a-1,b) )
                return Failed;
            else
            {
                ++aWin;
                ScoreTab[nMatch][A] = a;
                ScoreTab[nMatch][B] = b;
                ++nMatch;
                a = b = 0;
                if( aWin == 3 )
                    return Finished;
                else
                    return Success;
            }
        }
    }
    else
    {
        b += score;
        if( Win(b,a) )
        {
            if( Win(b-1,a) )
                return Failed;
            else
            {
                ++bWin;
                ScoreTab[nMatch][A] = a;
                ScoreTab[nMatch][B] = b;
                ++nMatch;
                a = b = 0;
                if( bWin == 3 )
                    return Finished;
                else
                    return Success;
            }
        }
    }
    return Success;
}

void Solve(int start, enum SIDE side)
{
    if( unknown )
        return;
    if( start == nNumber )
    {
        if( a!=0 || b!=0 )
            return;
        if( !hasOldAnswer )
        {
            int i;
            hasOldAnswer = 1;
            Old_nMatch = nMatch;
            for(i=0; i<nMatch; ++i)
            {
                Old_ScoreTab[i][A] = ScoreTab[i][A];
                Old_ScoreTab[i][B] = ScoreTab[i][B];
            }
        }
        else
        {
            if( Old_nMatch != nMatch )
                unknown = 1;
            else
            {
                int i;
                for(i=0; i<nMatch; ++i)
                {
                    if( Old_ScoreTab[i][A] != ScoreTab[i][A] )
                    {    unknown = 1;    break;    }
                    else if( Old_ScoreTab[i][B] != ScoreTab[i][B] )
                    {    unknown = 1;    break;    }
                }
            }
        }
        return;
    }
 if( Numbers[start] != 10 )
    {
        enum Result tmp = AddScore(side, Numbers[start]);
        if( tmp == Failed )
            return;
        else if( tmp==Finished && nNumber-start!=1 )
            return;
        else /* Success || Finished */
            Solve(start+1, (enum SIDE)(AB-side));
    }
    else
    {
        enum Result tmp;
        int ta,tb,taWin,tbWin,tnMatch;
        ta = a;
        tb = b;
        taWin = aWin;
        tbWin = bWin;
        tnMatch = nMatch;

        tmp = AddScore(side,10);
        if( tmp == Failed )
            return;
        else if( tmp==Finished && nNumber-start!=1 )
            return;
        else
            Solve(start+1, (enum SIDE)(AB-side));

        a = ta;
        b = tb;
        aWin = taWin;
        bWin = tbWin;
        nMatch = tnMatch;
        tmp = AddScore(side,10+Numbers[start+1]);
        if( tmp == Failed )
            return;
        else if( tmp==Finished && nNumber-start!=2 )
            return;
        else
            Solve(start+2, (enum SIDE)(AB-side));
    }
}

int main(int argc, char *argv[])
{
    int nCase;
    FILE *fin;
    fin = fopen(argv[1], "r");
    if( !fin )
    {
        printf("Error: cannot open input file.\n");
        return 1;
    }
    fscanf(fin, "%d", &nCase);
    while( nCase-- )
    {
        int i;
        fscanf(fin, "%d", &nNumber);
        for(i=0; i<nNumber; ++i)
        {
            char tmp[2];
            fscanf(fin, "%s", tmp);
            if( *tmp == 'X' )
                Numbers[i] = 10;
            else
                Numbers[i] = (*tmp-'0');
        }
        hasOldAnswer = 0;
        a = b = aWin = bWin = nMatch = 0;
        unknown = 0;
        Solve(0,A);
        assert( hasOldAnswer );
        if( unknown )
            printf("UNKNOWN\n");
        else
        {
            for(i=0; i<Old_nMatch; ++i)
                printf("%d:%d\n", Old_ScoreTab[i][A], Old_ScoreTab[i][B]);
        }
        if( nCase != 0 )
            printf("\n");
    }
    fclose(fin);
    return 0;
}
/////////////////////////////////////////////////////////////////////


3.变态比赛规则 
/*
算法分析：
1。用数组total[]存储可能存在的比赛场数。
2。顺序分析把n个人分成2-（n-1）个组的情况，即顺序分析k= 2-（n-1）
A 用数组fenfa[]存储分成k组时各种不同组合的比赛场数，用数组part[]存储存储具体的组合情况，
即每组有多少人 。
B 将问题“求把n个人分成k组时各种不同组合的情况”转化为：
      将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)，
例如:n=7,k=3,下面三种分法被认为是相同的。
    1，1，5；     1，5，1；    5，1，1；
    求各种不同分法的组合。
C  把求得的各种不同分法的组合存储到数组part[]中。再根据数组part[]计算每种组合的比赛场数。
D  把每种组合的比赛场数存储到数组fenfa[]中。
3。按照上面的分析方法，可以产生n-1个一维数组fenfa[]，把每个数组fenfa[]的值存储到数组total[]。
4。根据输入数据，在数组total[]中进行分析判断。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 100;
void Readata(const char *filename);
void SplitNumber(int n, int k, int step, int part[], int fenFa[], int &top);
int NumGame(const int part[], int low, int high);

int main()
{
    time_t startTime;
    time_t endTime;
    time(&startTime);

    Readata("in.txt");

    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}

void Readata(const char *filename)
{
      fstream in(filename);
      if (!in)
            return ;   //结束程序执行

      while (!in.eof())
      {
            int data[2];

            in >> data[0];
            in >> data[1];
            //cout << data[0] << ' ' << data[1] << endl;
            int *total = new int[data[0]*data[0]*data[0]];//存储可能存在的比赛场数
            total[0] = 0;
            int t = 1;
            for (int k=2; k<=data[0]; k++)//分析各种分组可能产生的比赛场数
            {
                  int *fenFa = new int[k*data[0]];//存储分成k组时各种不同组合的比赛场数
                  int *part = new int[k+1];//存储具体的组合情况，即每组有多少人

                  part[0] = 1;//为处理方便，不考虑下标0，并使part[0] = 1
                  int top = 0;//累积各种不同组合的数量
                  SplitNumber(data[0], k, 0, part, fenFa, top);//处理各种不同组合的分法

                  //for (int i=0; i<top; i++)
//                        cout << fenFa[i] << ' ';
//                  cout << endl;
                  for (int i=0; i<top; i++)//存储可能存在的比赛场数
                        total[t++] = fenFa[i];

                  delete []part;
                  delete []fenFa;
            }
            int i;
            for (i=0; i<t; i++) //判断是否可能存在data[1]场比赛
                  if (data[1] == total[i])
                  {
                        cout << "YES" << endl;
                        break;
                  }
            if (i == t)
                  cout << "NO" << endl;
            delete []total;
      }

    in.close(); //关闭文件
}

void SplitNumber(int n, int k, int step, int part[], int fenFa[], int &top)
{
      if (k == 2)
    {
            for (int i=part[step]; i<=n/2; i++)
            {
                  if (n-i >= i)
                  {
                        part[step+1] = i;
                        part[step+2] = n-i;
                        //for (int j=1; j<=step+2; j++)
//                              cout << part[j] << ' ';
//                        cout << endl;

                        fenFa[top++] = NumGame(part, 1, step+2); //存储每种组合的比赛场数
                  }
        }
      }
      else
      {
            for (int i=part[step]; i<=n/2; i++)
            {
                   part[step+1] = i;
                   SplitNumber(n-i, k-1, step+1, part, fenFa, top);
            }
      }
}

int NumGame(const int part[], int low, int high)//计算每种组合的比赛场数
{
      int sum;

      if (low == high) //如果只有1个组，比赛场数为0
            sum = 0;
      else if (low == high-1)//如果有2个组，比赛场数为两组人数的乘积
            sum = part[low] * part[high];
      else  //如果多于2个组，先把多个组合并成两个大组，再递归处理每个大组
      {
            int mid = (low + high) / 2 ;
            int sum1 = 0;
            for (int i=low; i<=mid; i++)
                  sum1 += part[i];

            int sum2 = 0;
            for (int i=mid+1; i<=high; i++)
                  sum2 += part[i];

            sum = sum1 * sum2;
            sum += NumGame(part, low, mid) + NumGame(part, mid+1, high);
      }

      return sum;
}