1554-D, *1800

Problem - 1554D - Codeforces

문제

• 다음 조건을 만족시키는 길이가 $n(1\leq n \leq 10^{5})$인 문자열$s$을 출력하라
• $s$의 부분문자열의 개수는 항상 홀수개여야 한다 ~ !
  ex) uuuauu
  ㅇ u -5개
  ㅇ uu - 3개
  ㅇ uuu - 1개
  ㅇ au - 1개 ...

 

$O(n)$

Claim
다음과 같은 형태의 문자열을 생각하자
$$\begin{aligned}
\text{uu}&\text{lu}\\
\text{uuu}&\text{luu}\\
\text{uuuu}&\text{luuu}\\
\end{aligned}$$

이와 같은 규칙을 갖는 문자열은 조건 ! 을 만족한다

$\because$
오직 한번만 등장하는 문자를 포함하는(l 을 포함하는) 부분문자열의 개수는 항상 1개만 존재한다
따라서 u 만으로 이루어진 문자열의 개수만을 세어 조건이 만족되는지 확인한다

l 을 기준으로 왼쪽과 오른쪽에서 각각 어떤 부분문자열의 수를 셀 때
한쪽은 짝수, 다른한쪽은 홀수가 나오므로 그 부분문자열의 개수는 항상 홀수이다

예를 들어, $\text{uuuu}\text{luuu}$ 에서 부분문자열 $\text{uuu}$를 센다고 하면
l 왼쪽에는 2개, 오른쪽에는 1개가 나오게 되어 총 홀수개의 부분문자열이 존재한다□

 

Cor
다음과 같은 문자열도 조건을 만족시킨다
$$\begin{aligned}
\text{buu}&\text{lu}\\
\text{buuu}&\text{luu}\\
\text{buuuu}&\text{luuu}\\
\end{aligned}$$

$\because$
오직 한번만 등장하는 문자를 포함하는(b 또는 l을 포함하는) 부분문자열의 개수는 항상 1개이고
u 만으로 이루어진 부분문자열은 항상 홀수개임을 앞서 증명했다□

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        if(n==1){
            cout << 'u' << endl;
            continue;
        }
        loop(i, n/2) cout << 'u';
        cout << 'a';
        loop(i, n/2-1) cout << 'u';
        if(n%2) cout << 'b' << endl;
        else cout << endl;
    }
 
    return 0;
}cs

※ 항상 최대와 최소는 예외가 발생하지 않는지 확인해볼것!