欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ZOJ 1633 Big-String

程序员文章站 2024-03-18 22:12:46
...
Big String

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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^__^".
Your task is to find out the n-th character of this infinite string.


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了。不可原谅!ZOJ 1633 Big-String

相关标签: 紫书