题解：P14245 [CCPC 2024 Shandong I] 左移

Fine_Dust_Z · 2025-10-17 22:58:47 · 题解

题目大意

给定长度为 N 字符串 S，现在 S 的所有循环同构 A 中如果存在 A_1 与 A_N 相同的情况。

循环同构

找 i（1 \le i \le N），将 S_i 以前的所有字符移至末尾组成新的字符串 A 就是 S 的循环同构。

现在问你：若存在 A_1 与 A_N 相同的情况，输出最小的 i。

否则输出 -1。

思路

每次左移 S_1 会被移至最后，也就是说 S_1 等于 S_2，那么左移后就是一个合法字符串。这道题就转变为如果 S 最开始就合法输出 0，接着从 1 枚举 i，若 S_i 等于 S_{i+1} 就输出并结束枚举，最终若 S 没有一个循环同构是合法的就输出 -1。

code

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x) {
    x = 0;
    char c;
    int sgin = 1;
    do {
        c = getchar();
        if (c == '-')sgin = -1;
    } while (!isdigit(c));
    do {
        x = x * 10 + c - '0';
        c = getchar();
    } while (isdigit(c));
    x *= sgin;
}
void solve(){
    string s;
    cin>>s;
    if(s[0]==s[s.size()-1]){// 开始合法
        puts("0");
        return ;
    }
    for(int i=0;i<s.size()-1;i++){// 枚举所有 i
        if(s[i]==s[i+1]){
            cout<<i+1<<endl;// 输出并结束
            return ;
        }
    }
    puts("-1");//没有一个循环同构合法
    return ;
}
int main() {
    int t;
    read(t);
    while(t--)solve();
    return 0;
}