专栏文章

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

FFine_Dust_Z
P14245题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@minkxbmk
此快照首次捕获于
2025/12/02 04:06
3 个月前
此快照最后确认于
2025/12/02 04:06
3 个月前
查看原文

题目大意

给定长度为 NN 字符串 SS，现在 SS 的所有循环同构 AA 中如果存在 A1A_1 与 ANA_N 相同的情况。

循环同构

找 ii（1≤i≤N1 \le i \le N），将 SiS_i 以前的所有字符移至末尾组成新的字符串 AA 就是 SS 的循环同构。
现在问你：若存在 A1A_1 与 ANA_N 相同的情况，输出最小的 ii。
否则输出 -1。

思路

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

code

CPP
#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;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...