P3612 [USACO17JAN] Secret Cow Code S题解

题目

奶牛正在试验秘密代码，并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。

给定一个字符串，让后面的字符旋转一次（每一次正确的旋转，最后一个字符都会成为新的第一个字符）。也就是说，给定一个初始字符串，之后的每一步都会增加当前字符串的长度。

给定初始字符串和索引，请帮助奶牛计算无限字符串中位置N的字符。

第一行输入一个字符串。该字符串包含最多30个大写字母，数据保证N≤。

第二行输入N。请注意，数据可能很大，放进一个标准的32位整数可能不够，所以你可能要使用一个64位的整数类型（例如，在C/C++中是long long）。

请输出从初始字符串生成的无限字符串中的位置的字符。第一个字符是N=1。

输入输出样例

输入样例

COW 8

输出样例

C

解析

先看样例

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<iostream>
using namespace std;
string s;
long long n,num,i;
int main(){
	cin>>s>>n;
	num=s.length();//记录字符串的长度
	while(num<n){//当字符串长度小于n时进入循环
		i=num;
		while(n>i){//当n大于i时，不断的旋转，增加长度
			i*=2;
		}
		i/=2;//长度取一半
		n-=(i+1);
		if(n==0){//特殊处理
			n=i;
		}
	}
	cout<<s[n-1];//数组索引从0开始，所以为n-1
	return 0;
}