黛苏珂の专用板子

如题目＞▽＜

自用代码模板

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <set>
#include <stack>
#include <list>
#include <map>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define P (int)(1e9+7)
#define INF 0x3f3f3f3f
#define MAX 500005
#define all(arr) arr.begin(),arr.end()
#define rall(arr) arr.rbegin(),arr.rend()
#define pb emplace_back
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define forn(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;

int main(){
    fast;
    
    return 0;
}

基础

算法基础

二分

特征

  1. 具有单调性的数组
  2. 求最大/最小值
  3. 答案离散(具有有限种可能)
  • 不直接找到目标值的写法，跳出循环后的num[l-1]要么是目标值，要么是目标值目标值左面的值；num[l]是目标值右面的值
1
2
3
4
5
6
7
8
9
10
11
int l=0,r=n+1;
while (l<r){
    int mid = l + ((r - l) >> 1);//取中间值
    if(num[mid]<target){
        l = mid + 1;
    }
    else{
        r = mid;
    }
}
cout<<num[l-1];

三分

特征

类似于二分查找，三分搜索法也是比较常用的基于分治思想的高效查找方法。但是和二分不同，二分只适用于单调函数，三分用于单峰函数(求极值)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long double f(double x){// 算出某个点的函数值
    //something
}

const double eps=1e-10;// 精度，建议开高一点，免得被卡
long double sanfen(double l, double r){
    long double mid,midr,ans, midl;
    while (fabs(r-l)>eps) {
        mid = (r - l) / 3.0;
        midl = l + mid;
        midr= r - mid;
        //>:求极小值  <:求极大值
        if(f(midl) > f(midr)) l=midl; else r=midr;   
    } 
    ans=f(l);// l为三分出的极值点，f(l)为此处的函数值
    return ans;
}

位运算

  1. ’&’符号，x&y，会将两个十进制数在二进制下进行与运算(都1为1，其余为0） 然后返回其十进制下的值。例如3(11)&2(10)=2(10)。
  2. ’|’符号，x|y，会将两个十进制数在二进制下进行或运算（都0为0，其余为1） 然后返回其十进制下的值。例如3(11)|2(10)=3(11)。
  3. ’^’符号，x^y，会将两个十进制数在二进制下进行异或运算（不同为1，其余 为0）然后返回其十进制下的值。例如3(11)^2(10)=1(01)。
  4. ’’符号，x，按位取反。例如~101=010。
  5. ’<<’符号，左移操作，x<<2，将x在二进制下的每一位向左移动两位，最右边用0填充，x<<2相当于让x乘以4。 ’>>’符号，是右移操作，x>>1相当于给x/2，去掉x二进制下的最右一位
  6. 判断一个数字x二进制下第i位是不是等于1。（最低第1位）
    方法：if(((1<<(i−1))&x)>0) 将1左移i-1位，相当于制造了一个只有第i位 上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0， 说明x第i位上是1，反之则是0。
  7. 将一个数字x二进制下第i位更改成1。
    方法：x=x|(1<<(i−1)) 证明方法与1类似。
  8. 将一个数字x二进制下第i位更改成0。
    方法：x=x&~(1<<(i−1))
  9. 把一个数字二进制下最靠右的第一个1去掉。
    方法：x=x&(x−1)
  10. 获取一个32位数字二进制中1的个数
    方法：__builtin_popcount(x)

数据结构

队列

见STL队列的使用

栈

单调栈

特征

定义：内部元素满足单调性的栈。
用途：线性时间内处理出数组中每一个 i 左边/右边 第一个 大于/小于 ai 的位置。

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
// aj < ai 时，ai的结果记录为aj,没有的话记录为0
int res[MAX];// 结果数组
int a[MAX];// 原数组
stack<pair<int, int> > st;// 单调非递减栈
int main(){
 fast;
 
 int n;
 cin >> n;
 for (int i = 1; i <= n; i++) {
  cin >> a[i];
  if (st.size()) {
   while (st.size()&&st.top().first > a[i]) {// 当单调栈有内容时，并且栈中元素大于当前值时
    res[st.top().second] = i;// 将原本栈顶元素的结果值更改为现值的下标
    st.pop();
   }
  }
  st.push({a[i], i});// 新元素入栈
 }
 for(int i = 1; i <= n; i++) {
  cout << res[i] << " ";
 }
 
 return 0;
}

堆

对顶堆

特征

可用于动态维护第k大的值（例如中位数）,每次操作为O（logn）

原理

我们需要分别维护两个堆，让小根堆的堆顶作为分界线，如果大于它就加入小根堆，否则就加入大根堆,如果两个堆的个数相差超过1，就将多的那个堆的堆顶弹出来放到另一个堆的堆顶。奇数个数的中位数显然是堆中数量最多的堆的堆顶。偶数个数的中位数则是两个堆堆顶取平均值。

  • 加入元素的操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
priority_queue<int> q_big;// 大顶堆
priority_queue<int, vector<int>, greater<int> > q_less;// 小顶堆

void insert(int x) {
    if (q_less.empty() || x > q_less.top()) {
        q_less.push(x);
    } else {
        q_big.push(x);
    }
    while (q_less.size() > q_big.size() + 1) {
        q_big.push(q_less.top());
        q_less.pop();
    }
    while (q_big.size() > q_less.size() + 1) {
        q_less.push(q_big.top());
        q_big.pop();
    }
}

树

BT树（普通平衡树）

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1.插入数值 x

2.删除数值 x (若有多个相同的数，应只删除一个)。

3.查询数值 x 的排名(若有多个相同的数，应输出最小的排名)。

4.查询排名为 x 的数值。

5.求数值 x 的前驱(前驱定义为小于 x 的最大的数)。

6.求数值 x 的后继(后继定义为大于 x 的最小的数)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n,opt,x;
 
vector<int> epic;
 
int main()
{
 cin>>n;
 while(n--)
 {
  cin>>opt>>x;
  
  if(opt==1) epic.insert(upper_bound(epic.begin(),epic.end(),x),x);
  else if(opt==2) epic.erase(lower_bound(epic.begin(),epic.end(),x));
  else if(opt==3) printf("%d\n",lower_bound(epic.begin(),epic.end(),x)-epic.begin()+1);
  else if(opt==4) printf("%d\n",epic[x-1]);
  else if(opt==5) printf("%d\n",*--lower_bound(epic.begin(),epic.end(),x));
  else if(opt==6) printf("%d\n",*upper_bound(epic.begin(),epic.end(),x));
 }

LCA (最近公共祖先)

特征

在一个树上找到两个点最近的公共祖先，使用倍增法创建ST表需要nlogn时间，查询logn时间，一次建表、多次使用，若只有几次查询还不如暴力（）

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
vector<int> g[MAX];
int fa[MAX][25], dep[MAX];// fa[i][j] 表示节点i的2^j级祖先, dep 节点深度
void bfs(int u) {// bfs求深度
    memset(dep, 0x3f, sizeof dep);
    dep[0] = 0, dep[u] = 1;
    queue<int> q;
    q.push(u);
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (auto v : g[t]) {
            if (dep[v] > dep[t] + 1) {
                dep[v] = dep[t] + 1;
                q.push(v);
                fa[v][0] = t;
                forn (i, 1, 20) {// 一般2^20 大约1e6够用了
                    fa[v][i] = fa[fa[v][i - 1]][i - 1];//它的2^i-1 级祖先的2^i-1 级祖先
                }
            }
        }
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);// 确保dep[x]>=dep[y]
    for (int i = 19; i >= 0; i--) {
        if (dep[fa[x][i]] >= dep[y]) {// 增量递减的方式找x
            x = fa[x][i];// 当深度比y大时，x跳到那个位置。寻找到增量为0，即x,y在同一深度
        }
    }
    if (x == y)// y就是父亲
        return x;
    for (int i = 19; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i], y = fa[y][i];// 到达的节点不同时，一起向上走
        }
    }
    return fa[x][0];
}

模板题
例题

线段树

特征

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

  • 普通带懒标记线段树
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
72
73
74
75
76
// 建树前准备
#define ls(x) x << 1 // 左儿子
#define rs(x) x << 1 | 1 //右儿子
long long num[MAX << 2];// 线段树本体（需要四倍空间）
long long a[MAX];// 源数据数组
long long lazy[MAX << 2];// 懒标记

// 线段树的建立
inline void push_up(ll p) { // 向上更新节点的值
    num[p] = num[ls(p)] + num[rs(p)];
}
inline void build(ll p, ll l, ll r) {
    lazy[p] = 0;
    if (l == r) {// 如果左右区间相同，那么当前必然是叶子节点，真实赋值
        num[p] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    // 采用二叉树来降低复杂度
    push_up(p);
    // 通过子节点来维护父亲节点，所以应当在回溯时pushup
}

// 线段树的区间修改
inline void f(ll p, ll l, ll r, ll k) {
    num[p] += (r - l + 1) * k;
    lazy[p] += k;
    // 区间统一进行修改，懒标记加上k，节点值加上节点长度*k（区间每个数同时加上k）
}
// f函数用于更新当前节点所代表的区间
inline void push_down(ll p, ll l, ll r) {
    ll mid = (l + r) >> 1;
    f(ls(p), l, mid, lazy[p]);
    f(rs(p), mid + 1, r, lazy[p]);
    lazy[p] = 0;
    // 每次更新两个儿子节点，向下传递懒标记（注意将本节点的懒标记清零）
}
inline void update(ll nl, ll nr, ll l, ll r, ll p, ll k) {
    // nl, nr为要修改的区间
    // l, r, p为当前节点的区间断点以及节点编号
    if (nl <= l && nr >= r) {// 要修改的区间包含该节点，进行更新
        f(p, l, r, k);
        return;
    }
    ll mid = (l + r) >> 1;
    // 下一次递归点，要向下更新节点
    push_down(p, l, r);
    if (nl <= mid) {
        update(nl, nr, l, mid, ls(p), k);
    }
    if (nr > mid) {
        update(nl, nr, mid + 1, r, rs(p), k);
    }
    // 回溯时要向上更新节点值
    push_up(p);
}

// 线段树的区间查询
inline ll query(ll x, ll y, ll l, ll r, ll p) {
    ll res = 0;
    if (x <= l && y >= r) {// 查找的区间包含该节点，直接返回该节点的值
        return num[p];
    }
    ll mid = (l + r) >> 1;
    // 一定不要忘了查询时也要向下更新节点，因为有的懒标记有可能没有完全覆盖需要查询的区间，所以要进行更新
    push_down(p, l, r);
    if (x <= mid) {
        res += query(x, y, l, mid, ls(p));
    }
    if (y > mid) {
        res += query(x, y, mid + 1, r, rs(p));
    }
    return res;
}
  • 好用的一键打包式线段树
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
// 这两个宏不能忘了
#define ls(x) x << 1
#define rs(x) x << 1 | 1

struct Tree {
    ll l, r, sum, len;
} tree[MAX << 2];
void push_up(ll p) {
    ll l = tree[p].l, r = tree[p].r;
    if (tree[p].sum) {
        tree[p].len = X[r + 1] - X[l];
    } else {
        tree[p].len = tree[ls(p)].len + tree[rs(p)].len;
    }
}
void build(ll p, ll l, ll r) {
    tree[p].l = l, tree[p].r = r;
    tree[p].len = 0;
    tree[p].sum = 0;
    if (l == r) {
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
}
void update(ll p, ll L, ll R, ll k) {
    ll l = tree[p].l, r = tree[p].r;
    if (X[l] >= R || X[r + 1] <= L) {
        return;
    }
    if (X[l] >= L && X[r + 1] <= R) {
        tree[p].sum += k;
        push_up(p);
        return;
    }
    update(ls(p), L, R, k);
    update(rs(p), L, R, k);
    push_up(p);
}

上面模板只提供了最基础的加法线段树，其他高端的线段树请自定义
区间乘法：需要将区间内的数*x，两个懒标记可解。更新值时要注意要先乘再加这样才不会丢失精度

树状数组

特征

树状数组（Binary Index Tree, BIT），是一种简洁好用的数据结构，最简单的树状数组支持两种操作

  • 单点修改：更改数组中某一个元素的值
  • 区间查询：查询一个区间内所有元素的和
    可以解决大部分基于区间上的更新与求和问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int tree[MAXN];
inline void update(int i, int x)// 单点修改
{
    for (int pos = i; pos < MAXN; pos += lowbit(pos))
        tree[pos] += x;
}
inline int query(int n)// 求前n项和
{
    int ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos))
        ans += tree[pos];
    return ans;
}
inline int query(int a, int b)// 区间和查询
{
    return query(b) - query(a - 1);
}
  • 区间更新，单点查询
    我们可以引入一个差分数组b
    设数组原数组为a，则有$b[i]=a[i]-a[i-1];(a[0]=0;)$，那么$a[i]=b[1]+….+b[i]$，求单点就是差分数组的前n项和，剩下都一样了
  • 多维区间查询
    要注意块与块之间的重叠

并查集

特征

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

  • 合并（Union）：把两个不相交的集合合并为一个集合。
  • 查询（Find）：查询两个元素是否在同一个集合中。

基础代码（路径压缩）

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
int fa[MAXN];
inline void init(int n)// 初始化
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

int find(int x)// 查询父节点
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

inline void merge(int i, int j)// 合并
{
    fa[find(i)] = find(j);
}

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

扩展（按秩合并）

优点：可进一步省时间
原因：我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

STL引入

引用 Reference

  • 是一个别名，相当于给其取个小名（蟑螂和小强都指代一个东东）,可以增强代码可读性
1
2
3
4
5
int zhanglang[3]={1,2,3};
for(int i=0;i<3;i++){
    const &p=zhanglang[i];
    cout<< p<<endl;
}
  • 函数传参：相当于传入地址
1
2
3
4
5
void _swap(int &x,int &y){
    int t=x;
    x=y;
    y=t;
}

类 class struct

  • 一个构造器
1
2
3
4
5
6
// struct是访问权限为public的class
class _class{
    public:
    int num;
    _class(int _num):num(_num){}
};
1
2
3
4
5
// struct是访问权限为public的class
struct _class_struct{
    int num;
    _class_struct(int _num):num(_num){}
};
1
2
3
4
struct node{
    int u,v,w;
    node(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
};
  • new一个对象
1
2
3
_class a=_class();//先new出对象，再拷贝到新的对象中
_class a(123456);// previous: _class(int _a){a(_a);} 有参构造
_class a;//无参构造

重载运算符

  • 格式：[返回值][operator][运算符][参数列表][const][body]
1
2
3
4
5
6
7
8
9
10
11
12
13
struct node{
    int u,v,w;
    node(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
    bool operator<(const node&_node) const{// 成员变量重载
        return w<_node.w;
    }
    bool friend operator>(node &node_a,node &node_b){//友元变量重载
        return node_a.w>node_b.w;
    }
};
int operator+(node &_node_a,node &_node_b){// 类外重载
    return _node_a.w+_node_b.w;
}

匿名函数 lambda expressions

  • 可以在函数中定义函数的骚操作（常用于sort中的cmp函数定义）,当然也可以将其实名化
1
2
3
4
5
6
7
8
9
10
11
12
auto func=[](int a,int b){
    return a+b;
}
cout<<func(1,2);

int a[3]={1,2,3};
sort(a,a+3,[](int a,int b){return a>b;});
//也可以使用greater(降序)排序方式进行排序(升序为less)
//sort(a,a+3,greater<>());
for(int i=0;i<3;i++){
    cout<<a[i]<<endl;
}

pair<T1,T2>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//tip1
using pii =pair<int,int>;//常用的int型pair
//or:
typedef pair<int,int> pii;
#define pii pair<int,int>

//tip2
#define x first//在访问pair成员时可以用x，y来直观地引用
#define y second

//ctor(constructor)
pii p(1,2);
pii a=make_pair(3,4);
auto b=a;
cout<<p.x<<"="<<p.first;

pair<int,pii>pill(12345,make_pair(123,234));//可以pair套pair
// 默认重载小于号< 依照first排序
puts(a<b?"less":"greater");

迭代器 Iterator

Container->Iterator->Algorithm(容器通过迭代器调用算法)
类似于指针,通过迭代器访问容器的值

  • 分类
  1. 正向迭代器
1
container::iterator it;
  1. 反向迭代器
1
container::reverse_iterator it;

使用

  • 使用auto关键帧循环
1
2
3
4
map<int, int> dsk;
for (auto it : dsk) {
  cout<<it.second<<" ";
}
  • 正常遍历
1
2
3
4
5
using Iter=vector<int>::iterator;//迭代器重命名，方便使用
vector<int> dsk = {1, 2, 3, 4, 5};
    for (Iter it = dsk.begin(); it != dsk.end();it++){
        cout << *it << " ";
    }

STL常用算法

排序 sort&stable_sort

  • sort(begin,end,cmp);
  • begin：头迭代器
  • end：尾迭代器
  • cmp：排序方式
1
2
3
4
5
6
7
8
9
int arr[]={1,1,4,5,1,4,114514,-114514,19260817};
int n=sizeof(arr)/sizeof(arr[0]);
sort(arr,arr+n);//默认升序排列
sort(arr,arr+n,greater<>());//降序排列

stable_sort(arr,arr+n);//稳定排序，不会打乱原有相同元素的位置关系，相当于使用归并排序
vector<int> dsk={1,1,4,5,1,4,114514,-114514,19260817};
sort(dsk.begin(),dsk.end());//升序
sort(dsk.rbegin(),dsk.rend());//降序,使用反向迭代器的骚操作

二分查找 lower_bound&upper_bound

  • 在有序容器中，使用二分的方式查找元素
  • lower_bound:查找到第一个大于等于目标值的元素，返回迭代器
  • upper_bound:查找到第一个大于目标值的元素，返回迭代器
1
2
3
4
5
6
7
8
9
10
11
int arr[]={1,1,4,5,1,4,114514,-114514,19260817};
int n=sizeof(arr)/sizeof(arr[0]);
sort(arr,arr+n);//升序排列
int pos=lower_bound(arr,arr+n,114514)-arr;//获得待查找元素的相对位置
auto acl=lower_bound(arr,arr+n,114514);//获得待查找元素的迭代器
cout<<arr[pos]<<"="<<*acl<<endl;

sort(arr,arr+n,greater<>())//降序排列
int pos=lower_bound(arr,arr+n,114514,greater<>())-arr;//在递减的时候，我们需要greater仿函数龟腚比较方向
auto acl=lower_bound(arr,arr+n,114514);//获得待查找元素的迭代器
cout<<arr[pos]<<"="<<*acl<<endl;

两级反转 reverse

  • 将能够双向查询的迭代器翻转过来
1
2
3
4
5
6
7
8
9
int arr[]={1,2,3,4,5,6,7,8};
int n=sizeof(arr)/ sizeof(arr[0]);
reverse(arr,arr+n);
//reverse(begin(arr),end(arr));//另一种写法，不常用

string orl="ybbbby";
string rev(orl);//拷贝赋值，效率高一点，也可以写成rev=rel
reverse(rev.begin(),rev.end());
puts(orl==rev?"Yes":"No");//简单回文串判定

填充 fill&fill_n

  • 快速填充一段区间内的值（相当于memset）
1
2
3
4
int arr[]={1,2,3,4,5,6,7,8};
int n=sizeof(arr)/ sizeof(arr[0]);
fill(arr,arr+n,0);
fill_n(arr,n,0);

最大公约数 gcd

1
cout<<__gcd(2,4);

排列

生成全排列(n!复杂度，少用)

1
2
3
4
5
6
int orl[]={2,1,3};
sort(olr,olr+3);
do{
    cout << orl[0] << orl[1] << orl[2] << endl;
} while (next_permutation(orl, orl + 3));//升序全排列
//} while (prev_permutation(orl, orl + 3));//降序全排列

STL容器

向量 vector// 查找 find()–>查不到返回_set.end()

1
2
3
4
5
cout<<*_set.find(100)<<endl;
// 二分查找，直接键入目标值
cout<<*_set.lower_bound(3)<<e ndl;
cout<<*_set.upper_bound(3)<<endl;
vector<int>arr1(10000, 0x3f3f3f3f);//第一个是大小，第二个是初始值
  • 传入值
1
2
3
arr.push_back(1);
arr.emplace_back(1);//推荐，这个是按引用传递，能快一点
arr[3]=1;//直接更改
  • 大小&容积
1
2
3
4
for (int i = 0; i < 10;i++){
    arr.emplace_back(1);//size（大小）与capacity（容积）的比较
    cout << arr.size() << "/" << arr.capacity() << endl;//倍增->log n
}
  • 提取最值&求和
1
2
3
cout<< *max_element(all(arr))<<endl;//求最大值
cout<< *minelement(all(arr))<<endl;//求最小值
cout << accumulate(all(arr), 0);//求和，初值为零
  • 重定义大小&清空
1
2
3
4
5
arr.resize(100);
cout << arr.size() << "/" << arr.capacity() << endl;
arr.clear();//在size清空的条件下，不清空capacity
arr.emplace_back(1);
cout << arr.size() << "/" << arr.capacity() << endl;
  • 推荐宏定义
1
2
3
#define all(arr) arr.begin(),arr.end()
#define rall(arr) arr.rbegin(),arr.rend()
#define pb emplace_back
  • 离散化(得到大数字的相对大小，有些大数要存到的下标太大存不下)
1
2
sort(all(arr));
arr.erase(unique(all(arr)), arr.end());
  • 邻接表（超好用）
1
2
3
4
5
6
7
8
9
struct Edge
{
    int v, cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge> E[N];
void addEdge(int u,int v,int w=1){
    E[u].emplace_back(Edge(v, w));
}

栈 队列 双端队列 stack queue deque

  • 栈（建议手写，容易被卡）
1
2
3
4
5
6
7
8
stack<int> stk;//建立
stk.push(1);//推入栈
cout << stk.top();//输出栈顶
puts(stk.empty() ? "Yes" : "No");//判断是否空
if(!stk.empty())
    cout << "size=" <<stk.size();//输出栈的大小
stk.pop();//弹出栈顶
stk = stack<int>();//清空栈

集合 Set

  • 基于红黑树(RB-tree)实现，特点是元素具有互异性
  • 优点：有序容器，能实现高效插入、查找、删除（Ologn）
  • 使用multiset可以允许元素重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
set<int> _set;//默认升序
//set<int,greater<int> > _set;//加入降序比较器
// insert 返回值为 pair<set<class>::iterator,bool>
_set.insert(1);_set.insert(2);_set.insert(3);_set.insert(1);
//set 的迭代器是只读的->const_iterator

// 查找 find()-->查不到返回_set.end()
cout<<*_set.find(100)<<endl;
// 二分查找，直接键入目标值
cout<<*_set.lower_bound(3)<<endl;
cout<<*_set.upper_bound(3)<<endl;

// erase 删除元素
_set.erase(1);
//删除元素指引位置
_set.erase(_set.insert(454).x);
//删除一段区间
_set.erase(_set.lower_bound(114),_set.lower_bound(514));//删除[114,514]内的值

映射 Map

  • 同样基于红黑树(RB-tree)的有序容器（按照key排序）,map可建立[数据结构]到[数据结构]的映射，可以说是very good
  • 通常使用场景在于离散化、建立映射关系等等。它同样支持高效插入，查询，修改(可修改value，不能修改key)，以及删除
  • 每个key(键)只能出现一次，不允许重复。
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
//前两个是类型，后面的是比较方式
map<string,int,comp>mp;
// insert(k,v) -->pair<key,value>  -->p.first p.second
mp.insert({"daisuke",520});

//使用重载的[]输出，或者迭代器输出
cout<<mp["daisuke"]<<endl;
for(auto p:mp)
    cout<<p.first<<":"<<p.second<<endl;

// 查找 find()-->查不到返回_set.end()
cout<<mp.find(100)->second<<endl;
// 二分查找，直接键入目标值
cout<<mp.lower_bound(3)->second<<endl;
cout<<mp.upper_bound(3)->second<<endl;

//排序方式，先看长度，再看字典序
struct comp{
    bool operator()(const string&a,const string&b)const{
        int la=a.size();
        int lb=b.size();
        return la!=lb?la<lb:a<b;
    }
}

// 键值是否出现过(这个复杂度还不如直接用lower_bound)
puts(mp.count("daisuke")?"Yes":"No");

无序哈希表 unordered_x

优点：查询速度很快
缺点：哈希表建立比较耗费时间
适用：查找较多时

压位 bitset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

ST表

特征

  1. ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。它主要应用倍增的思想，可以实现 [公式] 预处理、 [公式] 查询。
  2. RMQ 表示区间最大（最小）值。
  3. 可重复贡献问题是指对于运算，满足f（a，a）=a，则对应的区间询问就是一个可重复贡献问题。例如，最大值max(a, a) = a ，最大公因数gcd(a, a) = a，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。但像区间和就不具有这个性质。
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
int Max[P][21];

int query(int l, int r) {// 求区间【l,r】的所求值
    int k = log2(r - l + 1);
    return max(Max[l][k], Max[r - (1 << k) + 1][k]);
}

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {// 初始数据输入
    scanf("%d", &Max[i][0]);
}

for (int j = 1; (1 << j) <= n; j++) {// st表的创建
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
        }
    }

for (int i = 0; i < m; i++)// 区间查询
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

数学

数论

埃氏筛

1
2
3
4
5
6
7
8
bool isnp[MAXN]; // is not prime: 不是素数
void init(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (!isnp[i])
            for (int j = i * i; j <= n; j += i)
                isnp[j] = 1;
}

欧拉筛

代码如下（C++11风格）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])//是质数就存入质数表
            primes.push_back(i);
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;//标记为合数
            if (i % p == 0)
                break;
        }
    }
}

(卡c++11版本)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isnp[P];
int primes[P]; // 质数表
int pos;
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])//是质数就存入质数表
            primes[pos++] = i;
        for (int j = 0; j < pos; j++)
        {
            int p = primes[j];
            if (p * i > n)
                break;
            isnp[p * i] = 1;//标记为合数
            if (i % p == 0)
                break;
        }
    }
}

(超短风格)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void get_prime(int n){//n是筛的范围，超1e8就不好使了
    for(int i = 2; i <= n; i ++){
        if(!isnp[i]) primes[cnt ++] = i;
        
        for(int j = 0; primes[j] <= n / i; j ++){
        //这里没对j限制，因为筛质数是以i*p[j]实现的
        //而当i*p[j]>n就该结束了，所以不用限制j
            isnp[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        //这里是欧拉筛的精髓
        //保证每个合数只被自己的最小质因子筛去
        //减少了重复筛的垃圾时间
        }
    }
}

注意判断越界那里最好使用乘法而不是除法，一般不会溢出，计算机算除法比乘法要慢得多。

欧拉函数

用于求1~n中与n互质数的个数

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
int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

gcd/lcm

1
2
3
4
5
6
7
8
9
10
11
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
//或者这样写
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
// lcm=(a*b) / |gcd(a,b)|
printf("%lld\n",1ll*a*b/gcd(a,b));//需要用long long 1ll这是个ll型的1,乘上后面的强制转换

约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 试除法求所有约数
vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

调和级数

形如：ans = 1 + 1/2 + 1/3 + … +1/(n-1) = ln(n) + y
其中 y ≈ 0.5772156649(欧拉常数)

快速幂

1
2
3
4
5
6
7
8
9
10
11
//非递归快速幂
ll qpow(ll a,ll n){
    ll ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

逆元

前置知识

假设未知数分别为m、n、p，需要求C(m,n)%p。(0<=m<=n)

求组合数的数学公式：C(m,n) = n! / （m! *(n - m)!）

数学的世界很奇妙，我们知道，模运算的加法，减法，乘法和四则运算类似，即：模运算与基本四则运算有些相似。

(a + b) % p = (a % p + b % p) % p

(a - b) % p = (a % p - b % p) % p

(a b) % p = (a % p b % p) % p

但对于除法却不成立，即(a / b) % p ≠ (a % p / b % p) % p 。于是我们需要引入逆元的概念

逆元特征

即建立式子 ax%p=1 ， x的最小正整数解就是 a 的逆元。
求取 (a / b % p) 等同于 求取 (a∗(b的逆元)%p) 。 因此，求模运算的除法问题就转化为就一个数的逆元问题了。
而求取一个数的逆元，有两种方法：

  1. 费马小定理
  2. 扩展欧几里得算法

费马定理/欧拉定理

特征

在比赛中常见的p为质数，如果a,b<=1e5,p是质数时（常见有1e9+7），我们可以使用费马小定理b^(p-1)%p=1，推出b的逆元是b^(p-2)，使用快速幂求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
ll qpow(ll a, ll b, ll p) {
  ll ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a % p;//步步取余
    }
    a = a * a % p;
    b >>= 1;
  }
  return ans%p;
}
ll inv(ll a, ll p) { return qpow(a, p - 2, p); }

扩展欧几里得

特征

ax + by = m

该算法（exgcd）可以求取ax + by = gcd(a,b)的整数解x,y。进而可以求取a的逆元x。该算法有三个应用：

  1. 求解不定方程
  2. 求解模的逆元
  3. 求解线性同余方程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 记得int该ll
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int k=x;
    x=y;
    y=k-a/b*y;
    return d;
}
int inv(int a, int p) {
    int x, y;
    int gcd = exgcd(a, p, x, y);
    return (a%p*x%p) % p;
}

用扩展欧几里得求取逆元之后(a / b) % p可以换成a * inv(b, p) % p来让除法对 $p$ 取模。
注意：扩展欧几里得定理的使用前提是 m % gcd(a,b)== 0 ，否则逆元不存在

线性基

性质

  1. 线性基具有普通集合所具有的性质，即确定性、互异性、无序性。

  2. 线性基中每个数二进制下的 1 的最高位都是不同的。

  3. 线性基中没有异或和为 0 的子集。

  4. 线性基中任意多元素的异或和的值域等于原集合中任意多元素的异或和的值域。

  5. 线性基在满足上一个条件的情况下，所包含元素个数是最少的。

  6. 线性基中不同的元素异或出来的值是不同的。

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
typedef long long LL;
const int N = 100010;

int n;
LL a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);

    int k = 0;
    for (int i = 62; i >= 0; i -- )
    {
        for (int j = k; j < n; j ++ )
            if (a[j] >> i & 1)
            {
                swap(a[j], a[k]);
                break;
            }
        if (!(a[k] >> i & 1)) continue;
        for (int j = 0; j < n; j ++ )
            if (j != k && (a[j] >> i & 1))
                a[j] ^= a[k];
        k ++ ;
        if (k == n) break;
    }

    LL res = 0;
    for (int i = 0; i < k; i ++ ) res ^= a[i];
    printf("%lld\n", res);//最大异或和
    return 0;
}

BSGS算法（大步小步算法）

性质

给定一个质数 p，以及正整数 a，b，求满足同余方程 $a^x \equiv b (mod ; p)$ 的最小非负整数 x，无满足的 x 则输出 -1。 时间复杂度为$O(\sqrt{p})$。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll bsgs(ll a, ll b, ll mod){
    map<ll, ll> mp;
    ll cur = 1, t = sqrt(mod) + 1;
    for(int B = 1; B <= t; B++){
        cur = cur * a % mod;
        mp[b * cur % mod] = B;
    }
    ll now = cur;
    for(int A = 1; A <= t; A++){
        if(mp[now]) return (ll)A * t - mp[now];
        now = now * cur % mod;
    }
    return -1;
}

组合数学

全错排

1
2
3
4
5
// dp[n] 为 n 个东西任意排全排错的组合数
int dp[N+10];
dp[0]=1;
 for(int i=1;i<=N;i++)
  dp[i]=(i-1)*(dp[i-1]+dp[i-2]);

组合数

如果n,m很大，能达到1e18,p很小 <= 1e5 ，我们可以利用lucas定理C(n, m) % p = C(n % p, m % p) * lucas(n/p, m/p) % p

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
//记得int改ll
// 用于存储阶乘值
int f[1000010];
int init(int n, int p) {//初始化阶乘
  f[0] = 1;
  for (int i = 1; i < 1000005; i++) {
    f[i] = (f[i - 1] * i) % p;
  }
}
int qpow(int a, int b, int p) {//快速幂
  int ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a % p;
    }
    a = a * a % p;
    b >>= 1;
  }
  return ans;
}
int inv(int a, int p) { return qpow(a, p - 2, p); }//费马小定理求逆元
int C(int n, int m, int p) {//求组合数
  return f[n] * inv(f[m], p) % p * inv(f[n - m], p) % p;
}
int lucas(int n, int m, int p) {//卢卡斯定理，解决大组合数取模
  if (m == 0) {
    return 1;
  }
  // optimize with Lucas theorem
  return (C(n % p, m % p, p) * lucas(n / p, m / p, p)) % p;
}

博弈论

巴什（巴适）博弈

特征

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

结论

1
2
// 等于零先手负， 大于0先手胜
int res = n % (m + 1);

尼姆博弈

特征

有n堆若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，最多不限，最先取完着胜。

结论

1
2
3
4
5
6
7
8
9
// 所有堆的物品的数量异或起来是0，先手必败。
int n;
cin >> n;
int res = 0;// 结果为零先手输
forn (i, 0, n) {
    int x;
    cin >> x;
    res ^= x;
}

SG函数

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
 任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

定理

(1)有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
(2)有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

有向图游戏的和

有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和（因此我们可以把nim博弈和bash博弈杂交一起）

时间复杂度

最多100堆石子，记忆化搜索每个状态计算一次，一个状态最多k个后继状态，sg计算次数最多为1e4次，所以总时间复杂度不超过1e6,O(mk)，m为每堆的石子个数

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
int s[1100], sg[MAX];// s为每堆可以去的石子数， sg[i]为第i堆游戏的结果
int k;// 可以取得石子数
int SG(int x)  //用记忆化搜索来求SG值
{
    if (sg[x] != -1)  //保证每个状态只会被算一次，避免了时间复杂度为指数级别
        return sg[x];
    //用一个哈希表来存当前局面所能到达的局面
    set<int> st;
    for (int i = 0; i < k; i++)  //遍历可以取的石子数
    {
        if (x >= s[i])
            st.insert(SG(x - s[i]));  //把这个状态加进去并且求这个状态的SG值
    }
    //找到当前最小的自然数
    for (int i = 0;; i++)
        if (st.count(i) == 0)  //当前状态中没有i，所以最小的自然数就是它了
            return sg[x] = i;
}
int main() {
    memset(sg, -1, sizeof(sg));  //不需要多次初始化sg，因为x值相等对应的SG值是一定的
    int ans = 0;
    for(int i=0;i<n;i++)// n堆
    {
        int x;
        cin>>x;
        ans^=SG(x);
    }
    if(ans)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

字符串

字典树（Trie树）

特征

Trie树是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

功能模块

  • 存储树
1
2
3
4
5
struct Trie {
    int son[50] = {0}; // son[i]记录的是当前节点的子节点
    int sum = 0;// num 是当前这个单词在查询中出现的次数
} a[MAX];
int t = 0;// 节点编号
  • 建树
1
2
3
4
5
6
7
8
9
10
void build(string s) {
    int p = 0;// 当前访问的节点
    for (int i = 0; i < s.size(); i++) {
        if (a[p].son[s[i] - 'a'] == 0) {// 判断当前字符是否存在Trie树中
            a[p].son[s[i] - 'a'] = ++t;// 不存在则添加新节点
        }
        p = a[p].son[s[i] - 'a'];// 插入下一个字符
    }
    // a[p].sum++;// 标记当前字符串有一个
}
  • 查询
1
2
3
4
5
6
7
8
9
10
11
int query(string s) {
    int p = 0;// 当前访问的节点
    for (int i = 0; i < s.size(); i++) {
        if (a[p].son[s[i] - 'a'] == 0) { // 如果该字符的节点不存在
            return 0;// 直接返回0代表查询不到
        }
        p = a[p].son[s[i] - 'a'];// 查询下一个字母
    }
    // a[p].sum++; // 该单词的查询次数+1（本题要求）
    return a[p].sum;
}

AC自动机

特征

AC自动机用于多模式串匹配问题，例如给几个关键词（模式串），再给一篇文章，判断关键词是否在文章中出现，或出现的次数，有哪些关键词出现等等

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
namespace ac {
    int t = 0;
    int tr[MAX][26], e[MAX], fail[MAX];
    
    void insert(char *s) {
        int p = 0;
        for (int i = 0; s[i]; i++) {
            if (!tr[p][s[i] - 'a']) {
                tr[p][s[i] - 'a'] = ++t;
            }
            p = tr[p][s[i] - 'a'];
        }
        e[p]++;// 节点为p的字符串的个数
    }
    queue<int> q;
    void build() {
        for (int i = 0; i < 26; i++) {
            if(tr[0][i]) {// 最初的首字母入队
                q.push(tr[0][i]);
            }
        }
        while (!q.empty()) {
            int p = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                if (tr[p][i]) {
                    fail[tr[p][i]] = tr[fail[p]][i];// 有子节点，将子节点的fail指向父节点fail指向的节点
                    q.push(tr[p][i]);
                } else {
                    tr[p][i] = tr[fail[p]][i];// 无该子节点，将该子节点指向父节点fail指向的节点
                }
            }
        }
    }
    int query (char *s) {
        int p = 0, res = 0;
        for (int i = 0; s[i]; i++) {
            p = tr[p][s[i] - 'a'];
            for (int j = p; j > 0 && e[j] != -1; j = fail[j]) {
                res += e[j];
                e[j] = -1;
            }
        }
        return res;
    }
}
char s[MAX];
int main(){
    fast;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        ac::insert(s);
    }
    cin >> s;
    ac::build();
    cout << ac::query(s);
    return 0;
}

杂项

对拍器

对拍用咯！！

1
2
3
4
5
6
7
8
9
10
11
g++ mkd.cpp -o mkd -g -std=c++20 
g++ std.cpp -o std -g -std=c++20 
g++ bl.cpp -o bl -g -std=c++20 
:loop
    mkd.exe >_data.txt
    std.exe <_data.txt >_Wrong.txt
    bl.exe <_data.txt >_Right.txt
    fc _Wrong.txt _Right.txt
if not errorlevel 1 goto loop
pause
goto loop

离散化

使用场景

在数据规模较大（大于数组能开的范围），只需要数据的相对关系，而不需要数据的具体值时，我们可以使用离散化

代码

  • STL版
1
2
3
4
5
6
for(int i=1;i<=n;i++)
 scanf("%d",p+i),b[i]=p[i];// 建立两个相同的数组
sort(b+1,b+n+1); 
int m = unique(b + 1, b + n + 1) - b - 1;// 去重，指向最后一个相同的数，所以要-1
for(int i=1;i<=n;i++)
 p[i]=lower_bound(b+1,b+m+1,p[i])-b;// 在第二个数组中找出当前值，获取该值的下标（相对位置）
  • 非STL版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int a[MAX];// 源数据数组
int A[MAX];// 离散化数组
int n;// 数组长度
int cmp(int i, int j) {
    return a[i] < a[j];// 点睛之笔，用源数据来进行离散数组的排序，这样离散数组就会排出来源数据的相对大小

}

for (int i = 1; i <= n; i++) {
    cin >> a[i];
    A[i] = i;// 初始化相对位置

    // 例：
    // a: 3 2 7 5
    // A: 1 2 3 4
}
sort(A + 1, A + 1 + n, cmp);
// A: 2 1 4 3

逆序对

特征

设有一个序列{a_1, a_2, a_3,…a_{n-1}, a_n},对于序列中任意两个元素ai,aj，若i<j,ai>aj，则说明ai和aj是一对逆序对。下面给出求逆序对的数量代码

  • 归并排序做法
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
int n,a[500010],c[500010];
long long ans;

void msort(int b,int e)//归并排序
{
    if(b==e)  
  return;
    int mid=(b+e)/2,i=b,j=mid+1,k=b;
    msort(b,mid),msort(mid+1,e);
    while(i<=mid&&j<=e)
     if(a[i]<=a[j])
      c[k++]=a[i++];
     else
      c[k++]=a[j++],ans+=mid-i+1;//统计答案
    while(i<=mid)
     c[k++]=a[i++];
    while(j<=e)
     c[k++]=a[j++];
    for(int l=b;l<=e;l++)
     a[l]=c[l];
} 

int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)
     scanf("%d",&a[i]);
    msort(1,n);
    printf("%lld",ans);
    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
int n;
int tree[MAX];
int a[MAX], b[MAX];
inline int lowbit(int x) {
    return x & (-x);
}
inline void update(int i, int x) {
    for (; i <= n; i += lowbit(i)) {
        tree[i] += x;
    }
}
inline int query(int i) {
    int res = 0;
    for (; i; i-= lowbit(i)) {
        res += tree[i];
    }
    return res;
}
int main(){
    fast;
    cin >> n;
    ll res = 0;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + n + 1);
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(b, b + n + 1, a[i]) - b;
        update(x, 1);
        res += i - query(x);
    }
    cout << res;
    return 0;
}

动态规划

最值型

题意：给定几枚硬币，最少用几枚能拼出目标钱数

动态规划组成部分

1. 确定状态
  • 最后一步： (最优策略中使用的最后一枚硬币$a_k$)
  • 子问题： (最少的硬币拼出更小的面额$21-a_k$)
2. 转移方程

假设现在有2，5,7三种面额的钱

  • $f[x] = min(f[x-2]+1,f[x-5]+1,f[x-7]+1)$
3. 初始条件和边界情况
  • 初始条件$f[0] = 0$,如果不能拼出Y,f[Y]=正无穷
  • 无边界情况

计数型

题意：给定一个m行n列的网格，一个机器人从左上角(0,0)位置出发，每次只能向右或向下走一步，问走多少种不同的方式从左上角走到右下角

动态规划组成部分

1. 确定状态
  • 最后一步:无论机器人如何到达右下角，一定在上一步中挪过来的(向右或向下)
  • 右下角坐标设为(m-1,n-1)
  • 前一步一定在(m-2,n-1)或者(m-1,n-2)上
  • 子问题：如果机器人有X种方式从左上角走到(m-2,n-1),Y种方式从左上角走到(m-1,n-2)，则机器人有X+Y种方式走到(m-1,n-1)
  • 状态:设f[i][j]为机器人有多少种方式从左上角走到(i,j)
2. 转移方程
  • $f[i][j]=f[i-1][j]+f[i][j-1]$
3. 初始条件和边界情况
  • 初始条件：f[0][0]=1，机器人只有一种方式走到左上角
  • 边界情况：f[i][0]=1,f[0][j]=1,每行每列只能一路走过来，因此也只有一种方式

存在型

题意：有n块石头分别在x轴的0,1，……，n-1位置，一只带黑框眼镜的青蛙在石头0上想跳到n-1上，如果ta在第i块石头上，ta最多可以向右跳距离$a_i$，问ta能否跳到n-1

例子：

  • $输入：a=[2,3,1,1,4]$
  • $输出：True$
  • $输入：a=[3,2,1,0,4]$
  • $输出：False$

动态规划组成部分

1. 确定状态
  • 最后一步：如果能从i跳过来，那么青蛙一定能跳到i并且最后一步不超过能跳过来的最大距离$n-1-i<=a_i$
  • 子问题：能否跳到当前位置
  • 状态:设f[j]表示能否跳到石头j
2. 转移方程
  • $f[j]=OR_{0<=i<j}(f[i]ANDj-i>=a[i])$
3. 初始条件和边界情况
  • 初始条件：f[0]=True 第一块石头一定能跳上去
  • 无边界情况

坐标型

1.题目：最长上升连续子序列
题意：给定一个数组，求出最长的连续子序列（单调上升或下降）

动态规划组成部分

1. 确定状态
  • 最后一步：对于最优策略，一定有最后一个元素a[j]，如果子序列长度大于1，那么最优策略a[j]的前一个元素肯定是a[j-1]，使得$a[j-1]<a[j]$
  • 子问题： 要求以a[j]结尾的最长连续上升子序列,那么就要求以a[j-1]结尾的最长连续上升子序列
  • 状态：设f[j]=以a[j]结尾的最长连续上升子序列的长度
2. 转移方程
  • $f[i]=max(1,f[i-1]+1ANDa[j-1]<a[j])$
3. 初始条件和边界情况
  • 初始条件：无
  • 边界情况：前面的数存在，并且前面的数小于当前数
4. 空间优化

由于转移方程只涉及到i与i-1,所以我们可以用一个长度为2的滚动数组优化

1
2
3
4
5
int f[2],now=0,old=0;
for(int i=0;i<n;i++){
    old=now;
    now=1-old;//交换顺序，滚动起来
}

2.题目：最小路径和
题意：

  • 给定m*n的网格，每个格子（i,j)里都有一个非负数A[i][j]
  • 求一个从左上角到右下角的路径，每一步只能向右或向下走，求所有路径中最小的路径和

动态规划组成部分

1. 确定状态
  • 最后一步：一定是从上面或左面的总和最小过来的
  • 子问题： 要求(m-1,n-1)的最小路径和，需要知道(m-1,n-2),(m-2,n-1)的最小路径和加上(m-1,n-1)的大小
  • 状态：设从(0,0)走到(i,j)的最小数字总和f[i][j]
2. 转移方程
  • $f[i][j]=min(f[i-1][j],f[i][j-1])+A[i][j]$
3. 初始条件和边界情况
  • 初始条件：f[0][0]=A[0][0]
  • 边界情况：第一行和第一列只能从一个方向过来
4. 空间优化

由于转移方程只涉及到两行或两列，所以我们可以用两行的滚动数组优化，详见戳我(～￣▽￣)→))￣▽￣)o
3.题目：炸弹袭击
题意：

  • 有一个M*N的网格，每个格子可能是空的，可能有一个敌人，可能有一堵墙
  • 只能在某个空格子里放一个炸弹，炸弹会炸死所有同行同列的敌人，但是不能穿透墙，问最多能炸死几个敌人

动态规划组成部分

1. 确定状态
  • 假设：所有的格子都能放炸弹
    • 有敌人的格子：格子里的敌人被炸死并且能够继续向四周爆炸
    • 有墙的格子：炸弹炸不死任何人
  • 在(i,j)格放一个炸弹，能够向上炸死的敌人数：（接下来以向上为例）
    • (i,j)为空地：能向上炸死(i-1,j)人
    • (i,j)为敌人:能向上炸死(i-1,j)+1人
    • (i,j)为墙：0
  • 最后一步：无
  • 子问题： 求(i,j)格能向上炸死的人数需要知道(i-1,j)格向上能炸死的敌人数
  • 状态：Up[i][j]表示(i,j)格放一个炸弹向上能炸死的敌人数
2. 转移方程
  • $f[n]=\begin{cases}
    Up[i-1][j],&if(i,j)格是空地\
    Up[i-1][j]+1,&if(i,j)格是敌人\
    0,&if(i,j)格是墙\
    \end{cases}$
3. 初始条件和边界情况
  • 初始条件：如果(0,j)格不是敌人，Up[0][j]=0,如果是敌人Up[0][j]=1;
  • 边界情况：同上
4. 程序

序列型(从下标1开始计算)

1.题目：房屋染色
题意：

  • 有一排N栋房子，每栋房子需要刷：红、蓝、绿其中一种颜色
  • 任何两栋相邻房子不能刷成同一颜色
  • 第i栋房子染成红、蓝、绿的花费分别是cost[i][0]，cost[i][1],cost[i][2]
  • 最少要花多少钱油漆这些房子

动态规划组成部分

1. 确定状态
  • 最后一步：最优策略中房子N-1一定染成 红、蓝、绿中的一种，而N-2栋房子一定不能和第N-1栋颜色一样（上一步的钱数与颜色两种因素共同影响当前步），所以我们需要再开一维来表示房子的颜色
  • 子问题：求出前N栋房子并且第N-1栋房子在红、蓝、绿颜色的最小花费
  • 状态：设油漆前i栋房子，并且第i-1栋房子是红、蓝、绿的最小花费为f[i][0],f[i][1],f[i][2]
2. 转移方程
  • $f[i][0]=min{f[i-1][1]+cost[i-1][0],f[i-1][2]+cost[i-1][0]}$
  • $f[i][1]=min{f[i-1][0]+cost[i-1][1],f[i-1][2]+cost[i-1][1]}$
  • $f[i][2]=min{f[i-1][0]+cost[i-1][2],f[i-1][3]+cost[i-1][2]}$
3. 初始条件和边界情况
  • 初始条件：f[0][0]=f[0][1]=f[0][2]=0 前0个什么都没有
  • 无边界情况

2.题目：房屋染色2
题意：

  • 有一排N栋房子，每栋房子需要刷K种颜色的一种
  • 任何两栋相邻房子不能刷成同一颜色
  • 第i栋房子染成第j种颜色的花费是cost[i][j]
  • 最少要花多少钱油漆这些房子

动态规划组成部分

1. 确定状态
  • 最后一步：与第一题相似，还是最后一栋与前一栋颜色不能一样所以我们需要再开一维来表示房子的颜色
  • 子问题：求出前N栋房子并且第N-1栋房子在K种颜色的最小花费
  • 状态：设油漆前i栋房子，并且第i-1栋房子是1,2……K颜色的最小花费为f[i][0],f[i][1],f[i][2]……f[i][k-1]
2. 转移方程
  • $f[i][j]=min_{k!=j}(f[i-1][k])+cost[i-1][j]$

-

3. 初始条件和边界情况
  • 初始条件：f[0][0]=f[0][1]=f[0][2]=……=f[0][k-1]=0 前0个什么都没有
  • 无边界情况
4.时间优化

在转移方程中，每次我们都需要在k不同于j颜色中找到$f[i-1][k]$的最小值，因此这块的时间复杂度为$O(k^2)$,我们可以将其优化到$O(k)$。我们可以不用每次都查找最小值，而是把最小值与次小值都记录下来

如果最小值是第i个元素，次小值是第j个元素

  • 除掉的是第i个元素以外的元素，最小值就是第i个元素
  • 除掉的是第i个元素，最小值就是第j个元素

最长序列型动态规划

1.题目：最长递增子序列
题意：

  • 给定一个数组，找出其中严格递增子序列的长度

动态规划组成部分

1. 确定状态
  • 最后一步：最优策略中以a[j]结尾的子序列一定是最长的
  • 子问题：本来求a[j]结尾的上升子序列，现在需要知道在它之前小于它的元素a[i]结尾的上升子序列
  • 状态：设f[i]是以a[i]结尾的最长上升子序列的长度
2. 转移方程
  • $f[j]=max(1,f[i]+1(a[i]<a[j]ANDi<j))$
3. 初始条件和边界情况
  • 初始条件：无
  • 边界情况：a[i]<a[j]ANDi<j

总结（坐标型与序列型动态规划的区分）

二者可互通

  • 如果第一项不需要空串向后生成，可以直接写出来dp，那么就可以用坐标型
  • 如果不是很清楚第0个元素该怎么处理，那么选用序列型比较合适

划分型

1.题目：解码方法
题意：

  • 有一段由A-Z组成的字母串被加密成数字串
  • 加密方式：A->1,B->2,……Z->26
  • 给定加密后的数字串S,问有多少种方式解密成字符串

动态规划组成部分

1. 确定状态
  • 最后一步：最后一个字母是最后一位数字还是最后两位数字转化成的
  • 子问题： 设数字串长度为N,要 求前N个字符的解密方式数，需要知道前N-1和前N-2个字符的解密方式数
  • 状态：设数字串S前i个数字解密成字母串有f[i]种方式
2. 转移方程
  • $f[i]=f[i-1]{S[i]对应一个字母}+f[i-2]{S[i-1]S[i]对应一个字母}$
3. 初始条件和边界情况
  • 初始条件：f[0]=1 空串有一种解密
  • 边界情况：如果i=1，只看最后一位数字(没有两位数)
4. 程序

2.题目：完全平方数
题意：

  • 给一个正整数n
  • 问最少用几个完全平方数组成n

动态规划组成部分

1. 确定状态
  • 最后一步：最后的数一定是由某个数的平方和与剩下的数组成
  • 子问题： 要求组成i的最小平方数需要比较出i减去一个平方数后的数需要的最小平方数组合的个数
  • 状态：设能够组成i的最少的完全平方数有f[i]个
2. 转移方程
  • $f[i] = min_{1<=j*j<=i}(f[i - j * j])+1$
3. 初始条件和边界情况
  • 初始条件：f[0] = 0
  • 边界情况：无
4. 程序

3.题目：分割回文串 II
题意：

  • 给一个字符串s
  • 问最少分成几个回文子串需要分割几次

动态规划组成部分

1. 确定状态
  • 最后一步：最优策略有最后一段回文串 S[j……N-1],
  • 子问题： 求前N个字符S[0..N-1]最少分为几个回文串，需要知道S前j个字符[0..j-1]最少可以划分成几个回文串
  • 状态：设S前i个字符[0..i-1]最少可以划分成f[i]个回文串
2. 转移方程
  • $f[i] = min_{0<=j<=i-1}(f[j]+1,S[j..i-1]是回文串)$
3. 初始条件和边界情况
  • 初始条件：f[0] = 0 ,空串被分成0个回文串（序列型）
  • 边界情况：无
4. 程序

4.题目：书籍复印
题意：

  • 有N本书待抄写，第i本书有A[i]页
  • 有k个抄写员，每个抄写员可以抄写连续的若干本书（每分钟抄一页）
  • 最少需要多长的时间抄完所有的书

动态规划组成部分

1. 确定状态
  • 最后一步：最后一个抄写员（第k个）抄写第j本到第N-1本书需要时间最短
  • 子问题： 求K个人最短多长时间抄完前N本书，需要知道K-1个人最少多长时间抄完前j本书
  • 状态：设f[k][i]为k个抄写员需要多长时间抄完前i本书
2. 转移方程
  • $f[k][i] = min_{j=0..i}max(f[k-1][j],A[j] +..+ A[i-1])$
3. 初始条件和边界情况
  • 初始条件：
    • f[0][0] = 0 零个抄写员抄0本书。f[0][1]..f[0][N] = +inf
    • f[k][0] = 0 每个抄写员花费0分钟抄0本书
  • 边界情况：k > N ,可以赋值 k = N
4. 动态规划程序

二分查找程序

小结

  • 要求将一个序列或字符串划分成若干满足要求的片段
  • 解决方法：最后一步->最后一段
    • 枚举最后一段的起点
  • 如果题目不指定段数，f[i]表示前i个元素分段后的可行性/最值：解码方法，完全平方数，分割回文串2
  • 如果题目指定段数，用f[i][j]表示前i个元素分成j段或前j个元素分成i段后的可行性/最值：书籍复印

博弈型（规模不大）

1.题目：硬币排成线
题意：

  • 给N个物品，重量都是正整数
  • 一个背包最大承重为M
  • 最多能带走多重的物品

动态规划组成部分

1. 确定状态
  • 第一步：在当前局面走出一步可以让对手陷入必败的局面则必胜，在当前局面无路可走则必败
  • 子问题：面对N个石子是否先手必胜，需要知道面对N - 1, N - 2个石子，是否先手必胜
  • 状态：设f[i]为面对i个石子是否先手必胜
2. 转移方程
  • $f[i] = f[i-1] == false OR f[i-2] == false$
3. 初始条件和边界情况
  • 初始条件：f[0] = false 面对0个石子先手必输，f[1] = f[2] = true面对1,2个石子，先手必胜
4. 程序

背包问题

1.题目：背包问题(可行性)
题意：

  • 有n个物品装入背包，重量均为正整数
  • 假设背包最多能承重m，最多能装多满

动态规划组成部分

1. 确定状态
  • 最后一个物品（重量$A_{N-1}$)是否放入背包
    • 情况1：如果前N-1个物品能拼出W,当然前N个物品也能拼出W
    • 情况2：如果前N-1个物品能拼出$W-A_{N-1}$,再加上最后的物品$A_{N-1}$，拼出W
  • 子问题：要求前N个物品能否拼出重量0,1…,M，需要知道前N-1个物品能否拼出重量0,1,…,M
  • 状态：设f[i][w]为能否用前i个物品拼出w
  • 注意：背包问题一定要把承重放入状态
2. 转移方程
  • $f[i][w] = f[i-1][w] OR f[i-1][w-A[i-1]]$
3. 初始条件和边界情况
  • 初始条件：f[0][0]=true 前0个物品可以拼出重量0
    • f[0][1..M]=false 0个物品拼不出大于0的重量
  • 边界情况：f[i-1][w-A[i-1]]只能在w>=A[i-1]时使用
4. 程序

2.题目：背包问题5（计数型）
题意：

  • 有n个正整数，一个正整数Target
  • 每个正整数只能用一次，求有多少种组合加起来是Target

动态规划组成部分

1. 确定状态
  • 最后一个物品（重量$A_{N-1}$)是否放入背包
    • 情况1：如果前N-1个物品能拼出W,当然前N个物品也能拼出W
    • 情况2：如果前N-1个物品能拼出$W-A_{N-1}$,再加上最后的物品$A_{N-1}$，拼出W
    • 情况1的方式数+情况2的方式数=用前N个物品拼出W的方式数
  • 子问题：要求前N个物品能否拼出重量0,1…,，需要知道前N-1个物品能否拼出重量0,1,…,Target
  • 状态：设f[i][w]为用前i个物品多少种方式拼出w
  • 注意：背包问题一定要把承重放入状态
2. 转移方程
  • $f[i][w] = f[i-1][w] + f[i-1][w-A[i-1]]$
3. 初始条件和边界情况
  • 初始条件：f[0][0]=1 前0个物品可以有一种方式拼出重量0
    • f[0][1..M]=0 0个物品拼不出大于0的重量
  • 边界情况：f[i-1][w-A[i-1]]只能在w>=A[i-1]时使用
4. 空间优化

5. 程序

空间优化过的程序
3.题目：背包问题2(最值型)
题意：

  • 有n个物品，每个物品都有重量和价值两个属性
  • 一个背包最大承重是正整数M
  • 最多能带走多大价值的物品

动态规划组成部分

1. 确定状态
  • 最后一个物品（重量$A_{N-1}$价值$V_{N-1}$)是否放入背包
    • 情况1：如果前N-1个物品能拼出W,最大总价值是V当然前N个物品也能拼出W并且总价值是V
    • 情况2：如果前N-1个物品能拼出$W-A_{N-1}$最大总价值是V,再加上最后的物品（重量$A_{N-1}$价值$V_{N-1}$)，拼出W，总价值为$V + V_{N-1}$
    • 情况1的方式数+情况2的方式数=用前N个物品拼出W的方式数
  • 子问题：要求前N个物品能否拼出重量0,1…,M,以及拼出重量W能获得的最大价值，需要知道前N-1个物品能否拼出重量0,1,…M,以及拼出重量W能获得的最大价值
  • 状态：设f[i][w]为用前i个物品拼出w时获得的最大价值(-1表示无法拼出)
  • 注意：背包问题一定要把承重放入状态
2. 转移方程
  • $f[i][w] = max(f[i-1][w], f[i-1][w-A[i-1]] + V[i-1] |w >= A[i-1] AND f[i-1][w-A[i-1]] != -1)$
3. 初始条件和边界情况
  • 初始条件：f[0][0]=0 前0个物品可以有一种方式拼出重量0,价值为0
    • f[0][1..M]=-1 0个物品拼不出大于0的重量
  • 边界情况：f[i-1][w-A[i-1]]只能在w>=A[i-1]时使用
4. 程序

空间优化过的程序
4.题目：背包问题3(最值型)
题意：

  • 有n种物品，每种物品都有重量和价值两个属性
  • 每种物品都有无穷多个
  • 一个背包最大承重是正整数M
  • 最多能带走多大价值的物品

动态规划组成部分

1. 确定状态
  • 与背包2几乎一致，区别在于每次可以将一个物品放多次
  • 状态：设f[i][w]为用前i个物品拼出w时获得的最大价值(-1表示无法拼出)
  • 注意：背包问题一定要把承重放入状态
2. 转移方程
  • $f[i][w] = max(f[i-1][w], f[i-1][w-kA[i-1]] + kV[i-1] |kw >= A[i-1] AND f[i-1][w-kA[i-1]] != -1)$
  • 优化：f[i][w] = max(f[i-1][w], f[i][w-A[i-1]] + V[i-1] |w >= A[i-1] AND f[i-1][w-A[i-1]] != -1)$
3. 初始条件和边界情况
  • 初始条件：f[0][0]=0 前0个物品可以有一种方式拼出重量0,价值为0
    • f[0][1..M]=-1 0个物品拼不出大于0的重量
  • 边界情况：f[i-1][w-A[i-1]]只能在w>=A[i-1]时使用
4. 空间优化

5. 程序

空间优化过的程序

小结

  • 可行性背包
    • 题面：要求不超过Target时能拼出的最大重量
    • 记录f[i][w]=前i个物品能否拼出重量w
  • 计数型背包
    • 题面：要求有多少种方式拼出重量Target
    • 记录f[i][w]=前i个物品有多少种方式拼出重量w
  • 最值型背包
    • 题面：要求能拼出的最大价值
    • 记录f[i][w]=前i个物品能拼出重量w能获得的最大价值
  • 关键点
    • 最后一步
      • 最后一个背包里的物品是哪一个
      • 最后一个物品有没有放进背包
    • 数组大小和最大承重Target有关

区间型

1.最长回文子串
题意：

  • 一个字符串S,长度为N
  • 找到它最长的回文子序列的长度

动态规划组成部分

1. 确定状态
  • 子问题：要求S[i..j]的最长回文子串
  • 若S[i]=S[j],需要知道S[i+1..j-1]的最长回文子串(两边的字符相等)
  • 否则答案是S[i+1..j]或S[i..j-1]的最长回文子串(两边的字符不等)
  • 状态：设f[i][j]为S[i..j]的最长回文子串长度
2. 转移方程
  • $f[i][j] = max(f[i+1][j],f[i][j-1],f[i+1][j-1]+2 | s[i]=s[j])$
3. 初始条件和边界情况
  • 初始条件：f[0][0]=f[1][1]=…=f[n-1][n-1]=1(一个字母为长度为1的回文子串)
  • 如果s[i]==s[i+1],f[i][i+1]=2
  • 如果s[i]!=s[i+1],f[i][i+1]=1
4. 计算顺序

按照长度j-i，从小到大计算

5. 程序

2.题目：完全平方数
题意：

  • 给一个正整数n
  • 问最少用几个完全平方数组成n

动态规划组成部分

1. 确定状态
  • 最后一步：最后的数一定是由某个数的平方和与剩下的数组成
  • 子问题： 要求组成i的最小平方数需要比较出i减去一个平方数后的数需要的最小平方数组合的个数
  • 状态：设能够组成i的最少的完全平方数有f[i]个
2. 转移方程
  • $f[i] = min_{1<=j*j<=i}(f[i - j * j])+1$
3. 初始条件和边界情况
  • 初始条件：f[0] = 0
  • 边界情况：无
4. 程序
赏

来根小鱼干好吗o( =·ω·= )m

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

20级的菜鸡，一条咸鱼，圈子小，由于天赐の礼物——脸盲，不认识几个人，只要你主动一点点我们就有故事⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄。