题解 B4126：古希腊掌管节奏的神

本题考查字符串的综合应用，对选手分析题意、整体规划自己程序的能力有初步的考察。

一种可能的实现是把程序分为两步：第一步把字符串转化成二维数组，表示每一拍的每一根手指是否敲击桌面；第二步则是根据第一步得到的数组求出连击数量。

第一步

为了避免相同的代码写四遍，可以给手指标号：L,L',R,R' 分别用

0,1,2,3

表示。然后我们规定

tap_{t,fin}

表示

t

时刻

fin

手指是否敲击。

整体求值流程是从前往后按顺序读取字符串内容。为了把手指信息正确填入

tap

数组，还要记录当前的

t

表示接下来读取第几拍。

先忽略括号，考虑读取到一个字母（假设为 s[i]）怎么办：

如果字母是 L 则 fin=0，否则 fin=2。
如果下一个字符是引号，那么 fin 额外 $+1$ 。
把 tap[t][fin] 设为 $1$ ，然后把 $t$ 增加 $1$ 。

接下来考虑括号。

在括号内的手指的读取流程和括号外完全一致，唯一的不同点在于，每次读取结束后不需要把

t

增加

1

。

因此我们可以用一个变量 single 表示“是否是单击模式”，如果是则每次读取结束后

t

增加

1

，否则

t

增加

0

，换言之把 t+=1 换成 t+=single 即可。

下面给出第一步的参考代码（注意，

t

的初值为

1

）：

CPP

scanf("%s%d",s,&type);
	int n=strlen(s),single=1;
	for(int i=0;i<n;i++){
		if(s[i]=='(')
			single=0;
		else if(s[i]==')'){
			single=1;
			t++;
		}
		else{
			int fin=0;
			if(s[i]=='R')fin=2;
			if(s[i+1]=='\''){
				fin++;
				i++;
			}
			tap[t][fin]=1;
			t+=single;
		}
	}
	printf("%d\n",t-1);

第二步

外层循环

fin

枚举四根手指，考虑内层循环，用一个 cur 表示当前连续敲击，以及 best 表示当前最大连续敲击即可。

CPP

if(type==0)
		return 0;
	for(int fin=0;fin<4;fin++){
		int best=0,cur=0;
		for(int i=1;i<t;i++){
			if(tap[i][fin]){
				cur++;
				best=max(cur,best);
			}
			else
				cur=0;
		}
		printf("%d ",best);
	}

std 总长为 667B，并不算很长，这体现了选取一个合适的框架写程序的重要性。

题解 B4126：古希腊掌管节奏的神

文章操作

第一步

第二步

相关推荐

评论

题解 B4126：古希腊掌管节奏的神