题目描述
blablabla
样例
/* */
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f;
const int MAX = 5e5+7;
int vis[MAX];
void solve()
/*算数开ll 存图用int*/
{
int n;
cin>>n;
string s;
cin>>s;
s = " "+s;
int ans = 0;
for(int i=1;i<=n;i++)
{
int l = i-1;
int ll = 0;
int lr = 0;
while(l>=1 && s[l]!=s[i])
{
ll++;
l--;
}
int r = i+1;
while(r<=n && s[r]!=s[i])
{
lr++;
r++;
}
ans += ll*lr + max((int)0,ll-1) + max((int)0,lr-1);
//1。当前这个在中间被两边的不同的包起来
//2。当前这个与前面一个连起来的前提下 然后前面的再与其连起来(当队尾)
//3。当前这个与后面一个连起来的前提下 然后后面的再与其接上(当对头)
}
cout<<ans;
}/*算数开ll 存图用int*/
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
cout.tie(0);
//cout<<fixed<<setprecision(2);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla