Problem
题目简述
给你一个整数 \(n\) 和字符串 \(s\)，问：能不能在小于 \(n\) 次操作的情况下，输出字符串 \(s\)。
有两次操作可供使用：
- 在已打出内容的最后添加一个字符。
- 复制已打出内容的一个连续的子串并加到内容的末尾。
思路
用到的容器：\(\text{map}\)。
用 \(\text{map}\) 来记录每个子串出现的次数，然后求出字符串中长度为 \(2\) 的相同字串个数。
附：\(\text{map}\) 的简单介绍：
map<key的数据类型, value的数据类型>
它是 C++ 里的 STL 容器，底层用红黑树实现，如果需要 \(\text{map}\) 需要 include <map>。
取 \(\text{map}\) 里面元素的方法：mp[key]。
本题里面 \(\text{map}\) 的函数介绍：
mp.find()查找元素(没找到返回mp.end())mp.end()返回的是 \(\text{map}\) 最后一个元素地址的下一个地址，一定注意不是最后一个元素！
代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int t, n;
bool f;
string s1, s2;
map<string, int> mp;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); // 读入流优化
cin >> t;
while (t--) {
mp.clear(); // 注意多组测试数据的情况下，一定看看哪些变量需要清空
f = false;
cin >> n >> s1;
for (int i = 0; i < n; i++) {
s2 = "";
s2 = s1[i - 1];
s2 += s1[i];
if (!mp[s2]) { mp[s2] = i; continue; }
if(mp[s2] != i - 1 && mp.find(s2) != mp.end()) { // 找到字符
cout << "YES" << endl;
f = true;
break;
}
}
if (!f) cout << "NO" << endl;
}
return 0;
}