【ZOJ-1633】解题报告（字符串递推，二分查找）

原始题目

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 \le N \le 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="T.T" ， C=BA="T.T__" ，再令C=B, B=A，重复这种操作，问如此构成的字符串第n个字符是什么。

解题思路

  • \(dp[i]\) 表示第i个字符串由多少个字符构成，已知\(dp[0]=4,dp[1]=3,dp[2]=7\)，根据递推规则可知\(dp[i+1]=dp[i]+dp[i-1]\)
  • 折半查找第一个比n大的dp[i]，则第i串里的第n位与第i-1串里的第n-dp[i-1]（可以保证这一项大于零）位对应字符相同。递归操作直至n<7。从"T.T__"寻找就可以了

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
using namespace std;
typedef long long ll;
ll a[95];  //保存字符串的长度
int main()
{
    string C = "T.T^__^";
    a[0] = 4;
    a[1] = 3;
    int i;
    for(i = 2; i < 90; i++)
        a[i] = a[i-1] + a[i-2];
    ll n;
    while(cin >> n)
    {
        while(n > 7)
        {
            int pos = lower_bound(a, a+89, n) - a;
            n -= a[pos-1];
        }
        cout << C[n-1] << endl;
    }
    return 0;
}

收获与反思

  • 二分查找与递推的结合