首页 > 试题广场 >

宝石手串

[编程题]宝石手串

热度指数：8509 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\hspace{15pt}$ 小红有一个 $n$ 颗宝石构成的环形宝石手串，即第一颗和最后一颗宝石相连，其中第 $i$ 个宝石的属性为 $s_i$ ；若两个宝石的属性相同，那么这两个宝石会相互排斥，导致断开。
$\hspace{15pt}$ 小红可以从手串中摘掉一些宝石，每次摘掉后，这个宝石左右的两个宝石会相接，手串依旧是环形。

$\hspace{15pt}$ 小红想要破坏这个手串。她想要知道，最少还需要摘掉多少个宝石才会导致手串断开。特别的，当手串上剩余的宝石数量恰好为 $2$ 而依旧没能断开时，视为破坏失败，直接输出 $-1$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数  代表手串初始的宝石数量。
第二行输入一个长度为  、仅由小写字母构成的字符串，代表手串上每个宝石的属性。

除此之外，保证单个测试文件的  之和不超过  。

输出描述:

对于每一组测试数据，如果手环无法破坏，直接输出  ；否则，在一行上输出一个整数，代表手串断开需要的最少操作次数。

示例1

输入

2
2
ac
3
aac

输出

-1
0

算法知识视频讲解

wa哭了

发表于 2025-03-03 20:23:14

#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int t; cin>>t; 展开全文

牛客856751393号

发表于 2025-03-04 17:28:53

while True: try: T = int(input()) for _ in range(T): n = int(input()) s = input() if len(s) == 展开全文

牛客719093728号

发表于 2025-03-03 15:27:20

思路：hash计数法 #include <iostream> #include <cstring> #include <unordered_map> using namespace std; const int INF = 2e9; int main() { 展开全文

鳗鱼山

发表于 2025-04-16 10:03:08

import java.util.HashMap; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] ar 展开全文

牛客505100029号

发表于 2025-03-17 22:57:29

//求最小操作次数即求字符串中两个相同字符之间的最小距离 import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(Sys 展开全文

何成95

发表于 2025-05-26 10:15:00

如注释，比较笨的办法。1、先找到所有重复元素（作为字典的键）及其位置（存储为列表作为字典的值），2、然后遍历所有重复元素的位置，寻找最小相邻距离。 import sys m = int(input()) for _ in range(m): n = int(input()) bras 展开全文

学习小生

发表于 2025-08-24 11:31:38

n = int(input()) for i in range(n): lens = int(input()) arr = list(input()) set_arr = set(arr) # 记录每种字母的所有索引 index = {} for i 展开全文

牛客652808722号

发表于 2025-04-09 14:23:01

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = 展开全文

扎男_

发表于 2025-04-09 16:27:17

// 活动地址：牛客春招刷题训练营 - 编程打卡活动 #include<iostream> #include<algorithm> #include<cmath> #include<vector> #define int long long us 展开全文

永夏360

发表于 2025-05-17 17:01:14

#include <iostream> using namespace std; int main() { int a;cin>>a; while (a--) { // 注意 while 处理多个 case int n ;cin>> 展开全文

问题信息

哈希

难度：

24条回答 181收藏 692浏览

宝石手串

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题