游客 注册 | 登录
中文 | En

1706 - 高分笔记叠罗汉

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

又到了天勤计算机考研《高分笔记》专业课辅导系列书籍发售的时候了，在ACM俱乐部团队的办公室里堆着许多新版的高分笔记准备出售。
团队成员平时喜欢用高分笔记叠罗汉，以此来锻炼身体。不过，他们是按照一定的规则来叠的，规则如下：
（为方便起见，我们用D代表数据结构高分笔记，用P代表计算机组成原理高分笔记，用O代表操作系统高分笔记，用N代表计算机网络高分笔记。）
（1）D可以叠在P、O、N三者任意一个的上面，但是D上面就不能再叠其他的书了。
（2）P、O、N三者可以互相层叠，也可以多本P（或O、N）叠在一起。但是，不允许大于等于2本的D叠在一起。
（3）D的下方必须至少叠有一本书，且每堆的最上面必须是D，否则不算作一堆。
现在给你一个序列，表示他们拿书的顺序，后取的书只能放在先取的上面。如果某本书无法叠放，则抛弃。
请你编程计算他们叠出的每堆书的本书。

题目输入

输入包含多组测试数据。
每组输入占一行，为一个字符串，字符串中只包含D、P、O、N四个字母，此字符串从左往右表示他们拿书的顺序，字符串的长度不大于50。

题目输出

对于每组输入，在一行内按照先后顺序输出他们叠出的每堆书的本数，相邻的结果之间输出一个空格。如果一堆都叠不出来，则输出0。

输入/输出样例

输入格式

POND
DPPODNOD
ONPDNNDODPP
DPON

输出格式

4
4 3
4 3 2
0

C语言解答

#include<stdio.h>
#include<string.h>

int main(){
    char str[100];
    int i, count, len,heap;
    while(scanf("%s", str)==1){
        count=0;
        heap=0;
        len=strlen(str);
        for(i=0; i<len; i++){
            if(str[i]=='D'){
                if(count>0){
                    printf("%d", count+1);
                    heap++;
                    count=0;
                    break;
                }
            }
            else{
                 count++;
            }
        }
        i++;
        for(; i<len; i++){
            if(str[i]=='D'){
                if(count>0){
                    printf(" %d", count+1);
                    heap++;
                    count=0;
                }
            }
            else{
                 count++;
            }
        }
        if(heap==0) printf("0\n"); 
        else printf("\n");        
    }
    return 0;
}

C++解答

#include <cstdio>
#include <stack>
using namespace std;

int main() {
	int i, flag, k;
	char s[51];
	while (scanf("%s", s) != EOF) {
		stack<char> S;
		for (flag = k = i = 0; s[i]; i++) {
			if (s[i] == 'D') {
				if (!S.empty()) {
					if (flag)
						printf(" %d", S.size() + 1);
					else {
						printf("%d", S.size() + 1);
						flag = 1;
					}
					k = 1;
				}
				while (!S.empty())
					S.pop();
			} else
				S.push(s[i]);
		}
		if (!k)
			printf("0");
		printf("\n");
	}
	return 0;
}

Java解答

import java.io.*;
import java.util.*;
import java.util.Arrays;

public class Main{
  public static void main(String [] args){
    final int NUM = 51;
    String  s;
    int i, j;
    Scanner in = new Scanner(System.in); 
    while(in.hasNext()){
      s = in.next();
      int[][]result = new int[NUM][2];
      for(i=0; i<NUM; i++){
        result[i][0] = 0;
        result[i][1] = 0;
      }

      int statics = 0;
      int length = s.length();

      for(i=0; i<length; i++){
        if(s.charAt(i) != 'D'){
          result[statics][0]++;
        }
        else{
          if(result[statics][0] > 0)
            result[statics][1] = 1; 
          else{
            result[statics][1] = 0;
            continue;
          }
          statics++;
        }
      }

      i=0; 
      while(result[i][0] != 0){
        
        if(result[i][1] == 0){
          i++;
          continue;
        }
        if(i != 0)
          System.out.print(" ");
        System.out.print(result[i][0]+1);
        
        i++;
      }
      if(result[0][1] == 0)
        System.out.print("0");

      System.out.print("\n");
    }
  }
}
请先登陆