动态规划

LIS（最长上升子序列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//复杂度O(nlogn)
int n;
cin>>n;
vector<int> v(n+5);//原始数据
int len = 0;
for(int i= 1;i<=n;i++) scanf("%d",&v[i]);
vector<int> stk;//stk[i]表示长度为i+1的上升子序列，末尾最小是多少。
for(int i = 1;i<=n;i++){
    if(stk.empty() || v[i] > stk.back()){//如果能接在后面
        stk.push_back(v[i]);
    }else{//如果不能，就在stk中找第一个大于等于v[i]的stk[t],用v[i]替换
        int t = lower_bound(stk.begin(),stk.end(),v[i]) - stk.begin();
        stk[t] = v[i];
    }
}
cout<<stk.size();

LCS（最长公共子序列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f[N][N];
int n,m;
cin>>n>>m;
string A, B;
cin>>A>>B;
A = " " + A;
B = " " + B;
for(int i = 1;i<=n;i++){
    for(int j = 1;j<=m;j++){
        f[i][j] = max(f[i][j],f[i-1][j]);
        f[i][j] = max(f[i][j],f[i][j-1]);
        if(A[i] == B[j]){
            f[i][j] = max(f[i][j],f[i-1][j-1] + 1);
        }
    }
}
cout<<f[n][m];

数论

博弈论：sg函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 1e5+5;//N表示一个堆最多多少物品
int f[N];//f[i] = sg(i).记忆化搜索
int num[50];//num储存总的有向图的数量（也就是NIM中的有几堆物品）
int sg(int x){
    if(f[x] != -1) return f[x];
    unordered_set<int> s;
    //出边，分别代表取一个，取两个，全取出来
    if(x >= 1) s.insert(sg(x-1));
    if(x >= 2) s.insert(sg(x-2));
    s.insert(sg(0));
    //mex
    for(int i = 0;;i++){
        if(!s.count(i)) return f[x] = i;
    }
}
int main(){
    memset(f,-1,sizeof(f));
    f[0] = 0;//初始值，可以不设?,也可以视情况设其他的(例如脑算出sg(1),sg(2)等，然后直接给出值)
    int res = 0;//总的sg
    for(int x : num){
        // res ^= sg(x);
    }
    return 0;
}

数据结构

线段树

查询区间最值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
struct segment_tree{
	#define ls (p<<1)
	#define rs (p<<1|1)
	
	int n;
	struct node{
		int mx,mi;
	}tr[maxn<<3];
	
	void push_up(int p){
		tr[p]=node(max(tr[ls].mx,tr[rs].mx),min(tr[ls].mi,tr[rs].mi));
		return;
	}
	void build(int p,int l,int r){
		if(l==r){
			cin>>tr[p].mx;
			tr[p].mi=tr[p].mx;
			return;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(p);
	}
	void build(int _n){
		n=_n;
		build(1,1,n);
	}
	void print(int p=1,int l=1,int r=n){
		printf("%2d[%d,%d] %d %d \n",p,l,r,tr[p].mx,tr[p].mi);
		if(l==r){
			return;
		}
		int mid=(l+r)>>1;
		print(ls,l,mid);
		print(rs,mid+1,r);
	}
	
	void erase(int p,int l,int r,int id){
		if(l==r){
			tr[p].mx=-inf;
			tr[p].mi=inf;
			return;
		}
		int mid=(l+r)>>1;
		if(id<=mid)erase(ls,l,mid,id);
		else erase(rs,mid+1,r,id);
		push_up(p);
	}
	int qmx(int p,int l,int r,int L,int R){
		if(l<=L && R<=r){
			return tr[p].mx;
		}
		int mid=(l+r)>>1,ans=-inf;
		if(L<=mid)ans=max(ans,qmx(ls,l,mid,L,R));
		if(mid+1<=R)ans=max(ans,qmx(rs,mid+1,r,L,R));
		return ans;
	}
	int qmi(int p,int l,int r,int L,int R){
		if(l<=L && R<=r){
			return tr[p].mi;
		}
		int mid=(l+r)>>1,ans=inf;
		if(L<=mid)ans=min(ans,qmi(ls,l,mid,L,R));
		if(mid+1<=R)ans=min(ans,qmi(rs,mid+1,r,L,R));
		return ans;
	}
	
	#undef ls
	#undef rs
}tr;