P1885 Moo

题目描述

奶牛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”

………

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

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

现在的问题是：给出一个整数N (1 <= N <= 10^9)，问第N个字符是字母‘m’还是‘o’?

输入输出格式

输入格式：

一个整数N。

输出格式：

一个字符，m或者o

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

样例解释：

由题目所知：字符串S(0)是moo, 现在要求第11个字符，显然字符串S(0)不够长；

同样S(1)的长度是10，也不够长；S(2)的长度是25，够长了，S(2)的第11个字符是m，所以答案就输出m。

思路：分治。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n;

int l,r,mid;

int f[];

void dfs(int k){

    if(k==){

        if(n==)    cout<<"m";

        else cout<<"o";

        return ;

    }

    else if(n>f[k-]&&n<=f[k-]+k+){

        if(n==f[k-]+)    cout<<"m";

        else cout<<"o";

        return ;

    }

    else if(n<=f[k-])    dfs(k-);

    else if(n>f[k-]+k+){

        n-=f[k-]+k+;

        dfs(k-);

    }

}

int main(){

    scanf("%d",&n);

    f[]=;

    for(int i=;i<=;i++){

        f[i]=f[i-]+f[i-]++i;

        if(f[i]>n){

            dfs(i);

            break;

        }

    }

}

巴特西

洛谷 P1885 Moo

P1885 Moo

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章