首页 > ACM题库 > HDU-杭电 > HDU 3328-Flipper-栈-[解题报告]HOJ
2014
03-16

HDU 3328-Flipper-栈-[解题报告]HOJ

Flipper

问题描述 :

Little Bobby Roberts (son of Big Bob, of Problem G) plays this solitaire memory game called Flipper. He starts with n cards, numbered 1 through n, and lays them out in a row with the cards in order left-to-right. (Card 1 is on the far left; card n is on the far right.) Some cards are face up and some are face down. Bobby then performs n – 1 flips ― either right flips or left flips. In a right flip he takes the pile to the far right and flips it over onto the card to its immediate left. For example, if the rightmost pile has cards A, B, C (from top to bottom) and card D is to the immediate left, then flipping the pile over onto card D would result in a pile of 4 cards: C, B, A, D (from top to bottom). A left flip is analogous.

The very last flip performed will result in one pile of cards ― some face up, some face down. For example, suppose Bobby deals out 5 cards (numbered 1 through 5) with cards 1 through 3 initially face up and cards 4 and 5 initially face down. If Bobby performs 2 right flips, then 2 left flips, the pile will be (from top to bottom) a face down 2, a face up 1, a face up 4, a face down 5, and a face up 3.

Now Bobby is very sharp and you can ask him what card is in any position and he can tell you!!! You will write a program that matches Bobby’s amazing feat.

输入:

Each test case will consist of 4 lines. The first line will be a positive integer n (2 ≤ n ≤ 100) which is the number of cards laid out. The second line will be a string of n characters. A character U indicates the corresponding card is dealt face up and a character D indicates the card is face down. The third line is a string of n – 1 characters indicating the order of the flips Bobby performs. Each character is either R, indicating a right flip, or L, indicating a left flip. The fourth line is of the form m q1 q2 . . . qm, where m is a positive integer and 1 ≤ qin. Each qi is a query on a position of a card in the pile (1 being the top card, n being the bottom card). A line containing 0 indicates end of input.

输出:

Each test case will consist of 4 lines. The first line will be a positive integer n (2 ≤ n ≤ 100) which is the number of cards laid out. The second line will be a string of n characters. A character U indicates the corresponding card is dealt face up and a character D indicates the card is face down. The third line is a string of n – 1 characters indicating the order of the flips Bobby performs. Each character is either R, indicating a right flip, or L, indicating a left flip. The fourth line is of the form m q1 q2 . . . qm, where m is a positive integer and 1 ≤ qin. Each qi is a query on a position of a card in the pile (1 being the top card, n being the bottom card). A line containing 0 indicates end of input.

样例输入:

5
UUUDD
RRLL
5 1 2 3 4 5
10
UUDDUUDDUU
LLLRRRLRL
4 3 7 6 1
0

样例输出:

Pile 1
Card 1 is a face down 2.
Card 2 is a face up 1.
Card 3 is a face up 4.
Card 4 is a face down 5.
Card 5 is a face up 3.
Pile 2
Card 3 is a face down 1.
Card 7 is a face down 9.
Card 6 is a face up 7.
Card 1 is a face down 5.

#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
stack<int> s[105];         //每张牌看成一个栈
int main()
{
  int n,m,num=1,i,j,a[105],k;
  char str[105];
  int ok[105];               //标记每张牌的状态
  while(scanf("%d",&n)!=EOF)
  { 
    if(n==0)
         break;
    scanf("%s",str);
    for(i=0;i<n;i++)
    {
       if(str[i]=='U')
           ok[i]=1;
       else
           ok[i]=0;
    }
    
    int l=0,r=n-1;
    for(i=0;i<n;i++)
        s[i].push(i);       
    scanf("%s",str);
    for(i=0;i<n-1;i++)
    {
       if(str[i]=='L')
       { 
         l++;
         for(j=0;j<l;j++)
             ok[j]=1-ok[j];
         while(!s[l-1].empty())
         {
             s[l].push(s[l-1].top());
             s[l-1].pop();
         }
       }
       else
       {
         r--;
         for(j=n-1;j>r;j--)
             ok[j]=1-ok[j];
         while(!s[r+1].empty())
         {
           s[r].push(s[r+1].top());
           s[r+1].pop();
         }
       }
    }
     for(i=0;i<n;i++)
     {
         a[i]=s[l].top();
         s[l].pop();
     }
     printf("Pile %d\n",num++);
     scanf("%d",&m);
     while(m--)
     {  
        scanf("%d",&k);
        printf("Card %d is a face ",k);  
        k--;  
        printf(ok[a[k]]?"up ":"down ");  
        printf("%d.\n",a[k]+1);  
     }
  }
  return 0;
}

参考:http://blog.csdn.net/steamqueen/article/details/7730304


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。