題目鏈接：點擊這里

題目大意：
給出一個長度為 $n$ 的序列 $a$ ，有 $q$ 次詢問，每次詢問含有一組 $l,r$ 求 $a_l$ 到 $a_r$ 中是否能找出三條邊使之構成三角形

題目分析：
我們先從暴力出發，我們發現：
對于一次詢問的 $l,r$ 我們將 $a_l$ 到 $a_r$ 進行從小到大的排序，然后逐個枚舉相鄰三個的元素，如果滿足 $a[i]+a[i+1]>a[i+2]$ 則可以構成三角形，如果 $a[i]$ 和 $a[i+1]$ 都不能和 $a[i+2]$ 構成三角形那么其他的數更沒辦法滿足兩邊之和大于 $a[i+2]$ 。但是其復雜度是 $O(nlogn)$ 是難以支持 $q$ 次查詢的
我們繼續考慮優化 $a[i]+a[i+1]>a[i+2]$ ，我們發現當讓不等號為等號時有 $a[i]+a[i+1]=a[i+2]$ 此式子為斐波那契數列的遞推式，而我們知道斐波那契數列在第 $46$ 項的時候就爆 $int$ 了，題目給出$a[i]$ 的范圍是 $a[i]\le 1e9$ ，因此當 $r?l+1\ge 45$ 即區間長度大于 $45$ 時我們可以直接判斷其可以找到三個元素使之作為三角形的三邊，對于 $r?l+1<45$ 時用之前那個 $nlogn$ 的方法暴力處理即可，其時間復雜度為 $O(q45log45)$

具體細節見代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<set> #include<map> #define ll long long #define inf 0x3f3f3f3f using namespace std; int read() {int res = 0,flag = 1;char ch = getchar();while(ch<'0' || ch>'9'){if(ch == '-') flag = -1;ch = getchar();}while(ch>='0' && ch<='9'){res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';ch = getchar();}return res*flag; } const int maxn = 1e5+5; const int mod = 1e9+7; const double pi = acos(-1); const double eps = 1e-8; int n,q,a[maxn],tmp[maxn]; int main() {n = read();q = read();for(int i = 1;i <= n;i++)a[i] = read();while(q--){int l = read(),r = read();int len = r-l+1;if(len >= 45) {puts("clynb");continue;}if(len <= 2) {puts("clycdd");continue;}for(int i = 0;i < len;i++)tmp[i] = a[l+i];sort(tmp,tmp+len);bool flag = false;for(int i = 2;i < len;i++){if(tmp[i-2]+tmp[i-1] > tmp[i]){flag = true;break;}}if(flag) puts("clynb");else puts("clycdd");}return 0; }

總結

以上是生活随笔為你收集整理的Cly的三角形 （思维+斐波那契）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。