题解：P1885 Moo

dH_Hb · 2024-08-29 20:38:13 · 题解

很考验思维的一道题。

60分

可以发现，这道题的答案只有两种 m 和 o，直接输出 m 就可以得60分。

80分

先算出最后产生的那个字符串 S(i) 中的 i，最后循环枚举字符串。

#include<bits/stdc++.h>
using namespace std;
int n;
int chang=3,i; //S(i)的长度为chang 
string s1="moo",s2="moo"; //s1为当前字符串，s2为 m+oo 那部分 
int main(){

    cin>>n;
    while(chang<n){
        i++;
        chang=chang*2+3+i; //找规律，很简单就不说了 
    }
    for(int j=1;j<=i;j++){
        s2+="o";
        s1=s1+s2+s1;
    }
    cout<<s1[n-1]; //字符串默认从0坐标开始 

    return 0;
}

但是你会发现，有两个点会 MLE，这可能因为 s1 的长度过长。

100分

可以发现 1 \le N \le 10^9，而且每两个字符串的差很大，由此可以得出 S(i) 中的 i 很小，所以我们可以模拟 i。

#include<bits/stdc++.h>
using namespace std;
int n;
int chang[10000]={3},i; //S(i)的长度为chang
string s1="moomooomoomoooomoomooomoo";
int main(){

    cin>>n;
    while(chang[i]<n){
        i++;
        chang[i]=chang[i-1]*2+3+i; //找规律，很简单就不说了 
    }
    while(i>1){
        if(n==chang[i-1]+1){ //中间的m 
            cout<<"m";
            return 0;
        }else if(n>chang[i-1]+1&&n<chang[i]-chang[i-1]+1){ //中间的oooo部分 
            cout<<"o";
            return 0; 
        }else{
            if(!(n<=chang[i-1])){ //!的比较级大于<=所以要加括号 
                n=n-chang[i-1]-3-i; //核心代码 
            }
            i--;
        }
    }
    cout<<s1[n-1];

    return 0;
}

好了，到这里就结束了，希望能帮到你，谢谢。