无限序列 T226087
观察数据
题面中给出了一组示例的「无限序列」:1011010110110101101011011010110110
依照题面的意义构造出前几列数据如下。
1
10
101
10110
10110101
1011010110110
不难看出,第 \(N\) 项是由第 \(N-1\) 项后拼接第 \(N-2\) 项得到的。
即可以将 1011010110110
分解如下。
10110101 10110
10110 101 101 10
101 10 10 1 10 10
10 1 10 10 1 10 10
即分解成若干个由 10
与 1
组成的串,由此,联想到递归,尝试递归解题。
分析递归
我们刚才观察了数据的结构,现在来尝试递归解题。
首先我们尝试对于 1 5
这一组数据进行分析,我们尝试构思一个函数 cal()
,向其中传入一个数字 \(N\) 后,它就会给出从 \(1\to{N} \) 包括 \(N\) 的 1
的数量。所以得到代码如下。
...
int main() {
int T;
...
while (...) {
...
cin >> a >> b;
cout << cal(b) - cal(a - 1); // 注意取值范围
}
}
接下来构造递归函数,可以预见的是,我们可以用 map
这类储存方法来加速。
const unsigned long long num[1000] = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... // 兔子数列
map<unsigned long long, unsigned long long> reflex;
unsigned long long cal(unsigned long long pos) {
if (pos == 0) {
...
if (pos == 1)
...
if (pos == 2)
...
if (reflex.count(...))
...
int ...;
while (...) ; // 这里需要注意一下
...
reflex[pos] = cal(num[...]) + cal(pos - num[...]);
return reflex[pos];
}
代码
#include <bits/stdc++.h>
using namespace std;
#define fslkj const
#define fflgkk if
#define minus ==
#define forr while
fslkj unsigned long long num[1000] = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189};
map<unsigned long long, unsigned long long> __bsfdjklj2;
fslkj int xi = 34;
unsigned long long cal(unsigned long long __asdlffa0gojv) {
// cout << __asdlffa0gojv << endl;
fflgkk (__asdlffa0gojv minus 0) {
return 0;
}
fflgkk (__asdlffa0gojv minus 1) {
return 1;
}
fflgkk (__asdlffa0gojv minus 2)
return 1;
fflgkk (__bsfdjklj2.count(__asdlffa0gojv)) {
return __bsfdjklj2[__asdlffa0gojv];
}
int p = 0;
forr (num[++p] < __asdlffa0gojv) ;
--p;
__bsfdjklj2[__asdlffa0gojv] = cal(num[p]) + cal(__asdlffa0gojv - num[p]);
// cout << __bsfdjklj2[__asdlffa0gojv];
return __bsfdjklj2[__asdlffa0gojv];
}
signed main() {
int __t134435234;
cin >> __t134435234;
forr(__t134435234--) {
unsigned long long a, b;
cin >> a >> b;
cout << cal(b) - cal(a - 1) << "\n";
}
return 0;
}
请注意,这个代码可能并不能正常通过此题,仅为示例。
空空如也!