2479: 【作】【普及-】【P3612】Secret Cow Code S
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：4
题目描述
奶牛正在试验秘密代码，并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。
给定一个字符串，让后面的字符旋转一次（每一次正确的旋转，最后一个字符都会成为新的第一个字符）。也就是说，给定一个初始字符串，之后的每一步都会增加当前字符串的长度。
给定初始字符串和索引，请帮助奶牛计算无限字符串中位置 的字符。
输入
第一行输入一个字符串。该字符串包含最多 个大写字母，数据保证 。
第二行输入 。请注意，数据可能很大，放进一个标准的 位整数可能不够，所以你可能要使用一个 位的整数类型（例如，在 C/C++ 中是 long long）。 输出
请输出从初始字符串生成的无限字符串中的位置的字符。第一个字符是 .。
样例输入 复制
COW 8样例输出 复制
C提示
In this example, the initial string COW expands as follows:
COW -> COWWCO -> COWWCOOCOWWC
分析：
因为是将原串的最后一个字符放到第一个来，其余字符全部后移一位，
所以在后一半的第i位就是前一半的第i−1位，如果是后一半的第1位，那么就是前一半的第len位。
我们每次分治可以将串长减少一半，所以只需要logn的时间就可以将询问的位数减小至最开始的原串长度以内，
就可以直接出结果了。
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL n;
int len;
char s[35];
/**
因为是将原串的最后一个字符放到第一个来，其余字符全部后移一位，
所以在后一半的第i位就是前一半的第i−1位，
如果是后一半的第1位，那么就是前一半的第len位。
我们每次分治可以将串长减少一半，
所以只需要logn的时间就可以将询问的位数减小至最开始的原串长度以内，
就可以直接出结果了。
**/
char find(LL id) {
if (id <= len) return s[id]; //如果到初始串内了就直接返回答案
LL tmp = len;
while ((tmp << 1) < id) tmp <<= 1; //tmp就是前半部分的长度
LL new_id = id - tmp - 1;
if (!new_id) new_id = tmp; //new_id是id位在前半部的位置
return find(new_id); //递归去找
}
int main() {
scanf("%s%lld", s + 1, & n);
len = strlen(s + 1);
printf("%c", find(n)); //找第n位
return 0;
}