一、題目

1、題目描述

2、輸入輸出

2.1輸入

2.2輸出

3、原題鏈接

570C - Replacement

---

二、解題報告

1、思路分析

1、長為cnt的連續串的最小操作次數為cnt - 1

2、每次將一個非. 替換為. f要么增加1要么增加2?

只有前后都是 . 的時候會增加2

同理，當我們將一個 . 替換為非 . ，也只有減少1和減少2兩種情況，是對偶的

那么我們直接模擬即可

2、復雜度

時間復雜度： O(N + M)空間復雜度：O(N)

3、代碼詳解

??

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
const int inf = 1e9 + 7, P = 998244353;void solve() {int n, m;std::cin >> n >> m;std::string s;std::cin >> s;std::vector<int> a(n + 2);for (int i = 0; i < n; i ++ )if (s[i] == '.') a[i + 1] = 1;int f = 0, con = 0;for (int x : a)if (x) ++ con;else {if (con) f += con - 1;con = 0;}for (int i = 0, idx; i < m; i ++ ) {char c;std::cin >> idx >> c;int v = c == '.';if (v != a[idx]) {if (v) {++ f;f += a[idx - 1] && a[idx + 1];f -= !a[idx - 1] && !a[idx + 1];}else {-- f;f -= a[idx - 1] && a[idx + 1];f += !a[idx - 1] && !a[idx + 1];            }a[idx] = v;}std::cout << f << '\n';}
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}