Codeforces Round #449 (Div. 2) C. Nephren gives a riddle 二叉树、回溯、分类讨论

My Solution

题意：用一个前缀s1，中间部分s2，后缀s3，fi = s1 + fi-1 + s2 + fi-1 + s3来构造字符串 fi，q个询问(n, k)，每次询问第n个字符串的第k个字符。

二叉树、回溯、分类讨论

这样构造出的字符串相当于一颗二叉树，从叶子开始回溯，回溯的时候根据k的情况，判断是从左子树向根回溯，还是从右子树向根回溯。

有点想主席树的一些操作，先预处理出fi的长度，然后每次对于k和当前fi的情况，回溯到i-1，

回溯的时候 如果是左边 k -= 34（前缀），如果是右边 k -= 34（前缀） + 32（中间），然后用新的k和新的n（n-1）进行进行计算。

具体的分类讨论情况，见源码。

时间复杂度 O(n*q)

空间复杂度 O(64)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 8;

string s, s0, s1, s2, s3, s4;
LL f[64];
int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 3;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);


    s0 = "What are you doing at the end of the world? Are you busy? Will you save us?";
    s1 = "What are you doing while sending "";
    s2 = ""? Are you busy? Will you send "";
    s3 = ""?";
    //cout << s0.size() << " " << s1.size() << " " << s2.size() << " " << s3.size() << endl;

    int i, maxi;
    f[0] = 75;
    for(i = 1; i < 64; i++){ f[i] = f[i-1]*2 + 34 + 32 + 2; if(f[i] > (LL)1e18){
            maxi = i;
            break;
        }
    }
    //cout << s0[31]<<endl; LL q, n, k; cin >> q;
    while(q--){
        cin >> n >> k;

        while(n && n--){
            n++;
            if(n <= maxi && f[n] < k){
                cout << "."; k = 0; break; } if(n - 1 > maxi){
                if(k > 34) k -= 34;
                else{
                    cout << s1[k-1];
                    k = 0;
                    break;
                }
            }
            else{
                if(34 + f[n-1] < k){
                    if(34 + f[n-1] + 32 + f[n-1] < k){
                        k -= 34 + f[n-1] + 32 + f[n-1];
                        cout << s3[k-1]; k = 0; break; } else{ k -= 34 + f[n-1]; if(k > 32) k -= 32;
                        else{
                            cout << s2[k-1];
                            k = 0;
                            break;
                        }
                    }

                }
                else{
                    //cout << "??" << n << " " << k << "??" ; if(k > 34) k -= 34;
                    else{
                        cout << s1[k-1];
                        k = 0;
                        break;
                    }
                }
            }
            n--;

        }
         //cout << n << " " << k << endl;
         if(n == 0 && k != 0){
            //cout << "??";
            if(k <= f[0]) cout << s0[k-1];
            else cout << ".";
         }
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx