codeforce每日一题汇总
题目链接
题目描述
给定一个字符串,我们最少可以用多少个长度为2的字符串拼接成它。拼接规则为只有一个字符串的末尾和另一个字符串的开头相等才能拼接,且合并的字母只算一次,如’ab’和’ba’合并后为’aba’,’ac’和’bc’不能合并。
样例
输入样例1
5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd
输出样例1
2
4
1
6
4
算法
(暴力枚举) $O(n)$
我们只需要判断有多少个长度为2的连续子序列就好了
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
inline void solve()
{
cin>>n;
string str;
cin>>str;
unordered_set<string> s;
for(int i=0;i<str.size()-1;i++){
s.insert(str.substr(i, 2));
}
cout<<s.size()<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}