题意:给定一个字符串,里面有各种小写字母和’ . ' ,无论是什么字母,都是一样的,假设遇到' . . ' ,就要合并成一个' .',有m个询问,每次都在字符串某个位置上将原来的字符改成题目给的字符,问每次须要多少次合并次数。才使字符串没有‘ .. '
思路:最原始的想法,就是对于每一次询问,都遍历整个字符串。这样时间复杂度o(n*m),就高达10^10方,非常明显会tle。
换下思路,事实上每次询问所改变的字符都会保留到下一次。也就是下一次的次数就会受到上一次的影响,那么我仅仅要就算出第一次的合并次数,以下的都能够推出来
题目链接:http://codeforces.com/problemset/problem/570/C
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
char a[300005],b[10];
int main(void)
{
scanf("%d%d",&n,&m);
scanf("%s",a+1);
scanf("%d%s",&cnt,b);
a[cnt]=b[0];//处理第一次
int ret,ans=0,flag;
for(int i=1; i<=n; i++)
{
ret=0;
flag=0;
while(a[i]=='.')//假设一个子序列全都是'.',假设有ret个'.',那么合并次数就是ret-1;
{
i++;
ret++;
flag=1;
}
if(flag) ans+=ret-1;
}
printf("%d\n",ans);
for(int i=1; i<m; i++)//处理剩余的m-1次,每一次的ans均由上一次推出
{ scanf("%d%s",&cnt,b);
char ch=a[cnt];
a[cnt]=b[0];
if(b[0]=='.'&&ch!='.')//假设这一次由字母变成'.',检查前后是否有'.',有一个的话合并次数就要+1
{
if(a[cnt-1]=='.') ans++;
if(a[cnt+1]=='.') ans++;
}
else if(b[0]!='.'&&ch=='.')//由字母变成'.'
{
if(a[cnt-1]=='.') ans--;
if(a[cnt+1]=='.') ans--;
}
printf("%d\n",ans);
}
return 0;
}