题解：P10296 [CCC 2024 S2] Heavy-Light Composition

· · 题解

一道红题但是我真的写了好久啊

题意

多测，每组数据给你个字符串。定义轻为该字母在本字符串中仅出现 1 次，重为该字母在本字符串中出现 > 1 次，问轻和重是否交替

分析

以下将轻称为 l （light），将重称为 h （heavy）

我们为了统计字母出现次数，可以使用一个桶 bkt[27] 来统计。由于全是小写字母，我们通过 ASCII 码来确定该字母是第几个字母。手推一下就行了，这里直接放出结论： (int)s[i]-96

接下来，我们看第一个字符是 l 还是 h

如果是 l 的话，我们判断下一个字符是不是 h ，反之亦然

当下一个字母不是交替的，我们就结束判断，输出 F 。

然后我们再看交替的问题。

我们可以定义 flag ，为真则是奇数轮，为假则是偶数轮。

对于每个奇数轮和偶数轮，我们都要再次进行 l 与 h 的判断。

奇数轮过后不能再来偶数轮，所以我判断完后们定义 gailunpanduan 为假，在最后我们再将 gailunpanduan 赋值为真。

如果判断 l 后不是 r 或 r 后不是 l ，我们就要直接输出 F 。我尝试用了 goto 语句，但是不起作用。于是我定义了个 aaa 变量。 aaa 为假时就结束循环，输出 F 。 aaa 如果一直循环到结束还是真则说明该字符串合法，输出 T 即可。

放上我写的像石山一样的 2.05KB 的 67 行代码

#include <bits/stdc++.h>
using namespace std;
string s;
//注释掉的都是调试代码
char mode,mode2;
int bkt[27];
bool flag=true,gailunpanduan=true,aaa;
int main(){
    int T,n;
    cin>>T>>n;
    while(T--){
        cin>>s;
        memset(bkt,0,sizeof(bkt));
        for(int i=0;i<s.length();i++){
            int x=s[i]-96;
            bkt[x]++;
            // cout<<x<<endl;
            // for(int j=1;j<=26;j++){
            //     if(bkt[j]!=0) cout<<j<<':'<<bkt[j]<<endl;
            // }
        }for(int i=0;i<s.length()-1;i++){
            if(i==0){//第一个字符
                if(bkt[(int)s[i]-96]>1) {mode='h';flag=true;/*cout<<(int)s[i]-96;*/}//重
                else {mode='l';flag=true;}//轻
            }
            if(flag==true&&gailunpanduan){//奇数轮
                if(mode=='h'){//判h后是不是l
                    if(bkt[(int)s[i+1]-96]==1){
                        mode2='l';
                        flag=false;aaa=true;
                        gailunpanduan=false;
                    }else{
                        aaa=false;
                    }
                }if(mode=='l'){//判l后是不是h
                    if(bkt[(int)s[i+1]-96]>1){
                        mode2='h';aaa=true;
                        flag=false;
                        gailunpanduan=false;
                    }else{
                        aaa=false;
                    }
                }
            }
            // cout<<mode<<' '<<mode2<<endl;
            if(flag==false&&gailunpanduan){//偶数轮
                if(mode2=='h'){//判h后是不是l
                    if(bkt[(int)s[i+1]-96]==1){
                       aaa=true; mode='l';flag=true;gailunpanduan=false;
                    }else{
                        aaa=false;
                    }
                }if(mode2=='l'){//判l后是不是h
                    if(bkt[(int)s[i+1]-96]>1){
                        aaa=true;mode='h';flag=true;gailunpanduan=false;
                    }else{
                        aaa=false;
                    }
                }
            }if(gailunpanduan==false)gailunpanduan=true;
            if(!aaa) break;
        }
        if(!aaa)cout<<'F'<<endl;
        else cout<<'T'<<endl;
    }
    return 0;
}