洛谷【P1885】Moo

我对分治的理解：https://www.cnblogs.com/AKMer/p/9728574.html

题目传送门：https://www.luogu.org/problemnew/show/P1885

这题跟[[洛谷【P3612】USACO17JAN Secret Cow Code秘密奶牛码差不太多，都是分治字符串然后乱搞一波就行了。

时间复杂度：\(O(logn)\)

空间复杂度：\(O(1)\)

代码如下：

#include <cstdio>
using namespace std;

int n;
char s[4]={' ','m','o','o'};

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

char find(int id) {
    if(id<4)return s[id];
    int tmp=3,pos=0;
    while(tmp<id)tmp=tmp*2+4+pos,pos++;
    int mid=tmp-pos-3;mid/=2;
    if(id<=mid)return find(mid);
    if(id<=mid+pos+3) {
        if(id!=mid+1)return 'o';
        else return 'm';
    }
    return find(id-(mid+pos+3));
}

int main() {
    n=read();
    printf("%c",find(n));
    return 0;
}

洛谷【P1885】Moo

原文：https://www.cnblogs.com/AKMer/p/9734788.html