题目

[USACO 21DEC.B] Lonely Photo

思路

include<bits/stdc++.h>

using namespace std;

define int long long

define N 500010

int n, m, i, j, k;
int l[N], r[N], ans;
char a[N];

signed main()
{
scanf("%d%s", &n, a+1);
for(i=1, k=0; i<=n; ++i)
if(a[i]a[i-1]) l[i]=0, ++k;
else l[i]=k, k=1;
for(i=n, k=0; i>=1; --i)
{
if(a[i]a[i+1]) r[i]=0, ++k;
else r[i]=k, k=1;
}
for(i=1; i<=n; ++i)
{
if(l[i]&&r[i]) ans+=l[i]*r[i];
if(l[i]>=2) ans+=l[i]-1;
if(r[i]>=2) ans+=r[i]-1;
}
printf("%lld", ans);
return 0;
}

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 500010
int n, m, i, j, k; 
int l[N], r[N], ans; 
char a[N]; 

signed main()
{
	scanf("%d%s", &n, a+1); 
	for(i=1, k=0; i<=n; ++i)
		if(a[i]==a[i-1]) l[i]=0, ++k; 
		else l[i]=k, k=1; 
	for(i=n, k=0; i>=1; --i)
	{
		if(a[i]==a[i+1]) r[i]=0, ++k; 
		else r[i]=k, k=1; 
	}
	for(i=1; i<=n; ++i)
	{
		if(l[i]&&r[i]) ans+=l[i]*r[i]; 
		if(l[i]>=2) ans+=l[i]-1; 
		if(r[i]>=2) ans+=r[i]-1; 
	}
	printf("%lld", ans); 
	return 0;
}