题解：CF798B Mike and strings

FISH酱 · 2025-08-02 22:59:03 · 题解

前置知识

你需要了解字符串知识，并且有一定的推理能力。

思路讲解

题意很清晰，这里不再赘述。

假设有当前字符串和目标字符串，希望通过若干次操作得到目标；我们把当前字符串想象成一条链子，每次把开头字母放到最后本质是一次旋转，我们想旋转找到新的起点，使得其与目标字符串一致；转化成代码，我们可以把当前字符串拼接两次得到新字符串，查找是否包含目标字符串，即查找旋转变换是否可行，如果可行，目标字符串第一次出现的位置即为最小旋转次数。

综上所述，我们通过暴力枚举每一个字符串作为目标，再枚举其他字符串：针对每个判断是否能旋转变换得到，若可以就累加次数，若不可以就说明该目标不可行，退出枚举；最后，如果全部可行就更新最小操作次数，否则找下一个目标。

代码展示

下面是我的代码，仅供参考：

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define inf 0x3f3f3f3f
#define endl "\n"

int n,minn=inf;
string s[57];

int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin>>s[i];

    for(int i=1;i<=n;i++){
        bool y=0;
        int ans=0;

        for(int j=1;j<=n;j++){
            if(i==j) continue;
            string h=s[j]+s[j];
            int w=h.find(s[i]);
            if(w==string::npos){
                y=1;
                break;
            }else{
                ans+=w;
            }
        }

        if(!y) minn=min(minn,ans);
    }

    if(minn==inf) cout<<-1;
    else cout<<minn;

    return 0;
}