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

yummy · 2025-01-21 12:46:19 · 题解

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

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

第一步

为了避免相同的代码写四遍，可以给手指标号：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）：

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 表示当前最大连续敲击即可。

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，并不算很长，这体现了选取一个合适的框架写程序的重要性。