Codeforces Round #316 (Div. 2) C. Replacement

原题: http://codeforces.com/contest/570/problem/C


题目大意: 给一个string s, s有小写字母和’.’组成. 做m个query替换操作, 对于每个操作都要进行固定的处理, 这个处理是把s中的连续两个’.’. 替换成1个, 一次替换消除一对’.’ 问对每个query, 需要几次替换.


分析: 开始的时候以为能爆过….结果暴到test case7 过不去了…后来只能分情况讨论. 一上来先算下原始的s需要几次替换, 假设原始string s 需要n次替换.  这时, 对于m个query, 有两种情况可以改变n的值.

  1. 替换的字符是’.’ 但是当前字符不是, 有以下两种情况:
    1. 如果当前字符的前边是’.’, n++
    2. 如果当前字符的后边是’.’, n++
  2. 替换的字符是字母, 但是当前字符是’.’, 有以下两种情况:
    1. 如果当前字符的前边是’.’, n–
    2. 如果当前字符的后边是’.’, n–

最后别忘了把字符替换一下.