首页 > ACM题库 > HDU-杭电 > Hdu 1854 Q-Sequence-字符串[解题报告] C++
2013
12-23

Hdu 1854 Q-Sequence-字符串[解题报告] C++

Q-Sequence

问题描述 :

A Q-sequence is defined as:

Q-Seq := 0 or
Q-Seq := Q-seq Q-seq 1

That is to say a Q-Sequence is a single ’0′ or two Q-Sequences followed by an ’1′.

Given a sequence of ’0′s and ’1′s, you are to determine whether it is a Q-Sequence.

输入:

The first line is a number n refers to the number of test cases. Then n lines follows, each line has a string made up of ’1′s and ’0′s. The maximum length of the sequence is 1000.

输出:

The output contain n lines, print "Yes" if it is a Q-sequence, otherwise print "No".

样例输入:

3
0010011
0101
00011

样例输出:

Yes
No
Yes

用int flag记录字符串中S-Q序列)的数量,对字符逐一分析:
起始flag=0;
若发现字符是 ’0′ ,flag++;
若发现字符是 ’1′ ,flag–;(占用之前的两个S-Q组成一个新的S-Q,所以个数减一)
……

如果检查某个是 ’1′ 的字符时发现 flag==1 ,则这个数列的整体不可能满足S-Q的定义(因为每个1必须和前面的两个S-Q序列结合才能组成一个新的S-Q序列,前面不足一个S-Q的话后面再就没可能凑成S-Q序列了),直接输出No并结束循环即可;
如果检查完了所有的字符,发现此时flag的值为1(就说明这个字符串中一共只有一个S-Q序列),即输出Yes

#include<stdio.h>
#include<string.h>
char s[1005];
int flag;
int  search(char * s)
{
int len=strlen(s);
int i;
flag=0;
for(i=0;i<len;i++)
{
if(s[i]=='0')
{
flag++;
}
else if(s[i]=='1')
{
if(flag==1)
return flag=0;
flag--;
}
}
if(flag==1)
return flag;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
search(s);
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}