洛谷P1885 Moo —— 搜索

This way

题意

奶牛 Bessie 最近在学习字符串操作它用如下的规则逐一的构造出新的字符串

$S(0)=$ moo

$S(1)=S(0)+$ m $+$ ooo $+S(0)=$ moo $+$ m $+$ ooo $+$ moo $=$ moomooomoo

$S(2)=S(1)+$ m $+$ oooo $+S(1)=$ moomooomoo $+$ m $+$ oooo $+$ moomooomoo $=$ moomooomoomoooomoomooomoo

$\dots$

Bessie 就这样产生字符串直到最后产生的那个字符串长度不小于读入的整数 $N$ 才停止。

通过上面观察可以发现第 $k$ 个字符串是由第 $k-1$ 个字符串 $+$ m $+$ $(k+2$ 个 $o)+$ 第 $k-1$ 个字符串连接起来的。

现在的问题是给出一个整数 $N(1\le N\le 10^9)$问第 $N$ 个字符是字母 m 还是 o

题解

    可以发现的是它其实就像一个分治的模型。对于每一层来说都可以分为左中右结构左右是下一层的东西中间才是这层的主体。
    那么我们想要找到N这个位置是什么其实也就是看N是落在哪一层的。然后在对于那一层看N是否是第一个位置即可。

于是我们dfs搜索就是去定位到对应的层而已可以先预处理len表示每一层的字符数量

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 35;
ll len[N];
int mx;
void dfs(int x,int now){
    while(len[now-1]>=x)now--;
    if(len[now-1]+1==x)
        printf("m\n");
    else if(len[now-1]+now+2>=x)
        printf("o\n");
    else
        dfs(x-len[now-1]-now-2,now-1);
}
int main()
{
    int n;
    scanf("%d",&n);
    len[1]=3;
    for(int i=1;len[i]<n;i++)
        len[i+1]=len[i]*2+i+3,mx=i+1;
    dfs(n,mx);
}