FOJ 1906解体报告

http://acm.fzu.edu.cn/problem.php?pid=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 %d\n",++count,down,up);   }   return 0; }