最長子序列

求最長子序列，滿足和是一個數(shù)的倍數(shù)。
題目鏈接

#include<bits/stdc++.h> #define ll long long #define N 100005 int inf = 0x3f3f3f3f; using namespace std; ll n, k, a[N]; int main (){ cin >> n >> k; //N個數(shù)，所求序列和是K的倍數(shù) for(int i = 1; i <= n; i++){ //讀入數(shù)據(jù) cin >> a[i];}int ans = 0; //答案 for(int i = 1; i <= n; i++){if(n - i + 1 < ans) //簡單的n方復(fù)雜度不行，在這里加個判斷break; //如果后面的序列長度小于ans，就直接退出。 ll sum = 0;for(int j = i; j <= n; j++){ sum += a[j]; if(sum % k == 0){ans = max(ans, j - i + 1);}}}cout << ans <<endl;return 0; }

最短子序列

求大與等于m的最短連續(xù)子序列

給出n個數(shù)，然后給一個數(shù)m，找出長度最短的連續(xù)子系列，其總和大于等于m。 n和m為正整數(shù)且n小于100 000，m小于100 000 000 若干組測試樣例，處理到文件結(jié)束,注意無解情況輸出0 第一行輸入m,m。接下來一行有n個數(shù)。 input 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5 output 2 3

尺取法

#include<bits/stdc++.h> #define ll long long #define N 100005 int inf = 0x3f3f3f3f; using namespace std; ll n, m, a[N], sum[N]; int main (){while(cin >> n >> m){a[0] = sum[0] = 0;for(int i = 1; i <= n; i++){cin >> a[i];sum[i] =sum[i-1] + a[i]; //讀入并計(jì)算sum[i] sum為遞增序列}int ans = n + 1;for(int i = 1; i <= n; i++){int t = lower_bound(sum + 1 + i, sum + 1 + n, m + sum[i - 1]) - sum;if(t <= n)ans = min(ans, t - i + 1);} if (ans == n + 1) //無解 ans = 0; cout << ans <<endl; } return 0; } #include<bits/stdc++.h> #define ll long long #define N 100005 int inf = 0x3f3f3f3f; using namespace std; ll n, m, a[N], sum[N]; int main (){while(cin >> n >> m){a[0] = sum[0] = 0;for(int i = 1; i <= n; i++){cin >> a[i];sum[i] =sum[i-1] + a[i]; //讀入并計(jì)算sum[i] }int ans = n + 1;int s = 0, e = 1;while(sum[e] - sum[s] < m){e ++;}while(e <= n){ // while(sum[e] - sum[s] < m && e <= n) { //要加上 e <= n，費(fèi)則會 runtime error // e ++; // }while(sum[e] - sum[s] >= m){ //更新最小序列 s ++;}ans = min(ans, e - s + 1);e ++; //枚舉下一個數(shù) s ++;}if (ans == n + 1) //無解ans = 0; cout << ans <<endl; } return 0; } #include<bits/stdc++.h> #define ll long long #define N 100005 int inf = 0x3f3f3f3f; using namespace std; ll n, m, a[N], sum[N]; int main (){while(cin >> n >> m){for(int i = 1; i <= n; i++){cin >> a[i];}int ans = n + 1;int s = 1, e = 1;ll sum = 0;while(1){while(sum < m && e <= n){sum += a[e++];}if(sum < m)break;ans = min(ans, e - s);sum -= a[s++];}if (ans == n + 1) //無解ans = 0; cout << ans <<endl; } return 0; }

總結(jié)

以上是生活随笔為你收集整理的子序列问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。