Jscpcp L. collecting diamonds (thinking)

2022 Jiangsu Collegiate Programming Contest

Solution

1. Note that if the operation deletes B Is the current ABC Group cannot continue , And only delete B To change the following ABC Group parity .
2. So you should try to delete each group once B, And try to ensure that you delete B Delete as many as possible before AC.
3. So a variable is used to store the previous deletion several times B, It can be used to calculate how many can be deleted AC

Code

The nature of the problem is not difficult , The hard part is how to achieve ..

const int N = 2e5 + 5;
pii a[N];

int main()
{
    
	string s; cin >> s;
	int n = sz(s);
	s = " " + s;

	int t = 0;
	for (int i = 1; i <= n; i++)
	{
    
		if (s[i] != 'B') continue;
		int l = i, r = i;
		while (l - 1 >= 1 && r + 1 <= n && s[l - 1] == 'A' && s[r + 1] == 'C')
			l--, r++;
		if(l != r) a[++t] = {
     i & 1, i - l };
	}

	int ans = 0, cnt = 0;// How many times has it been deleted  B
	for (int i = 1; i <= t; i++)
		if (cnt == 0)
		{
    
			if (a[i].ft) ans++, cnt++;
			else
			{
    
				if (a[i].sd == 1) ans++;
				else ans += 2, cnt++;
			}
		}
		else
		{
    
			ans += min(a[i].sd, (a[i].ft == 0) + cnt + 1);
			cnt++;
		}
	
	cout << ans << endl;


	return 0;
}