ZOJ 1633 Big-String
We will construct an infinitely long string from two short strings: A = "^__^" (four characters), and B = "T.T" (three characters). Repeat the following steps:
- Concatenate A after B to obtain a new string C. For example, if A = "^__^" and B = "T.T", then C = BA = "T.T^__^".
- Let A = B, B = C -- as the example above A = "T.T", B = "T.T^__^".
Input
The input contains multiple test cases, each contains only one integer N (1 <= N <= 2^63 - 1). Proceed to the end of file.
Output
For each test case, print one character on each line, which is the N-th (index begins with 1) character of this infinite string.
Sample Input
1 2 4 8
Sample Output
T . ^ T
Author: CHENG, Long
Source: Zhejiang University Local Contest 2003
题意概括:有a, b两个字符串,每次将a字符串置于b字符串之后,形成c字符串;然后将b字符串赋给a字符串,将c字符串赋给b字符串。反复如此。求第n个字符是什么。
解题思路:因为此题是一道规律题,所以先从分治的角度考虑,简化该问题。
1. 此题与斐波那契数列有异曲同工的地方。斐波那契数列是一个数是由此数之前的两个数的和所构成;而此题的c串是由ab两个串为基础的斐波那契串。因此可以用n减去小于n的最大的斐波那契数列——反复循环,当n的值小于或等于最初的c串的长度时,此时n在c串中的值就是第n个字符。
AC代码:
#include<stdio.h>
#define LEN 88
int main(void)
{
long long int n, f[LEN];
int i, j;
char str[8] = "T.T^__^";
f[0] = 7;
f[1] = 10;
for(i = 2; i < LEN; i ++)
{
f[i] = f[i - 1] + f[i - 2];
}
while(scanf("%lld", &n) != EOF) //此题第一次错误为整体思路有误。此处为第二次错误,即忘记了long long应该用lld。
{
while(n > 7)
{
int j = 0;
while(j < LEN && f[j] < n)
{
j ++;
}
n -= f[j - 1];
}
printf("%c\n", str[n - 1]);
}
return 0;
}
错误原因:
1. 思路有误:一开始总想着模拟整个c串,然后求出第n个字符。但是由于n的最大为2^63-1,所以很显然,数组开不了这么大。然后晕菜到就不知道该怎么办了。因此此种类型有规律的题一定要想办法对题目进行化简,通过分治法使大问题变成小问题,即可解决。
2. 粗心有误。将n定义为long long后忘记改scanf中的%lld了。不可原谅!