Hướng dẫn giải

Mỗi thanh nam châm có cực trái và cực phải. Hai thanh liền kề đẩy nhau khi cực phải của thanh trước và cực trái của thanh sau cùng dấu, khi đó Donal không nối được và tạo thành nhóm mới. Đếm số nhóm bằng cách bắt đầu từ 1 và cộng thêm 1 mỗi khi hai thanh liền kề đẩy nhau.

Bài chỉ có một cách duyệt tự nhiên (một lần quét các cặp liền kề), nên chỉ viết 1 sub.

Sub 1: Duyệt các cặp liền kề — ~O(n)~

Với mỗi ~i~, so sánh ký tự thứ hai của thanh ~i~ (cực phải) với ký tự thứ nhất của thanh ~i+1~ (cực trái). Nếu bằng nhau thì hai cực cùng dấu, đẩy nhau, tăng số nhóm. Đạt 60/60 test.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<string> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];

    // Mỗi nam châm có 2 cực: s[i][0] là cực trái, s[i][1] là cực phải.
    // Hai nam châm liên kết với nhau khi cực phải của cái trước và cực trái của cái sau khác dấu.
    // Nếu cùng dấu thì đẩy nhau, tạo nhóm mới.
    int groups = 1;
    for (int i = 0; i + 1 < n; i++) {
        if (s[i][1] == s[i + 1][0]) groups++;
    }
    cout << groups << "\n";
    return 0;
}