[已解决]哞哞哞~

柿子饼同学

题解看不懂 , 这道题好像要用 倍增 算法 , 求解释思路(或者不按题解也可) , 谢谢 ~

#include<stdio.h>
bool f=0;
int main(){
    int n;
    scanf("%d",&n);
    while(!f){
        int l=0,p=0;
        while(p*2+l+3<=n)p=p*2+l+3,l++;
        if(n>l+3+p)n-=(p+l+3);
        else{
            if(n-p==1)puts("m");
            else puts("o");
            f=1;
        }
    }
    return 0;
}

输入输出 :

11

m

谢谢回答

最佳答案

月排行榜 / 总排行榜

风车呼呼呼

2022-7-12 00:01:52

从 p*2+l+3<=n  看出 p*2+l+3 是计算字符串总长度
得出 p的含义：首尾那对字符串的长度

剩下 l+3，3是一个初始值，由每一轮比较都进行 l+1 操作，猜测 l 与 S[k] 中的 k 相等
去掉首尾，单独观察 S[k] 的中间部分，S[2]: moooo  S[1]: mooo , S[k+1] 比 S[k] 中间部分字符串相差 1 个字符
若将中间部分长度减去初始值 3 ，那剩余的字符数就是 k值，即 l 的值。（中间部分 字符数 = m +(k+2)个o，即字符数=k+3）
至此，符号含义已解出。


通过while的迭代，将 S[k] 扩大到能够包含到第 n 个字符为止。
设 S[k] 首尾相同的那对字符串为 Q
S[k] 的结构可写为 （Q）moo...oo（Q）

if(n>l+3+p)n-=(p+l+3)

判断 n 是否取在尾部Q的范围内，若为是，则可以直接减去前面的 Q+moo...oo 部分
因为 S[k] 的尾部Q，即与 S[k-1] 完全相同，完全可以在 S[k-1] 中找到答案。故重新迭代，找到 S[k-1] 进行判断。

若 n 并不在尾部Q位置取得，那么必定处在中间部分moo...oo处。（因为若处在首部Q内，之前的while循环中，只迭代到 S[k-1] 就能满足条件，到不了 S[k] 所必要的长度）
将 n 减去 首部Q 的长度，若为1，则是字符m，否则要处在中间部分，又不是首字母，那必定为字符o。
（S[0]可理解为 Q 是空字符串 ，中间部分为 moo）

跳转到最佳答案楼层

风车呼呼呼

从 p*2+l+3<=n  看出 p*2+l+3 是计算字符串总长度
得出 p的含义：首尾那对字符串的长度

剩下 l+3，3是一个初始值，由每一轮比较都进行 l+1 操作，猜测 l 与 S[k] 中的 k 相等
去掉首尾，单独观察 S[k] 的中间部分，S[2]: moooo  S[1]: mooo , S[k+1] 比 S[k] 中间部分字符串相差 1 个字符
若将中间部分长度减去初始值 3 ，那剩余的字符数就是 k值，即 l 的值。（中间部分 字符数 = m +(k+2)个o，即字符数=k+3）
至此，符号含义已解出。


通过while的迭代，将 S[k] 扩大到能够包含到第 n 个字符为止。
设 S[k] 首尾相同的那对字符串为 Q
S[k] 的结构可写为 （Q）moo...oo（Q）

if(n>l+3+p)n-=(p+l+3)

判断 n 是否取在尾部Q的范围内，若为是，则可以直接减去前面的 Q+moo...oo 部分
因为 S[k] 的尾部Q，即与 S[k-1] 完全相同，完全可以在 S[k-1] 中找到答案。故重新迭代，找到 S[k-1] 进行判断。

若 n 并不在尾部Q位置取得，那么必定处在中间部分moo...oo处。（因为若处在首部Q内，之前的while循环中，只迭代到 S[k-1] 就能满足条件，到不了 S[k] 所必要的长度）
将 n 减去 首部Q 的长度，若为1，则是字符m，否则要处在中间部分，又不是首字母，那必定为字符o。
（S[0]可理解为 Q 是空字符串 ，中间部分为 moo）

柿子饼同学

风车呼呼呼 发表于 2022-7-12 00:01
从 p*2+l+3

懂了 谢谢