FOJ 1906解题报告

Problem Description

There is a sequence that only consists of characters ‘/’ and ‘’. You should calculate the number of down sequences and up sequences respectively in the given sequence.
A down sequence is defined as follows:
1. “/” is a down sequence.
2. If S is a down sequence, then “S/” is also a down sequence.
3. Any other sequences are not a down sequences.
Similarly, an up sequence is defined as follows:
1. “/” is an up sequence.
2. If S is an up sequence, then “/S” is also an up sequence.
3. Any other sequences are not an up sequences.
For example, sequences “/”, “//” and “///” are all up sequences, while “/”, “/” and “//” are not. Sequences “/”, “//” and “///” are all down sequences, while “/”, “//” and “//” are not. There is only one down sequence in the sequence “//”, that is “/”. There are two up sequences in the sequence “//”, they are “/” and “//”.
Your task is to solve this problem.

Input

The first line of the input contains an integer T (T <= 10), indicating the number of cases. Each case begins with a line containing one integer n (1n100), the length of the sequence. The next line contains the sequence, consisting of characters ‘/’ and ‘’.

Output

For each test case, print a line containing the test case number (beginning with 1) and two numbers separated by a space indicating the number of down sequences and up sequences respectively in the given sequence.

Sample Input

3
2
/
7
////
15
//////////

Sample Output

Case 1: 0 1
Case 2: 1 3
Case 3: 5 5

Source

2010年全国大学生程序设计邀请赛(福州)热身赛
其实这是一道非常水的题目,题意大概是说,像’/’就是一个 up序列,而’//’就是2个up序列,同理’/’就是一个down序列,’//’是两个down序列,输入一行只包含’/’和”的字符串,然后统计出up和down序列的个数,其实只要进行两次线性扫描就可以了。似乎热身赛那天我把题目理解成类似括号匹配的题目,而且交了一段错误的代码还AC了。之后到FOJ提交,怎么也过不了。只能恨我英语实在太烂了,如果不是后来SunriseLin(最佳女队哦)给我看她的代码我还真不知道自己把整个题目都理解错了(RP暴涨,那天居然可以AC)。
思路:在读入字符串后,遍历数组,找到每个’/’后开始往前后扩展,就可以知道以这个’/’为中心的up序列有多长了。同理统计出down序列。

Code

#include
#include
int main()
{
  int t,n,x,i,count=0,up,down,dr,dl;
  char ch[105];
  bool flag;
  scanf("%d",&t);
  while(t--){
      scanf("%d",&n);
      scanf("%s",ch);
      up=0;
      for(i=0;i
					
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>