05-04 09:02 已編輯山東省煙臺(tái)第二中學(xué) 算法工程師發(fā)布于山東

關(guān)注

五一普轉(zhuǎn)提筆記Day-3

免責(zé)聲明:本人并非原創(chuàng)者，如有不對(duì)請(qǐng)指出，勿噴。

上午

1.lower_bound 和 upper_bound

lower_bound(首元素地址，尾元素地址的下一個(gè)地址，目標(biāo)數(shù))

找到第一個(gè)不小于k的元素的地址

upper_bound(首元素地址，尾元素地址的下一個(gè)地址，目標(biāo)數(shù))

找到第一個(gè)大于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(動(dòng)態(tài)規(guī)劃)

dp分類:

①狀態(tài):基礎(chǔ)

②轉(zhuǎn)移方程:狀態(tài)之間的關(guān)系

③初始化:邊界狀態(tài)的計(jì)算

④如何定狀態(tài):所有在變化的量定為狀態(tài)

第一類↓求數(shù)列中的某個(gè)值

$T1$

這道題共有 $8$ 個(gè)變量

所以應(yīng)該有 $8$ 個(gè)維度，但是空間有些太大了。我們可以將守門員和隊(duì)長(zhǎng)設(shè)為是否選定，其它角色根據(jù)題目設(shè)定，復(fù)雜度 $n^2$ 但是對(duì)于最后一問，這樣做就不可以了，因?yàn)閮蓚€(gè)隊(duì)伍其他人一樣，隊(duì)長(zhǎng)不一樣，也會(huì)被認(rèn)為不同，不符合題目要求。解決方法是把這些人按價(jià)值從大到小排序，然后在選人時(shí)就不需要隊(duì)長(zhǎng)這個(gè)維度了，直接把第一個(gè)人選為隊(duì)長(zhǎng)，因?yàn)樗麅r(jià)值最高。第一次寫這么多分析一道題

$T2$ 斐波那契數(shù)列

我們可以很好想到這個(gè)代碼:

#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;
}

時(shí)間復(fù)雜度為 $O(n)$ 但如果 $n≥10^9$ ,那就超時(shí)了，我們就要再想方法。我們可以求到通項(xiàng)公式，其實(shí)我也不會(huì):

但是這也用不了，因?yàn)槭紫扔?img alt="√" src="https://hr.nowcoder.com/equation?tex=%E2%88%9A&preview=true">，精度有問題。其次 $10^9$ 帶進(jìn)去太大了，也算不了。我們就要用矩陣。

①矩陣加法:大小相同，對(duì)應(yīng)位置相加即可。

②矩陣乘法:一個(gè) $nm$ 的矩陣乘一個(gè) $mk$ 的矩陣乘后會(huì)形成一個(gè) $n*k$ 的矩陣。先取出第一個(gè)矩陣的第x行，第二個(gè)矩陣的第y列，對(duì)應(yīng)好后相乘結(jié)果在相加，此時(shí)就可以求出結(jié)果矩陣第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;
}

由測(cè)試可知，循環(huán)順序?yàn)?img alt="i→k→j" src="https://hr.nowcoder.com/equation?tex=i%E2%86%92k%E2%86%92j&preview=true">會(huì)更快。其實(shí)我也不知道為什么。

原因:

計(jì)算機(jī)有三種存儲(chǔ)設(shè)備：緩存，內(nèi)存，硬盤。其中硬盤速度最慢，緩存速度最快。當(dāng)我們?cè)L問一個(gè)元素，計(jì)算機(jī)會(huì)先從緩存中找，如果找不到，就會(huì)把這一行中所有的元素存進(jìn)緩存，這就是為什么把j放到最后是最快的。

PS：理論上緩存比內(nèi)存快100倍！

還沒看懂點(diǎn)這里

回歸正題( $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)//計(jì)算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;
}

結(jié)論:與前面幾項(xiàng)有關(guān)就要寫幾項(xiàng)

第一類↑求數(shù)列中的某個(gè)值

第二類↓求方案數(shù)

方法:先升維再降維

$T3$

拆完點(diǎn)后用矩陣乘法 $+$ 快速冪，就做完了，手有點(diǎn)懶沒寫

$T4$

不難想到一個(gè)基礎(chǔ)的思路:把這道題轉(zhuǎn)化為上午的矩陣乘法+快速冪。

但是有1000個(gè)點(diǎn)，直接就TLE了(時(shí)間復(fù)雜度 $O(n^3log(t))$ )。我們就要更換思路，我們可以通過加括號(hào)和拆括號(hào)來求解，復(fù)雜度 $O(k^3log(t))$ 。

第二類↑求方案數(shù)

第三類↓排列dp

排列:一個(gè)序列中每個(gè)數(shù)出現(xiàn)且只出現(xiàn)1次

特征:問有多少個(gè)排列等有關(guān)排列的問題

核心:插入

維度:f[i]已經(jīng)把 $1到i$ 或 $i到n$ 插入了

$T5$

基礎(chǔ)思路是暴力，可時(shí)間復(fù)雜度為 $O(!n)$ ,太高了。

分析維度: $f[i][j]=方案數(shù)$ 表示已經(jīng)插入1~i其中有j個(gè)逆序?qū)Φ姆桨笖?shù)

轉(zhuǎn)移方程:i+1不會(huì)與前面所有數(shù)形成逆序?qū)?，?huì)與后面所有數(shù)形成逆序?qū)ΑＫ赞D(zhuǎn)移方程為: $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;
}

此時(shí)時(shí)間復(fù)雜度為O(n^4),很明顯需要優(yōu)化。優(yōu)化后代碼如下:

#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;
}

此時(shí)時(shí)間復(fù)雜度為O(n^2)，還是不盡人意，還需要優(yōu)化。圖如下:

此時(shí)時(shí)間復(fù)雜度為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;
}