题解 P1885 【Moo】

粉刷匠 · 2020-05-19 09:01:59 · 题解

暴力枚举会超时，通过找规律给出一个简单易懂的递归算法

#include<bits/stdc++.h>
#define intn long long
using namespace std;
int a[50];
int b[4]={0,1,0,0};
int getn(int l)
{
    for(int i=0;i<=30;i++)
    {
        if(l<=a[i])
        return i;
    }
}

int dfs(int l)
{
    if(l<=3)//当l小于3时可以得出结果
    {
        return b[l];
    } 
    int n=getn(l);//得到n
        //将s（n）分为三部分，s（n-1）,moo...,s(n-1)
    if(l==a[n-1]+1)
    return 1;
    if(l>a[n-1]+1&&l<=a[n-1]+1+n+2)
    return 0;
    return dfs(l-a[n-1]-n-3);
    //到第三部分时递归找在s（n-1）的第l-a[n-1]-n-3个字符。
}
main(void)
{
    int l;
    cin>>l;
    a[0]=3;
    for(int i=1;i<=27;i++)//预处理n和l的关系，根据数据范围可以枚举1到27。
    {
        a[i]=i+3+2*a[i-1]; //增长规律
    }
    if(dfs(l)==1)//寻找第l个字符
    {
        printf("m");
    }
    else
    {
        printf("o");
    }
}