题解：CF570C Replacement

CF570C 题目传送门

题目大意

给定一个包含小写英文字母和句点符号的字符串

s

，其中句点符号用 . 表示。定义替换操作如下：在字符串

s

中找到子字符串 ..，即两个连续的句点，选择第一个出现的子字符串并将其替换为 .。如果字符串

s

中没有连续的两个句点，则不发生任何操作。定义

f(s)

为使字符串中不再有任何连续句号所需的最小替换次数。您需要处理

m

个查询，第

i

个查询的结果是将字符串

s

中位置为

x_i

的字符赋值为

c_i

。每次操作完成后，您需要计算并输出

f(s)

的值。

解决思路

分类讨论是个好东西：

如果要被替换的位于 $x$ $x$ 的字符是 .，且要被字母替换：
- 如果前面也是点，因为他变成了字母所以要少一种情况；
- 如果后面也是点，因为他变成了字母所以要少一种情况；
如果要被替换的位于 $x$ $x$ 的字符是字母，且要被 . 替换：
- 如果前面也是点，因为他变成了点所以要多一种情况；
- 如果后面也是点，因为他变成了点所以要多一种情况。

代码展示

CPP

#include <iostream>
#define ll long long
//不开long long见祖宗 
using namespace std;

ll n, m;
string s;

int main()
{
	scanf("%lld%lld", &n, &m);
	cin >> s;//建议scanf,更快
	ll cnt = 0, l = s.size();//l记录字符串的长度
	for(int i = 0; i < l; i++)
		if(s[i] == '.' && s[i + 1] == '.')
			cnt++;//cnt记录两个连续的点的个数
	for(int i = 1; i <= m; i++)
	{
		ll x;
		char c;
		scanf("%lld%c", &x, &c);
		x--;//x--是因为字符串下标从0开始 
		if(s[x] == '.' && c >= 'a' && c <= 'z')
		{
			if(s[x-1] == '.' && x > 0) cnt--;
			//如果前面也是点，因为他变成了字母所以要少一种情况
			if(s[x+1] == '.' && x < l) cnt--;
			//如果后面也是点，因为他变成了字母所以要少一种情况
		}
		else if(c == '.' && s[x] >= 'a' && s[x] <= 'z')
		{
			if(s[x-1] == '.' && x > 0) cnt++;
			//如果前面也是点，因为他变成了点所以要多一种情况
			if(s[x+1] == '.' && x < l) cnt++;
			//如果后面也是点，因为他变成了点所以要多一种情况
		}
		s[x] = c;//将位置x换成指定字母
		printf("%lld\n", cnt);//建议printf,更快
	}
	return 0;
}

题解：CF570C Replacement

文章操作

CF570C 题目传送门

题目大意

解决思路

代码展示

相关推荐

评论

题解：CF570C Replacement