自动搬运

查看原文

来自洛谷，原作者为

	issue_is_fw 我又从轮回的尽头回来了呢,泽田纲吉

搬运于2025-08-24 21:50:45，当前版本为作者最后更新于2020-03-09 16:02:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言:在这道题目卡了很久，所以我想把自己的理解说出来，希望能帮到你们。管理大大让我过吧，(●ˇ∀ˇ●)自认为表达地比一些题解要好。

先看样例

$COW->COWWCO->COWWCOOCOWWC$

我们把这三个字符串编号为$1,2,3$

现在我们要求第8位，假如我们已经知道在3串，能否逆推出在第2串中的位置呢?如果能，似乎问题就迎刃而解了,因为2逆推到1也是一个相同的子问题。

题目的古怪要求复制要先复制最后一个字符，再复制前缀，我们姑且先直接复制前缀.

$COW->COWCOW->COWCOWCOWCOW$

现在求3串的8位置，3串长L,逆推回2串即为$8-L/2$位置

但我们复制的时候是先复制最后一个字符,所以要多减一为$8-1-L/2$

特别的,如果求的n刚好是先复制原串的那个位置,特殊处理，具体看代码

#include <bits/stdc++.h>
using namespace std;
string s;
long long n,num,i;
int main()
{
	//代码部分借鉴1楼 
	cin>>s>>n;
	num=s.length(); 
	while(num<n)
	{
		i=num;
		while(n>i)	i*=2;//求出当前刚好包括n位置的串长 
		i=i/2;//得到当前串的一半长 
	//	if(n==i+1)	n=i;特殊处理，假如这里n位置是i+1
	//那么经过下面这步操作后，变成了0，那我们下面对0特判 
		n-=(i+1); 
		if(n==0)	n=i;
	}
	cout<<s[n-1];
}