70分,TLE最后三个点的看过来
  • 板块P3938 斐波那契
  • 楼主TAMIYA
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/25 17:03
  • 上次更新2024/7/25 18:30:29
查看原帖
70分,TLE最后三个点的看过来
1252040
TAMIYA楼主2024/7/25 17:03

太神奇了,把二分函数直接写进主函数就可以过了,如果单独声明一个二分函数会TLE后三个点```cpp

include<bits/stdc++.h>

using namespace std;

long long fibo[70];

int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); fibo[1] = 1, fibo[2] = 1; for(int i = 3;i <= 59;i ++){ fibo[i] =fibo[i - 1] + fibo[i - 2]; } int n; cin >> n; for(int i = 0;i < n;i ++){ long long a, b; cin >> a >> b;

	while(a != b){
		if(a < b) swap(a, b);

// cout << maxx << endl; int l = 2, r = 59; while(l <= r){ int mid = (l + r) / 2; if(fibo[mid] >= a){ r = mid - 1; } else l = mid + 1; } a -= fibo[l - 1]; } cout << a << endl; } return 0; }

以下是TLE后三个点的写法
```cpp
# include<bits/stdc++.h>

using namespace std;

long long fibo[70];


int bisect(int x){
	int l = 1, r = 59;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(fibo[mid] >= x) r = mid - 1;
		else l = mid + 1;
	}
	return l;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	fibo[1] = 1, fibo[2] = 1;
    for(int i = 3;i <= 59;i ++){
    	fibo[i]  =fibo[i - 1] + fibo[i - 2];
	}
	int n;
	cin >> n;
	for(int i = 0;i < n;i ++){
		long long a, b;
		cin >> a >> b;
		
		while(a != b){
			if(a < b) swap(a, b);
			int maxx = bisect(a);
//			cout << maxx << endl;
			a -= fibo[maxx - 1];
		}
		cout << a << endl;
	}
    return 0;
}
2024/7/25 17:03
加载中...