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–

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

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int len = in.readInt();
        int m = in.readInt();
        char[] s = in.readLine().toCharArray();
        int res = process(s);
        for (int i = 0; i < m; i++) {
            int index = in.readInt() - 1;
            char c = in.readCharacter();
            if (c == '.' && s[index] != '.') {
                if (index > 0 && s[index - 1] == '.')
                    res++;
                if (index < s.length - 1 && s[index + 1] == '.')
                    res++;
            } else if (c != '.' & s[index] == '.') {
                if (index > 0 && s[index - 1] == '.')
                    res--;
                if (index < s.length - 1 && s[index + 1] == '.')
                    res--;
            }
            out.printLine(res);
            s[index] = c;
        }
    }

    private int process(char[] s) {
        int res = 0;
        for (int i = 1; i < s.length; i++) {
            if (s[i] == '.' && s[i - 1] == '.')
                res++;
        }
        return res;
    }