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<stdio.h>
#include<string.h>
 
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<n;i++)
	{
	  if(ch[i]=='/'&&ch[i+1]=='')
	    {
	      dl=i-1;dr=i+2;
	      while(ch[dl]=='/') dl--;
	      while(ch[dr]=='') dr++;
	      dl=i-dl;dr=dr-i-1;
	      up+=dr<dl?dr:dl;
	    }
	}
 
      down=0;
      for(i=0;i<n;i++)
	{
	  if(ch[i]==''&&ch[i+1]=='/')
	    {
	      dl=i-1;dr=i+2;
	      while(ch[dl]=='') dl--;
	      while(ch[dr]=='/') dr++;
	      dl=i-dl;dr=dr-i-1;
	      down+=dr<dl?dr:dl;
	    }
	}
      printf("Case %d: %d %dn",++count,down,up);
  }
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

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>