AT_abc394_c 题解

getchar_unlocked · 2025-02-23 22:43:24 · 题解

题目传送门

思路

首先不难想到遍历整个字符串，把所有的 \texttt{WA} 替换成 \texttt{AC}。然而这样遍历一遍，原字符串中可能会存在新的 \texttt{WA}。反复遍历最多会有 N 次，时间复杂度 \mathcal{O}(N^2)，不可行。

所以倒着遍历，这样就会覆盖掉新的 \texttt{WA}。时间复杂度 \mathcal{O}(N)。

AC CODE

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

int main(){
    string s;cin>>s;
    for(int i=s.size()-1;i>=1;--i)
        if(s[i]=='A'&&s[i-1]=='W')
            s[i]='C',s[i-1]='A';
    cout<<s<<"\n";
    return 0;
}