logoChat01.ai

ограничение по времени на тест2 секунды ограничени...

생성일: 2026년 4월 21일

답변에 사용된 모델 GPT-5.3 by Chat01

질문

ограничение по времени на тест2 секунды
ограничение по памяти на тест512 мегабайт
Есть таблица из 2×n
клеток. Каждая ячейка таблицы раскрашена в красный или черный цвет. Вы хотите перекрасить некоторые ячейки этой таблицы таким образом, чтобы существовал хотя бы один способ разбить все ячейки на n
пар так, чтобы выполнялись условия:

ячейки в каждой паре одного цвета;
ячейки в каждой паре являются соседними по стороне.
Какое минимальное количество ячеек необходимо для этого перекрасить?

Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t
(1≤t≤104
) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число n
(1≤n≤2⋅105
).

Вторая и третья строки каждого набора входных данных описывают цвета ячеек. Каждая строка состоит из букв «R» и «B» и имеет длину n
.

Дополнительные ограничения на входные данные:

сумма n
по всем наборам входных данных не превосходит 2⋅105
.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество ячеек, которые нужно перекрасить.

Пример
Входные данныеСкопировать
5
1
R
B
2
BR
BR
3
RBR
BRB
4
RRBB
BBRB
5
RBRBR
BBBRB
Выходные данныеСкопировать
1
0
3
1
4
Примечание
Рассмотрим 3
-й пример. Одним из вариантов является окраска всех ячеек в один цвет, что требует перекраски 3
-х ячеек.

В 4
-м примере одним из вариантов допустимой перекраски является

RRBB
BBRR

реши на с++

사고

Thought for 16s

답변

Да. Здесь достаточно обычного DP по столбцам.

Идея

Разбиение доски 2 × n на соседние по стороне пары — это просто замощение доминошками:

  • либо вертикальная доминошка в одном столбце,
  • либо две горизонтальные доминошки, покрывающие два соседних столбца.

Для каждой доминошки нужно, чтобы обе клетки стали одного цвета.
Минимальная цена для одной пары:

  • 0, если цвета уже совпадают,
  • 1, если разные.

Стоимости

Пусть строки — a и b.

1. Вертикальная пара в столбце i

Состоит из a[i] и b[i].

text
vert(i) = (a[i] != b[i] ? 1 : 0)

2. Две горизонтальные пары на столбцах i-1 и i

Нужно сделать одинаковыми:

  • a[i-1] и a[i],
  • b[i-1] и b[i].

Цена:

text
hor(i-1, i) = (a[i-1] != a[i] ? 1 : 0) + (b[i-1] != b[i] ? 1 : 0)

DP

dp[i] — минимальное число перекрашиваний для первых i столбцов.

Переходы:

  1. Поставить вертикальную доминошку в столбце i:
text
dp[i] = dp[i-1] + vert(i)
  1. Поставить две горизонтальные доминошки на столбцах i-1 и i:
text
dp[i] = dp[i-2] + hor(i-1, i)

Итого:

text
dp[i] = min(dp[i-1] + vert(i),
            dp[i-2] + hor(i-1, i))

Почему это правильно

Любое корректное разбиение первых i столбцов заканчивается ровно одним из двух способов:

  • либо последним столбцом, покрытым вертикальной парой;
  • либо двумя последними столбцами, покрытыми двумя горизонтальными парами.

Других вариантов для замощения полосы 2 × i нет.
Значит, оптимальный ответ для i столбцов получается из оптимального ответа на меньшем префиксе плюс стоимость последнего шага. Это и есть DP выше.

Сложность

На один тест: O(n)
По всем тестам: O(sum n)
Память: O(n), можно даже O(1).

Код на C++

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

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string a, b;
        cin >> a >> b;

        vector<int> dp(n + 1, (int)1e9);
        dp[0] = 0;

        for (int i = 1; i <= n; ++i) {
            // Вертикальная доминошка в столбце i
            int vert = (a[i - 1] != b[i - 1]);
            dp[i] = min(dp[i], dp[i - 1] + vert);

            // Две горизонтальные доминошки на столбцах i-1 и i
            if (i >= 2) {
                int hor = (a[i - 2] != a[i - 1]) + (b[i - 2] != b[i - 1]);
                dp[i] = min(dp[i], dp[i - 2] + hor);
            }
        }

        cout << dp[n] << '\n';
    }

    return 0;
}

Если хочешь, я могу еще написать короткое объяснение в стиле Codeforces editorial.

이 Q&A 공유하기