题解：CF570C Replacement

OIerJiang_1017 · 2024-12-25 14:13:31 · 题解

CF570C 题目传送门

题目大意

给定一个包含小写英文字母和句点符号的字符串 s，其中句点符号用 . 表示。定义替换操作如下：在字符串 s 中找到子字符串 ..，即两个连续的句点，选择第一个出现的子字符串并将其替换为 .。如果字符串 s 中没有连续的两个句点，则不发生任何操作。定义 f(s) 为使字符串中不再有任何连续句号所需的最小替换次数。您需要处理 m 个查询，第 i 个查询的结果是将字符串 s 中位置为 x_i 的字符赋值为 c_i。每次操作完成后，您需要计算并输出 f(s) 的值。

解决思路

分类讨论是个好东西：

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

代码展示

#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;
}