DRAGON (중상, p. 306)

문제#

어떻게 풀었나?#

segment tree문제 풀듯이 query에 해당하는 구간값을 계속 재귀호출 하면서 그 구간 값에 해당하는 영역에서는 정답 문자열을 return하도록 했다.

문제 난이도는 ‘중’으로 잡혀있는데, ‘중상’ 정도가 아닐까 싶다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
//[s,e]
string f(int gen, ll s, const string & str, int qs, int qe) {
    if(gen==N) {
        if(qs>=s) return str.substr(qs-s,qe-qs+1);
        else return str.substr(0,qe-s+1);
    }
    string ret;
    for(int i = 0; i < str.size(); i++) {
        if(str[i]=='X') {
            ll e = s + 3*(1LL<<(N-gen))-3;
            if(!(e<qs || qe<s)) ret += f(gen+1,s,"X+YF",qs,qe);
            s = e+1;
        }
        else if(str[i]=='Y') {
            ll e = s + 3*(1LL<<(N-gen))-3;
            if(!(e<qs || qe<s)) ret += f(gen+1,s,"FX-Y",qs,qe);
            s = e+1;
        }
        else {
            ll e = s;
            if(!(e<qs || qe<s)) ret += string(1,str[i]);
            s = e+1;
        }
        if(s>qe) break;
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        ll n,p,l; cin >> n >> p >> l;
        N = n;
        printf("%s\n", f(0,0,"FX",p-1,p-1+l-1).c_str());
    }
    return 0;
}