首页 > ACM题库 > HDU-杭电 > Hdu 1382 Ball Toss-模拟[解题报告] C++
2013
12-09

Hdu 1382 Ball Toss-模拟[解题报告] C++

Ball Toss

问题描述 :

Classmates stand in a circle facing inward, each with the direction left or right in mind. One of the students has a ball and begins by tossing it to another student. (It doesn’t really matter which one.) When one catches the ball and is thinking left, she throws it back across the circle one place to the left (from her perspective) of the person who threw her the ball. Then she switches from thinking left to thinking right. Similarly, if she is thinking right, she throws the ball to the right of the person who threw it to her and then switches from thinking right to thinking left.

There are two exceptions to this rule: If one catches the ball from the classmate to her immediate left and is also thinking left, she passes the ball to the classmate to her immediate right, and then switches to thinking right. Similarly, if she gets the ball from the classmate to her immediate right and is thinking right, she passes the ball to the classmate to her immediate left, and then switches to thinking left. (Note that these rules are given to avoid the problem of tossing the ball to oneself.)

No matter what the initial pattern of left and right thinking is and who first gets tossed the ball, everyone will get tossed the ball eventually! In this problem, you will figure out how long it takes.

You’ll be given the initial directions of n classmates (numbered clockwise), and the classmate to whom classmate 1 initially tosses the ball. (Classmate 1 will always have the ball initially.)

输入:

There will be multiple problem instances. Each problem instance will be of the form

n k t1 t2 t3 … tn

where n (2 <= n <= 30) is the number of classmates, numbered 1 through n clockwise around the circle, k (> 1) is the classmate to whom classmate 1 initially tosses the ball, and ti (i = 1, 2, …, n) are each either L or R, indicating the initial direction thought by classmate i. (n = 0 indicates end of input.)

输出:

For each problem instance, you should generate one line of output of the form:

Classmate m got the ball last after t tosses.

where m and t are for you to determine. You may assume that t will be no larger than 100,000.

Note that classmate number 1 initially has the ball and tosses it to classmate k. Thus, number 1 has not yet been tossed the ball and so does not switch the direction he is thinking.

样例输入:

4 2 L L L L
4 3 R L L R
10 4 R R L R L L R R L R
0

样例输出:

Classmate 3 got the ball last after 4 tosses.
Classmate 2 got the ball last after 4 tosses.
Classmate 9 got the ball last after 69 tosses.

//贡献了一次WA,原因是忽略了下面这句话:“Note that classmate number 1 initially has the ball and tosses it to classmate k. 
//Thus, number 1 has not yet been tossed the ball and so does not switch the direction he is thinking. ” 意思是说,虽然球是在同学1的
//手中,但是他是否被传过球,记为false的!要注意啊!还有一个需要注意的就是“she throws it back across the circle one place to the left 
//(from her perspective) of the person who threw her the ball” 要注意括号里面的句子,好重要,即是说:这个方向是你看一个人的左与右的方向,
//而不是一个人自己本身的左与右的方向!
#include <iostream>
#include <string>
using namespace std;

struct Info//储存同学的信息的 
{
    int num;//同学的序号 
    char direction;//想象中的方向 
    bool flag;//是否有接过球,即是话有没有同学传过球给他 
    int leftnum;//在其他同学眼中,他左边的数字! 
    int rightnum;//在其他同学眼中,他右边的数字!
    int left;//就他自己本身来说,他左边的数字! 
    int right;//就他自己本身;来说,他右边的数字! 
}info[35];

int main()
{
    int n, k, i, pre, c, tmp;
    char temp;
    bool ff;
    while (cin >> n && n)
    {
          cin >> k;
          for (i = 1; i <= n; i++)//信息的输入 
          {
              cin >> temp;
              info[i].num = i;
              info[i].direction = temp;
              info[i].flag = false;
          } 
          //对他左右边数的赋值 
          info[1].rightnum = 2;
          info[1].left = 2;
          info[1].leftnum = n;
          info[1].right = n;
          info[n].rightnum = 1;
          info[n].left = 1;
          info[n].leftnum = n-1;
          info[n].right = n-1;
          for (i = 2; i < n; i++)
          {
              info[i].rightnum = i+1;
              info[i].left = i+1;
              info[i].leftnum = i-1;
              info[i].right = i-1;
          }
          
          pre = 1;
          c = 1;
          ff = false;
          while (1)
          {
                for (i = 1; i <= n; i++)
                {
                    if (!info[i].flag)
                    {
                        ff = true;
                        break;
                    }
                }
                //分情况讨论其中的四种情况! 
                if (ff)
                {
                    if (info[k].direction == 'L')
                    {
                        info[k].flag = true;
                        if (pre == info[k].left)
                        {
                            info[k].direction = 'R';
                            tmp = info[k].right;
                        }
                        else 
                        {
                            info[k].direction = 'R';
                            tmp = info[pre].leftnum;
                        }
                    }
                    else if (info[k].direction == 'R')
                    {
                        info[k].flag = true;
                        if (pre == info[k].right)
                        {
                             info[k].direction = 'L';
                             tmp = info[k].left;
                        }
                        else 
                        {
                             info[k].direction = 'L';
                             tmp = info[pre].rightnum;
                        }
                    }
                    pre = k;
                    k = tmp;
                    ff = false;
                    c++;
                }
                else  break;
          }
          
          cout << "Classmate " << pre << " got the ball last after " << c-1 << " tosses." << endl;;
    }
    
    system("pause");
}

 

转自:http://blog.csdn.net/yzl_rex/article/details/7609035


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false