哞哞哞~
题解看不懂 , 这道题好像要用 倍增 算法 , 求解释思路(或者不按题解也可) , 谢谢 ~ #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:36 编辑
从 p*2+l+3<=n看出 p*2+l+3 是计算字符串总长度
得出 p的含义：首尾那对字符串的长度
剩下 l+3，3是一个初始值，由每一轮比较都进行 l+1 操作，猜测 l 与 S 中的 k 相等
去掉首尾，单独观察 S 的中间部分，S: mooooS: mooo , S 比 S 中间部分字符串相差 1 个字符
若将中间部分长度减去初始值 3 ，那剩余的字符数就是 k值，即 l 的值。（中间部分 字符数 = m +(k+2)个o，即字符数=k+3）
至此，符号含义已解出。
通过while的迭代，将 S 扩大到能够包含到第 n 个字符为止。
设 S 首尾相同的那对字符串为 Q
S 的结构可写为 （Q）moo...oo（Q）
if(n>l+3+p)n-=(p+l+3)
判断 n 是否取在尾部Q的范围内，若为是，则可以直接减去前面的 Q+moo...oo 部分
因为 S 的尾部Q，即与 S 完全相同，完全可以在 S 中找到答案。故重新迭代，找到 S 进行判断。
若 n 并不在尾部Q位置取得，那么必定处在中间部分moo...oo处。（因为若处在首部Q内，之前的while循环中，只迭代到 S 就能满足条件，到不了 S 所必要的长度）
将 n 减去 首部Q 的长度，若为1，则是字符m，否则要处在中间部分，又不是首字母，那必定为字符o。
（S可理解为 Q 是空字符串 ，中间部分为 moo） 风车呼呼呼 发表于 2022-7-12 00:01
从 p*2+l+3
懂了 谢谢
页:
[1]