Fibonacci

Fibonacci

思路

• 可以发现， 连续的三个字母不全相同， 所以 | s | \(\le\) 3 * |t|

• |S| 枚举一下即可（好像能证明但是不会），1e6 左右

• 所以只要暴力算出来一段 S， 然后枚举起点开始匹配即可

40 分

• \(O(|S| * |s|)\) 枚举即可

100 分

• 使用类似倍增的方法
  • st[i][j] 表示从 t[i] 出发， 在 s[j] 中找子序列， 能匹配到 t[st[i][j]]
  • 因为 s[j] = s[j-1] + s[j-2]， 所以 st[i][j] = st[i][j-1] + st[i+st[i][j-1]][j-2]
• 然后考虑怎么枚举起点
  • s[j] 可以拆成 s[j-1] + s[j-2]
  • s[j-1] 可以继续拆， 直到 j = 1 或 0
  • 每次删掉最头上的一个 j = 1 或 0 即可
  • 然后用 st 对剩下的进行匹配

代码

40 分

• 考场代码

#include <bits/stdc++.h> 
#define int long long
using namespace std;
const int N = 1e5 + 10;

string s1, s2, s;
string t;

signed main(){
//	freopen("1.in", "r", stdin);

	cin >> t;
	s1 = "b";
	s2 = "a";
	for(int i = 2; i; i++){
		s = s2 + s1;
		s1 = s2, s2 = s;
		if(s.size() > (int)6e4){
			break;
		}
	}	
	int mini = (int)1e18, cnt = 0;
	for(int i = 0; i < (int)s.size() - (int)t.size() + 1; i++){
		int step = 0, k = 0;
		for(int j = i; j < (int)s.size(); j++){
			step++; cnt++;
			if(s[j] == t[k]){
				k++;
			}
			if(k == (int)t.size()){
				break;
			}
		}
		if(k == (int)t.size()){
			mini = min(mini, step);
		}
	}
	cout << mini << "\n";
}

100 分

#include <bits/stdc++.h> 
#define int long long
using namespace std;
const int INF = 1e18;
const int N = 1.5e5 + 10;

int n;
int len, p, mini;
int fibo[35], st[N][35];
char t[N];
vector <int> que;

void Calc(int x){
	if(p > n){
		return;
	}
	if(x <= 1 || p + st[p][x] <= n){	// x <= 1 表示递归找到底了
		p += st[p][x];	// 该匹配哪一位了
		len += fibo[x];	// |s|
		return;
	}
	Calc(x - 1), Calc(x - 2);
}

void Solve(){	// 用 st 算挨个在 que 中找子序列的 |s|
	len = 0;	// |s|
	p = 1;	// 该去匹配 t 的第 p 位了（下标从 1 开始）
	for(int i = que.size() - 1; i >= 0; i--){
		Calc(que[i]);
	}
	if(p > n){
		mini = min(mini, len);
	}
}

signed main(){
//	freopen("1.in", "r", stdin);

	cin >> (t + 1);
	n = strlen(t + 1);
	for(int i = 1; i <= n; i++){
        // 初始化： 第一位和 s_0 / s_1 能匹配上
		if(t[i] == 'a'){
			st[i][1] = 1;
		}else{
			st[i][0] = 1;
		}
	}
	
	int up = 31;
	mini = 3 * n;
	for(int i = n; i >= 1; i--){
		for(int j = 2; j <= up; j++){
            // 类似倍增的操作
			st[i][j] = st[i][j - 1] + st[i + st[i][j - 1]][j - 2];
		}
	}
	
	fibo[0] = fibo[1] = 1;
	for(int i = 2; i <= up; i++){
        // 递推斐波那契序列， 用于计算 |s|
		fibo[i] = fibo[i - 1] + fibo[i - 2];
	}
	
	que.push_back(up);
	while(!que.empty()){
		Solve();
		while(que.back() >= 2){
			int ba = que.back();
			que.pop_back();
			que.push_back(ba - 2);
			que.push_back(ba - 1);
		}
		que.pop_back();	// 每次删掉一个最小单位（和 for(int i = 1; i <= n; i++) 没多大区别）
	}
	cout << mini << "\n";
}