==S1.序列问题==
一定要分清子串和子序列的区别
一.最长上升子序列
给定一个长度为 N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
1.暴力做法,复杂度$N^2$
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 1010
int n,arr[MAX],f[MAX],ans=0;
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i];
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++){
if(arr[j]<arr[i]) f[i]=max(f[i],f[j]+1);
}
}
for(int i=0;i<n;i++) ans=max(ans,f[i]);
cout<<ans<<endl;
}
2.二分优化版 N*logN
#include<iostream>
#include<algorithm>
using namespace std;
int arr[100010], f[100010], n, len = 0;
//二分左开右闭写法,范围永远:“左闭右开”,检查条件永远:“mid大于等于或大于arr[i],r=mid,l=mid+1
//左开右闭最后的l和r都是一样的,结果是[left,left)
//f数组存储的是对应每个长度的子序列的末尾值,比如f[4]=5,长度为4的子序列末尾那个数为5
//数学推理:随着长度增加,子序列末尾值也应该递增
//这里其实有一种贪心的思路,我们要求的是一个数,比他小而且最接近这个数的子序列长度末尾值,并且更新
//我们肯定希望对应长度的子序列末尾值尽量小点,这样能加进子序列的数更多,
//arr[i]<=q[r],arr[i]是新发现的序列,q[r]是原来存储的序列,所以可以更新
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
f[0] = -1e9;//里面数可能有负的,为0,yxc那种全闭写法就没事
for (int i = 0; i < n; i++) {
int l = 0, r = len + 1;//左开右闭
while (l < r) {
int mid = (l + r) >> 1;
if (f[mid] >= arr[i]) r = mid;
else l = mid + 1;
}
len = max(len, r);
//q[r-1]<=arr[i]<=q[r], arr[i]可以加在长度为r-1的后面,变成并更新长度r
//因为arr[i]<=q[r],所以可以把arr[i]更新给q[r]了,顺便更新下len长度
f[r] = arr[i];
}
cout << len << endl;
}
//yxc的全闭写法
#include<iostream>
#include<algorithm>
using namespace std;
int arr[100010], f[100010], n, len = 0;
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
for (int i = 0; i < n; i++) {
int l = 0, r = len;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (f[mid] < arr[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
f[r + 1] = arr[i];
}
cout << len << endl;
}
二.最长公共子序列897
给定两个长度分别为 N和 M的字符串 A和 B,求既是 A的子序列又是 B的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N和 M。
第二行包含一个长度为 N的字符串,表示字符串 A。
第三行包含一个长度为 M的字符串,表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N,M≤1000
输入样例:
4 5
acbd
abedc
输出样例:
3
#include<iostream>
#include<algorithm>
using namespace std;
//f[i][j]是截止a数组前i个,b数组前j个,公共序列的最大值
//如果正好当下的i和j相同,那么f[i][j]就可以更新成f[i - 1][j - 1] + 1了
//如果只取其中一个i或者j,因为末尾的公共数不一定就是i或者j,
//所以i和j的全都不选,就是只选i或者只选j的子序列了,包括在这俩种情况里面
int n, m, f[1010][1010];
char a[1010], b[1010];
int main() {
cin >> n >> m;
cin >> a + 1 >> b + 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = max(f[i][j - 1], f[i - 1][j]);//不一定末尾的数就是i或者j
if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
//两个正好想同才能更新成f[i - 1][j - 1] + 1
}
}
cout << f[n][m] << endl;
}
三.最短编辑问题902
给定两个字符串 A和 B,现在要将 A经过若干操作变为 B可进行的操作有:
1. 删除–将字符串 A中的某个字符删除。
2. 插入–在字符串 A的某个位置插入某个字符。
3. 替换–将字符串 A中的某个字符替换为另一个字符。
现在请你求出,将 A变为 B至少需要进行多少次操作。
输入格式
第一行包含整数 n表示字符串A的长度。
第二行包含一个长度为 n的字符串 A。
第三行包含整数m表示字符串 B的长度。
第四行包含一个长度为 m的字符串 B。
字符串中均只包含大小写字母。
输出格式
输出一个整数,表示最少操作次数。
数据范围
1≤n,m≤1000
输入样例:
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例:
4
#include<iostream>
#include<algorithm>
using namespace std;
//f数组存储的是,操作数列的前i个变成目标数列的前j个,的步数最小值
//有三种情况,f[i][j]如果是删,那么说明前i-1个和j个相同了已经,加个a[i]多余了,所以f[i - 1][j] + 1
//如果是加,相当于反向删个b[i],前i个和j-1个相同了已经,来了个不懂事的b[i],a被迫再加个数,所以f[i][j - 1] + 1
//如果是替换,有两种可能,一是a[i]和b[i]已经相同了啊,不用替换,如果不同,需要再加一步,替换
//找到这个过程的最小值
#define MAX 1010
int n, m;
char a[MAX], b[MAX];
int f[MAX][MAX];
int main() {
cin >> n >> a + 1;
cin >> m >> b + 1;
//初始值,把前i个和前0个组合的最小值,只能是把前i个都删掉/加上
for (int i = 0; i <= n; i++) f[i][0] = i;
for (int i = 0; i <= m; i++) f[0][i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
}
cout << f[n][m] << endl;
}
还有个899,复杂点的
==四.滑动窗口问题==
再举个大概例子吧,比如求最小值,现在窗口里是3,6,7了,来了个4,那么tt–,一直减到只剩一个3,然后q[++tt] = i;
i - k + 1就是窗口末位滑到哪了,那个q是存下标的,试了下,q数组不请空,直接拿去用求最大值也是ac的
#include<iostream>
using namespace std;
//讲一下大概思路,先讲求一个滑动窗口内的最小值吧,最大值照着推就ok了
//比如吧,有一行数列,其中有俩是3,1,1在3的右边,那么,1比3淘汰的更晚,而且比他更小
//那么我就可以直接把3删了啊,留着3干嘛,反正打印的是1
//别的就是,当窗口往右划了,别忘了跟进一下左端点,for循环到形成窗口了再打印
//看不懂的看这个视频https://www.bilibili.com/video/BV1H5411j7o6/?spm_id_from=333.999.0.0
//yxc讲课不知道整天讲的什么,听不懂烦死
const int N = 1e6 + 10;
int q[N], n, k, ss = 0, tt = -1, arr[N];
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= n; i++) {
if (ss <= tt && i - k + 1 > q[ss]) ss++;//这里应该无论是0开始,还是从1开始,都是要+1的
//右端点3,k是3,右端点减去k就是0了,所以得加个1(这时候左端点还是0呢)
while (ss <= tt && arr[q[tt]] >= arr[i]) tt--;
q[++tt] = i;
if (i >= k) cout << arr[q[ss]] << " ";
}
cout << endl;
ss = 0, tt = -1;
//按着类推就好,不过注意打印也是打印的右端点,我最早打印的左端点,但右端点才是情况下的最优解
for (int i = 1; i <= n; i++) {
if (ss <= tt && i - k + 1 > q[ss]) ss++;
while (ss <= tt && arr[q[tt]] <= arr[i]) tt--;
q[++tt] = i;
if (i >= k) cout << arr[q[ss]] << " ";
}
}
////下面附上从0开始的版本
#include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);//大概也就这里有变化了
}
puts("");
hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);//大概也就这里有变化了
}
puts("");
return 0;
}
五.求连续区间最大值
ll maxSum(ll a[], int n){
ll sum = -1e18;
ll b = 0;
for(int i = 0; i < n; i++){
if(b > 0)
b += a[i];
else
b = a[i];
if(b > sum)
sum = b;
}
return sum;
}