【题解】[ARC113C] String Invasion

题面传送门

解决思路

题目大意是给你一个字符串 \(s\) ，定义一次操作为对于长度为 \(3\) 的一个子段，满足 \(s_i=s_{i+1}\ne s_{i+2}\)，则可以将 \(s_{i+2}\) 变为 \(s_i\) 。问最多可以操作多少次。

首先可以对照样例三找出规律。对于样例三 anerroroccurred，最优的操作方法是：

先 \(2\) 后变成 anerroroccurrrr（改 r）
再 \(5\) 次变成 anerroroccccccc（改 c）
再 \(9\) 次变成 anerrrrrrrrrrrr（改 r）

可以发现，最优策略是从后往前找，每次找到可以操作的，就把它后面的所有字母都变成一样的。

假设字符串长度为 \(n\)，并且 \(s_i=s_{i+1}\)，则可以操作的次数是 \(n-(i+2)-(sum_{s_i}-2)\)，其中，\(n-(i+2)\) 算出之后有几个字符。\(sum_{s_i}\) 表示：当前字符串、当前操作位置及之后位置 有多少个字符为 \(s_i\) 。因为重复的字符不能操作，所以要减掉，又因为第 \(s_i,s_{i+1}\) 位不算，所以减 \(2\)。

一次修改后，之后的字符都变相同了，所以将 \(sum\) 清空，同时赋 \(sum_{s_i}\) 为 \(n-i\)。

AC Code

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

#define TIE cin.tie(0),cout.tie(0)

#define int long long

using namespace std;

string s;

int sum[200],ans;

signed main(){

	IOS;TIE;

	cin>>s;

	sum[s[s.size()-1]]++;

	sum[s[s.size()-2]]++;

	for(int i=s.size()-3;i>=0;i--){

		sum[s[i]]++;

		if(s[i]==s[i+1]&&s[i+1]!=s[i+2]){

			ans+=s.size()-i-sum[s[i]];

			for(int j='a';j<='z';j++) sum[j]=0;

			sum[s[i]]=s.size()-i;

		}

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

【题解】[ARC113C] String Invasion

题面传送门

解决思路

AC Code

最新文章

热门文章