logoChat01.ai

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

Erstellt am: 21. April 2026

Beantwortet mit GPT-5.3 von Chat01

Frage

ограничение по времени на тест2 секунды
ограничение по памяти на тест512 мегабайт
Назовем строку t
чередующейся, если для любого i
от 1
до n−1
выполняется ti≠ti+1
.

Дана строка s
, которая состоит только из букв «a» и/или «b». Вы можете не более одного раза совершить с ней следующую операцию:

выбрать подстроку slsl+1…sr
, состоящую хотя бы из одного символа;
после выбора подстроки можно изменить в ней все буквы, то есть заменить все «a» на «b» и все «b» на «a» (вы можете это сделать, но не обязаны);
перевернуть выбранную подстроку, то есть превратить строку s1s2…sl−1slsl+1…srsr+1…sn
в s1s2…sl−1srsr−1…slsr+1…sn
.
Обратите внимание, что вы не обязаны выполнять второй пункт операции. Например, для строки s=
«ababbab» после одной операции можно получить «abababa», выбрав в операции подстроку s5s6s7
и выполнив второй пункт операции, или «bababab», выбрав подстроку s1s2s3s4
и не выполнив второй пункт операции. Однако третий пункт операции выполняется всегда.

Можно ли получить из строки s
чередующуюся строку?

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

В единственной строке каждого набора входных данных содержится строка s
(2≤|s|≤2⋅105
). Строка состоит только из строчных латинских букв «a» и/или «b».

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

сумма длин строк по всем наборам входных данных не превосходит 2⋅105
.
Выходные данные
Для каждого набора входных данных выведите одно из двух:

YES, если возможно получить чередующуюся строку из s
;
NO в противном случае.
Каждую букву можно выводить в любом регистре.

Пример
Входные данныеСкопировать
8
abbaba
aaaaa
bababba
ab
abbaabba
bbb
ababa
aabb
Выходные данныеСкопировать
YES
NO
YES
YES
NO
YES
YES
YES
Примечание
В первом примере можно выбрать подстроку s3s4s5s6
и не выполнять второй шаг, тогда получим строку «ababab».

В третьем примере можно выбрать подстроку s1s2s3s4s5
и выполнить второй шаг, тогда получим строку «abababa».

В четвертом примере строка уже чередующаяся.

В шестом примере можно выбрать подстроку s2
и выполнить второй шаг, тогда получим строку «bab»

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e15 + 7;
const int C = 380;
const int B = 64;

void solve() {
string s;
cin >> s;
int cnt2 = 0, cnt3 = 0, cnt = 0, p = 0;
for (int i = 0; i < s.size() - 1; i++) {
if (s[i] == s[i + 1]) {
p++;
} else {
if (p == 1) cnt2++;
if (p == 2) cnt3++;
if (p > 2) cnt++;
p = 0;
}
}
if (p == 1) cnt2++;
if (p == 2) cnt3++;
if (p > 2) cnt++;

//cout << cnt2 << cnt3 << cnt;
if (cnt2 + cnt3 + cnt == 1 && cnt2 == 1) {
cout << "YES\n";
return;
}

if (cnt2 + cnt3 + cnt == 2 && cnt2 == 2) {
cout << "YES\n";
return;
}

if (cnt2 + cnt3 + cnt == 1 && cnt3 == 1) {
cout << "YES\n";
return;
}

if (cnt2 + cnt3 + cnt == 0) {
cout << "YES\n";
return;
}

cout << "NO\n";
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
cin >> tests;
while (tests--) {
solve();
}

return 0;

}
что не так

Gedanke

Сейчас разберу именно логику условия и покажу контрпример к твоему критерию, а потом дам короткое правильное решение с доказуемым условием.

Thought for 18s

Python

python
from itertools import product

def reachable(s):
    n=len(s)
    alts=[''.join('a' if (i+j)%2==0 else 'b' for i in range(n)) for j in [0,1]]
    if s in alts: return True
    for l in range(n):
        for r in range(l,n):
            sub=s[l:r+1]
            for flip in [0,1]:
                t=''.join(('b' if c=='a' else 'a') if flip else c for c in sub)[::-1]
                u=s[:l]+t+s[r+1:]
                if u in alts:
                    return True
    return False

def code(s):
    cnt2 = cnt3 = cnt = p = 0
    for i in range(len(s)-1):
        if s[i]==s[i+1]:
            p+=1
        else:
            if p==1: cnt2+=1
            if p==2: cnt3+=1
            if p>2: cnt+=1
            p=0
    if p==1: cnt2+=1
    if p==2: cnt3+=1
    if p>2: cnt+=1
    if cnt2+cnt3+cnt == 1 and cnt2 == 1: return True
    if cnt2+cnt3+cnt == 2 and cnt2 == 2: return True
    if cnt2+cnt3+cnt == 1 and cnt3 == 1: return True
    if cnt2+cnt3+cnt == 0: return True
    return False

bad=[]
for n in range(2,11):
    for tup in product('ab', repeat=n):
        s=''.join(tup)
        r=reachable(s)
        c=code(s)
        if r!=c:
            bad.append((s,r,c))
            break
    if bad: break
len(bad), bad[:20]


(0, [])

Gedanke

Verifying the logic behind the solution

It looks like there isn't an obvious counterexample up to 10, so the code is likely correct. The user's code might be fine algorithmically, with some minor style issues like unnecessary constants or certain formatting choices. I’ll explain that the "bad edges <= 2" criterion holds and provide a simple proof. To achieve an alternating string, we just need to flip at most two bad edges, which I’ll show by constructing a working example for clarity.

Refining the alternating string proof

To fix two bad edges:

  • If they're consecutive (run length 3), flip the middle character.
  • If non-consecutive, the string will look like alternating characters with two segments where one character repeats. I can reverse the segment between those bad edges to fix the string—either flipping or not, depending on the situation. A simpler proof could show how the "bad edges <= 2" is sufficient for achieving the alternating pattern.

Thought for 3m 25s

Antwort

По логике у тебя тут ошибки нет — решение корректное.

Я даже проверил его полным перебором всех строк маленькой длины: контрпримеров нет.
Твой код по сути проверяет условие:

можно тогда и только тогда, когда число позиций i, для которых s[i] == s[i+1], не больше 2.

То есть твой разбор через cnt2 / cnt3 / cnt — это просто более сложная форма той же самой идеи.

Почему это так

Обозначим “плохую” позицию i, если

cpp
s[i] == s[i+1]

У чередующейся строки таких позиций должно быть 0.

Теперь посмотрим на операцию:

  • внутри выбранной подстроки мы делаем reverse,
  • возможно ещё и инвертируем все буквы.

Важное наблюдение

Для любых двух соседних символов внутри выбранной подстроки факт

  • равны они или нет

не меняется:

  • при перевороте порядок пары просто меняется;
  • при инверсии a↔b равенство/неравенство тоже сохраняется.

Значит, измениться могут только две границы подстроки:

  • между l-1 и l
  • между r и r+1

То есть количество плохих позиций можно уменьшить максимум на 2.

Следовательно:

  • если плохих позиций было 3 или больше, получить 0 уже невозможно;
  • если их 0, 1 или 2 — это всегда можно исправить одной операцией.

Что делает твой код

Ты считаешь блоки одинаковых соседей:

  • cnt2 — блок длины 1 плохая пара (aa или bb)
  • cnt3 — блок длины 2 (aaa или bbb)
  • cnt — длиннее

И разрешаешь только случаи:

  • нет плохих пар,
  • одна плохая пара,
  • две раздельные плохие пары,
  • две подряд плохие пары.

Это и есть ровно случаи, когда общее число плохих пар <= 2.

То есть ответ на твой вопрос

“Что не так?” — по сути ничего.
Код верный, просто его можно сильно упростить.

Более короткая версия

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

void solve() {
    string s;
    cin >> s;

    int bad = 0;
    for (int i = 0; i + 1 < (int)s.size(); i++) {
        if (s[i] == s[i + 1]) bad++;
    }

    cout << (bad <= 2 ? "YES\n" : "NO\n");
}

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

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Что я бы ещё убрал у тебя

Это не ошибки, но лишнее:

  • #define int long long — не нужно
  • srand(time(0)); — вообще не используется
  • константы N, C, B — тоже не используются

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

Diesen Q&A teilen