【题解】【分治】——Secret Cow Code S

[USACO17JAN] Secret Cow Code S

通往洛谷的传送门

题目描述

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

给定一个字符串，对字符串进行一次操作（每一次正确的操作，最后一个字符都会成为新的第一个字符），然后把操作后的字符串放到操作前的字符串的后面。也就是说，给定一个初始字符串，之后的每一步都会增加当前字符串的长度。

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

输入格式

第一行输入一个字符串。该字符串包含最多 $30$ 个大写字母，数据保证 $N\le 10^{18}$。

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

输出格式

请输出从初始字符串生成的无限字符串中的下标为 $N$ 的字符。第一个字符的下标是 $N=1$。

输入输出样例

输入 #1

COW 8

输出 #1

C

提示

In this example, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC

12345678

1.思路解析

    看到这道题，第一种思路就是直接使用字符串模拟。但是嘛……

    这里也把代码附上，供扩展思维。

#include<bits/stdc++.h>
using namespace std;
string str,s;
long long n;
void expand()
{
	if(str.size()>=n)
	    return;
	s="";
	for(int i=0;i<str.size()-1;i++)
		s+=str[i];
	str=str+str[str.size()-1]+s;
	expand();
}
int main()
{
    cin>>str>>n;
    expand();
    cout<<str[n-1];
	return 0;
}

    我们可以来研究研究一个长度为len的字符串str，给其中的字符标号，如下：
    1,2,3,4,5,6......len
    将它翻转之后，就变成了这样：
    1,2,3,4,5,···，len,len+1,len+2···2*len。
    根据翻转规则，str[len]=str[len+1]，其余每一个编号为i的字符，也就是str[i]都可以与str[i+len+1]相等，即str[i]=str[i+len+1]。

    那我们可不可以通过逆推，找到位置为n的字符在前半段的位置呢？当然可以。最后，知道我们将规模缩减到不用操作（即原字符串的长度）就可以了（递归边界）。将大规模问题分解成小规模问题，再逐一解决，这不就是递归（分治）吗？

    例如，上面的输入样例COW 8。将它操作到长度$>=8$时，对应字符的关系如下（对应的的字符用相同的数字代替）：
    1 2 3 4 5 6 6 1 2 3 4 5
    找到位置为8的字符：1，它在也一定在后半段（如果在前半段就直接返回了）。前面对应的字符的位置为1，在原字符串里面了，可以直接输出。如果不在原字符串里面，还需要递归继续求。读者可以手动模拟一下：COW 11。

    在实现代码时，还应当注意字符串的边界问题的处理。还有变量要开long long而不是int（自己去看题目 ）。

2.AC代码

#include<bits/stdc++.h>
using namespace std;
string s;
int len;//给定字符串的长度,这个可以不用开long long
void expand(long long n)//将求最后字符串的第n位转化成求给定字符串的第n位
{
	if(n<=len)//递推边界,n在给定字符串范围内就输出
	{
		cout<<s[n-1];
		return;
	}
	long long i=len;//i代表最后字符串的前一次操作的长度
	while((i<<1)<n)i<<=1;//将i不断扩大,每操作一次扩大两倍,直到求出最后字符串的长度
	n=n-(i+1);//求出映射到前面字符串的位置
	if(n==0)n=i;//特殊判断
	expand(n);//递归处理
}
int main()
{
	long long n;
    cin>>s>>n;
    len=s.length();
    expand(n);
	return 0;
}

喜欢就订阅此专辑吧！

【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。

欢迎扫码关注蓝胖子编程教育