首页 > ACM题库 > HDU-杭电 > HDU 1419 Dart-a-Mania-模拟-[解题报告] C++
2013
12-10

HDU 1419 Dart-a-Mania-模拟-[解题报告] C++

Dart-a-Mania

问题描述 :

The game of darts has many variations. One such variation is the game of 301. In the game of 301 each player starts with a score of 301 (hence the name). Each player, in turn, throws three darts to score points which are subtracted from the player’s current score. For instance, if a player has a current score of 272 and scores 55 points with the three darts, the new score would be 217. Each dart that is tossed may strike regions on the dartboard that are numbered between 1 and 20. (A value of zero indicates that the player either missed the dartboard altogether or elected to not throw the dart.) A dart that strikes one of these regions will either score the number printed on the dartboard, double the number printed, or triple the number printed. For example, a player may score 17, 34, or 51 points with a toss of one dart that hits one of the regions marked with a 17. A third way to score points with one dart is to hit the BULLS EYE which is worth 50 points. (There is no provision for doubling or tripling the bull’s eye score.)

The first player to reduce his score to exactly zero wins the game. If a player scores more points than his/her current score, the player is said to have "busted" and the new score is returned to the last current score.

Given a player’s current dart score, write a program to calculate all the possible combinations and permutations of scores on throwing three darts that would reduce the player’s score to exactly zero (meaning the player won the game). The output of the program should contain the number of combinatons and permutations found.

For example, if the player’s current score is 2, then there would be two combinations and six permutations. The combinations would be: 1) obtain a score of 2 on any one dart and zero on the other two, and 2) obtain a score of one on two different darts and zero on the third dart. The order in which this is accomplished is not important.

With permutations the order is significant; therefore the six permutations would be as follows:

Dart 1: 2 0 0 1 1 0
Dart 2: 0 2 0 1 0 1
Dart 3: 0 0 2 0 1 1

(Note: The program doesn’t print out the actual permutations & combinations, just the total number of each.)

输入:

The input file, DARTS.IN, contains a list of integers (each <= 999), one per line, that represent several players’ current scores. A value of zero or less will signify the end of the input file.

输出:

For each positive integer in the input file, 2 or 3 line(s) will be written to the output file, DARTS.OUT.

If the score can be reduced to zero, your program should write the lines:

NUMBER OF COMBINATIONS THAT SCORES x IS c.
NUMBER OF PERMUTATIONS THAT SCORES x IS p.

where x is the value of the player’s score while c and p are the total number of combinations and permutations possible, respectively.
If it is impossible to reduce the player’s score to zero, write the line:

THE SCORE OF x CANNOT BE MADE WITH THREE DARTS.

After the line(s) above are printed, your program should write a line of 70 asterisks to separate output for different scores. The message "END OF OUTPUT" should appear at the end of the output file.

样例输入:

162
175
2
68
211
114
-100

样例输出:

NUMBER OF COMBINATIONS THAT SCORES 162 I9 7.
NUMBER OF PERMUTATIONS THAT SCORES 162 I9 28.
***********************************************************************
THE SCORE OF 175 CANNOT BE MADE WITH THREE DARTS.
***********************************************************************
NUMBER OF COMBINATIONS THAT SCORES 2 I9 2.
NUMBER OF PERMUTATIONS THAT SCORES 2 I9 6.
***********************************************************************
NUMBER OF COMBINATIONS THAT SCORES 68 I9 187.
NUMBER OF PERMUTATIONS THAT SCORES 68 I9 1056.
***********************************************************************
THE SCORE OF 211 CANNOT BE MADE WITH THREE DARTS.
***********************************************************************
NUMBER OF COMBINATIONS THAT SCORES 114 I9 82.
NUMBER OF PERMUTATIONS THAT SCORES 114 I9 445.
***********************************************************************
END OF OUTPUT

说实话,真心觉得这个实在是一个模拟的题目一般,但是知识点却是图论当中的独立集。。。掌握知识点不牢固啊。。

题意就是一个配色方案,对于一条边而言,两端的顶点颜色不能够相同,尽可能的将颜色染为黑色。。求配色方案当中的黑色最多为多少,输出一个最佳配色方案中的黑色节点。。

  #include<iostream>
   #include<stdio.h>
   using namespace std;
   struct node
   {
       int end,next;       
   }edge[10002];
   int head[102],n,m,start,end,maxval,color[102];
   int answer[102];
   void dfs(int i,int j)
   {
       if(i>=n)
       {
           if(j>maxval)
           {
               maxval=j;
               for(int i=1;i<=n;i++)answer[i]=color[i];
           }    
           return ;
       }
       color[i]=-1;
       int end;
       for(end=head[i];end!=-1;end=edge[end].next)
       {
           if(color[edge[end].end]==-1)
           break;
       }
       if(end==-1)dfs(i+1,j+1);
       
        color[i]=1;
        dfs(i+1,j);
        color[i]=0;
       
   }
   int main()
   {
      int t;
      scanf("%d",&t);
      while(t--)
      {
              scanf("%d%d",&n,&m);
              for(int i=1;i<=n;i++)head[i]=-1;
              for(int i=0,Count=0;i<m;i++)
              {
                  scanf("%d%d",&start,&end);
                  edge[Count].end=end;
                  edge[Count].next=head[start];
                  head[start]=Count++;
                  edge[Count].end=start;
                  edge[Count].next=head[end];
                  head[end]=Count++;
              }
              maxval=0;
              dfs(1,0);
              printf("%d\n",maxval);
              for(int i=1;i<=n;i++)if(answer[i]==-1)printf("%d ",i);
              printf("\n");
      }
      return 0;    
   } 
   
   

 

解题报告转自:http://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667120.html


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.