05-04 09:02 已编辑山东省烟台第二中学算法工程师发布于山东

关注

五一普转提笔记Day-3

免责声明:本人并非原创者，如有不对请指出，勿喷。

上午

1.lower_bound 和 upper_bound

lower_bound(首元素地址，尾元素地址的下一个地址，目标数)

找到第一个不小于k的元素的地址

upper_bound(首元素地址，尾元素地址的下一个地址，目标数)

找到第一个大于k的元素的地址

代码：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
signed main(){
	int n=10;
	int a[15];
	set<int> se;
	for(int i=1;i<=n;i++) a[i]=i*i;
	cout<< *lower_bound(a+1,a+n+1,15)<<"\n";//16
	cout<< *upper_bound(a+1,a+n+1,15)<<"\n";//16
	for(int i=1;i<=n;i++){
		se.insert(i*i);
	}
	auto y = se.lower_bound(15);
	auto z = se.upper_bound(15);
	cout<<*y<<"\n";
	cout<<*z<<"\n";
	return 0;
}

$2$ .dp(动态规划)

dp分类:

①状态:基础

②转移方程:状态之间的关系

③初始化:边界状态的计算

④如何定状态:所有在变化的量定为状态

第一类↓求数列中的某个值

$T1$

这道题共有 $8$ 个变量

所以应该有 $8$ 个维度，但是空间有些太大了。我们可以将守门员和队长设为是否选定，其它角色根据题目设定，复杂度 $n^2$ 但是对于最后一问，这样做就不可以了，因为两个队伍其他人一样，队长不一样，也会被认为不同，不符合题目要求。解决方法是把这些人按价值从大到小排序，然后在选人时就不需要队长这个维度了，直接把第一个人选为队长，因为他价值最高。第一次写这么多分析一道题

$T2$ 斐波那契数列

我们可以很好想到这个代码:

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
signed main(){
	int n;
	cin>>n;
	vector<int> f(n);
	f[0]=0;
	f[1]=1;
	for(int i=2;i<=n;i++){
		f[i]=f[i-1]+f[i-2];
	}
	cout<<f[n]<<"\n";
	return 0;
}

时间复杂度为 $O(n)$ 但如果 $n≥10^9$ ,那就超时了，我们就要再想方法。我们可以求到通项公式，其实我也不会:

但是这也用不了，因为首先有 $√$ ，精度有问题。其次 $10^9$ 带进去太大了，也算不了。我们就要用矩阵。

①矩阵加法:大小相同，对应位置相加即可。

②矩阵乘法:一个 $nm$ 的矩阵乘一个 $mk$ 的矩阵乘后会形成一个 $n*k$ 的矩阵。先取出第一个矩阵的第x行，第二个矩阵的第y列，对应好后相乘结果在相加，此时就可以求出结果矩阵第x行第y列的值。

代码:

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct matrix{
	int n,m,a[1024][1024];
	matrix(){
		n=m=0;
		memset(a,0,sizeof(a));
	}
}x,y,z;
matrix operator*(const matrix &x,const matrix &y){
	matrix z;
	z.n=x.n;
	z.m=y.m;
	for(int i=0;i<z.n;i++){
		for(int k=0;k<x.m;k++){
			for(int j=0;j<z.m;j++)
				z.a[i][j]=z.a[i][j]+x.a[i][k]*y.a[k][j];
		}
	}
	//ijk 0.51秒
  //kji 0.57秒
  //ikj 0.03秒
}
signed main(){
	int n=1024;
	x.n=x.m=n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			x.a[i][j]=rand();
		}
	}
	y.n=y.m=n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			y.a[i][j]=rand();
		}
	}
	x*y;
	//cout<<"hello";
	return 0;
}

由测试可知，循环顺序为 $i→k→j$ 会更快。其实我也不知道为什么。

原因:

计算机有三种存储设备：缓存，内存，硬盘。其中硬盘速度最慢，缓存速度最快。当我们访问一个元素，计算机会先从缓存中找，如果找不到，就会把这一行中所有的元素存进缓存，这就是为什么把j放到最后是最快的。

PS：理论上缓存比内存快100倍！

还没看懂点这里

回归正题( $T2$ ),我们可以想到用快速幂和矩阵乘法：

代码:

#include<cstdlib>
#include<cstring>
#include<iostream>

using namespace std;

struct matrix
{
	int n,m;
	int a[3][3];
	matrix()
	{
		n=m=0;
		memset(a,0,sizeof(a));	
	} 
}A,B;

matrix operator*(const matrix &x,const matrix &y)
{//O(n^3)
	//matrix z;
	z.n = x.n;z.m = y.m;
	for (int i=1;i<=z.n;i++)
		for (int k=1;k<=x.m;k++)
			for (int j=1;j<=z.m;j++)
				z.a[i][j] = z.a[i][j] + x.a[i][k] * y.a[k][j];
	return z;
}

matrix ksm(matrix a,int b)//计算a^b
{
	if (b==0)
	{
		matrix c;
		c.n=c.m=a.n;
		for (int i=1;i<=c.n;i++)
			c.a[i][i]=1;
		return c;
	}
	matrix c = ksm(a,b/2);//c=a^(b/2)
	c=c*c;
	if (b&1) c=c*a;
	return c;
} 

int main()
{
	A.n=1;A.m=2;
	A.a[1][1]=0;A.a[1][2]=1;
	
	B.n=2;B.m=2;
	B.a[1][1]=0;B.a[1][2]=1;
	B.a[2][1]=1;B.a[2][2]=1;
	
	C = A * ksm(B,n);
	cout << C.a[1][1] << "\n";
	
	return 0;
}

结论:与前面几项有关就要写几项

第一类↑求数列中的某个值

第二类↓求方案数

方法:先升维再降维

$T3$

拆完点后用矩阵乘法 $+$ 快速幂，就做完了，手有点懒没写

$T4$

不难想到一个基础的思路:把这道题转化为上午的矩阵乘法+快速幂。

但是有1000个点，直接就TLE了(时间复杂度 $O(n^3log(t))$ )。我们就要更换思路，我们可以通过加括号和拆括号来求解，复杂度 $O(k^3log(t))$ 。

第二类↑求方案数

第三类↓排列dp

排列:一个序列中每个数出现且只出现1次

特征:问有多少个排列等有关排列的问题

核心:插入

维度:f[i]已经把 $1到i$ 或 $i到n$ 插入了

$T5$

基础思路是暴力，可时间复杂度为 $O(!n)$ ,太高了。

分析维度: $f[i][j]=方案数$ 表示已经插入1~i其中有j个逆序对的方案数

转移方程:i+1不会与前面所有数形成逆序对，会与后面所有数形成逆序对。所以转移方程为: $f[i][j]→f[i+1][j+i-k]$ ,如图:

代码如下:

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e3+10;
int f[maxn][maxn];
signed main(){
	
	int n;
	cin>>n;
	f[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=(i*(i-1))>>1;j++){
			for(int k=0;k<=i;k++){
				f[i+1][j+i-k]+=f[i][j];
			}
		}
	}
	cout<<f[n][n];
	return 0;
}

此时时间复杂度为O(n^4),很明显需要优化。优化后代码如下:

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e3+10;
int f[maxn][maxn];
signed main(){
	
	int n;
	cin>>n;
	f[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=1;j++){
			for(int k=0;k<=i;k++){
				f[i+1][(j+i-k)%2]+=f[i][j];
			}
		}
	}
	cout<<f[n][n];
	return 0;
}

此时时间复杂度为O(n^2)，还是不尽人意，还需要优化。图如下:

此时时间复杂度为O(n),代码如下:

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e3+10;
int f[maxn][maxn];
signed main(){
	
	int n;
	cin>>n;
	f[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=1;j++){
			f[i+1][(j+i)%2]+=x*f[i][j];
			f[i+1][j]+=y*f[i][j];
		}
	}
	cout<<f[n][n];
	return 0;
}