时间限制:10000ms
单点时限:1000ms
内存限制:256MB
-
描述
网易成立于1997年6月，是中国领先的互联网技术公司。其相继推出了门户网站、在线游戏、电子邮箱、在线教育、电子商务等多种服务，目标是利用最先进的互联网技术，加强人与人之间信息的交流和共享，实现“网聚人的力量”。
网易在线游戏是网易公司的一个重要组成部分，在开发实力、产品线和市场占有率上均是国产网游的领军者。正在运营的广受中国玩家欢迎的游戏包括《新大话西游2》、《梦幻西游2》、《天下3》等等。
小Z一直是网易的粉丝，从网易97年6月成立开始他就一直关注着它的发展，并且玩过几乎所有的网易游戏。同时他也是一名数学爱好者，经常沉迷于研究一些游戏数值的特点。他觉得这些数字的设计和网易本身或许有千丝万缕的关系。
有一天，他在游戏中获得了一串数字，直觉告诉他这不是一串普通的数字串，或许可以破解一些关于网易的秘密。破解的第一步，他很想知道，在这串数字中，最多可以挑出多少个'9706'串。挑选的规则为：
（1）挑出的数字'9','7','0','6'在原串中可以不连续，但是数字的先后顺序不能改变
（2）使用过的数字不能被再次使用
如'123901370997606'可以最多挑出2个'9706'，而'6079'则无法挑出任何一个'9706'。
输入
第一行是整数T(T <= 100)，表示下面有T组数据。
之后T行，每行为一组数据，每组数据为一个字符串。每个字符串的长度L <= 50000。每个字符串只会包含数字['0'...'9']。
输出
输出T行，每行对应一个数据的输出结果，表示字符串最多能挑出多少个'9706'。
- 样例输入
-
4 6097 97069706 997776600069 123901370997606
- 样例输出
-
0 2 1 2
代码：
#include "StdAfx.h"
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
#define MAX_LENGTH 50000
int main (){
int n ;
string str (MAX_LENGTH, 0);
cin>>n ;
while(n --){
cin>>str ;
int length = 0;
int flag [4] ={0 };
for(int i = 0 ; i < str. length() ; ++ i){
if(str [i] == '9' || str[ i] == '7' ||str [i] == '0' || str[i ] == '6'){
str[length ++] = str[ i];
}
}
for(int j = 0 ; j < length ;++j)
{
if(str [j] == '9'){
++flag[ 0];
}
else if (str[ j] == '7' ){
if(flag [1]+ 1 <= flag[ 0]){
++flag[ 1];
}
else flag [1]= flag[0 ];
}
else if (str[ j] == '0' ){
if(flag [2]+ 1<=flag [1]){
++flag[ 2];
}
else flag [2]= flag[1 ];
}
else if (str[ j] == '6' ){
if(flag [3]+ 1<=flag [2]){
++flag[ 3];
}
else flag [3]= flag[2 ];
}
}
cout<<flag [3]<< endl;
}
}