当前位置：首页 > article >正文

E. Alternating String

article 2024/9/27 5:23:53

这道题就是前缀和的变化, 现在做起来比较简单, 打这场的时候差了点时间就做出来了

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200010;

int od[N][30], ev[N][30];
int n;

void init()
{
	for(int i = 0; i <= n; i ++ )
	{
		for(int j = 1; j <= 26; j ++ )
		{
			od[i][j] = 0;
			ev[i][j] = 0;
		}
	}
}

void solve()
{
	string s;
	cin >> n;
	init();
	cin >> s;
	
	for(int i = 1; i <= n; i ++ )
	{
		if(i % 2 == 0) ev[i][s[i - 1] - 'a' + 1] = 1;
		else od[i][s[i - 1] - 'a' + 1] = 1;
		
		for(int j = 1; j <= 26; j ++ )
		{
			od[i][j] += od[i - 1][j];
			ev[i][j] += ev[i - 1][j];
		}
		
	}

	if(n % 2 == 0)
	{
		int maxx1 = 0, maxx2 = 0;
		
		for(int i = 1; i <= 26; i ++ )
		{
			maxx1 = max(maxx1, od[n][i]);
			maxx2 = max(maxx2, ev[n][i]);
		}
		
		cout << n - maxx1 - maxx2 << endl;
		return;
	}
	
	int maxx = 0;
	for(int i = 1; i <= n; i ++ )
	{
		int maxx1 = 0, maxx2 = 0;
		for(int j = 1; j <= 26; j ++ )
		{
			maxx1 = max(maxx1, od[i - 1][j] + ev[n][j] - ev[i][j]);
			maxx2 = max(maxx2, ev[i - 1][j] + od[n][j] - od[i][j]);
		}
		maxx = max(maxx, maxx1 + maxx2);
	}
	cout << n - maxx << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while (T -- )
	{
		solve();
	}
}

查看全文

http://www.kler.cn/news/321325.html