玖的数学&算法录
0%

发表于 更新于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

受队友影响，也开始在博客更新自己补题的记录

(1/1000)

阅读全文 »

发表于 更新于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

本文参照邓丝雨所写的dp进阶之路所作的笔记，在此%%邓丝雨姐姐

1.介绍

1.1 基本思想

​ dp的核心是对一类求最优解问题的算法，其核心是将一个问题分解成若干个子问题，通过每一次最优决策，求得出一个最优解。

​

1.2 适用条件

三点：

1.具有相同的子问题：首先，我们必须要保证这个问题能够分解出若干个子问题，并且能通过这些子问题来解决这个问题。

2.满足最优化原理（最优子结构）：一个最优决策的子决策也是最优的。

3.具有无后效性：他要求每一个问题的决策，不能对未来问题产生影响，如果产生影响，就无法保证决策的最优性，这就是无后效性。

1.3 解题步骤

  1. 确定问题的子问题；

  2. 确定状态

  3. 推出状态转移方程（关键）

  4. 确定边界

  5. 优化

1.4 方法

  1. 根据dp的三要素，从而确定方向

1.1：先确定阶段的问题 ：数塔问题

1.2 ： 先确定状态的问题 ：常见问题

1.3 ： 先确定决策的问题 ：背包问题

2. dp

2.1 线性dp

2.1.1 LIS问题

LIS问题即最长上升子序列（Longest increasing Sequence）：给定一个长为N的数列A，求严格递增的子序列的最长长度是多少？

2.1.1.1 dp，O（n²）解法

首先每个单独的数列是一个子序列，长度为1，因此赋初值f[i]=1；

在此基础上，对i而言，设立一个j从最左扫描到i，去记录每一个比当前值a[i]小的数，通过f[i]来维护当前值。

以 {3 1 2 1 8 5 6}为例子

a[i] 3 1 2 1 8 5 6

len 1 1 2 1 3 3 4

对应的例子是

{3}

{1}

{1,2}

{1}

{1,2,8}

{1,2,5}

{1,2,5,6}

状态转移方程为：

$$\displaystyle dp[j]=\max_{1\leqslant i <j且len(i)<len(j)} dp[i]+1$$

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
2.1.1.2 贪心+二分 O（nlogn）解法

状态表示：dp[i]表示长度为i的上升子序列的最后一个元素的最小值，类似于维护最值的单调队列。

状态转移：

  • 若a[i] > a[len] ,那么dp[++len] = a[i]，即把当前的元素追加到后面，使得上升子序列len+1。
  • 2反过来，则在dp中查找大于等于a[i]的第一个数的下标pos，令dp[pos] = a[i]。

最后结果就是dp[len]（最长上升子序列的内容）

1
2
3
4
5
6
7
8
9
10
int n,dp[N],a[N];
int len=0;
for(int i=1;i<=n;i++)
{
	if(a[i]>a[len]) a[++len] = a[i];
	else
	{
		*lower_bound(dp+1,dp+len+1,a[i])=a[i];
	}
}

发表于 更新于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

lowbit

就

x&(-x)

树状数组

维护一个数组 a_1,..,a_n ，在 O(logn) 满足以下作用

1.单点加

2.查询前缀和

用c[n]来记录 其实应该满足$$\displaystyle c_i = a_{i - lowbit(i) + 1}$$

以前八个数来看就是：

c[1] = a[1]

c[2] = a[1] + a[2]

c[3] = a[3]

c[4] = a[1] + a[2] + a[3] + a[4]

c[5] = a[5]

c[6] = a[5] + a[6]

c[7] = a[7]

c[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]

1.单点加

1
2
3
4
5
6
7
8
9
10
11
#define ll long long
const int N = 201000;
int a[N];
ll c[N];
ll query(int x){
    ll s = 0;
    for(; x; x -= x & (-x)){
        s += c[x];
    }
    return s;
}

2.查询前缀和

1
2
3
4
5
6
7
8
9
#define ll long long
const int N = 201000;
int a[N];
ll c[N];
void modify(int x,ll s){
	for(; x <= n; x += x & (-x)){
		c[x] += s;
	}
}

额外补充：

3.区间加的写法：

1.在区间 [l,r] 内的原数组a 加上 d

易知$$\displaystyle d_{i} = a_{i} - a_{i - 1}$$

如果对**[l , r]** 都加上 x，那么区间内差分数组实际上不会发生改变，实际上只有 $$\displaystyle d[l] += x,d[r + 1] -= x$$

coding:

1
2
3
4
5
6
7
int l,r;
long long d;
std::cin >> l >> r >> d;
c1.modify(l,d);
c1.modify(r + 1, -d);
c2.modify(l, l * d);
c2.modify(r + 1, (r + 1) * (-d));

2.在区间加的情况下进行查询

不难知道：

$$\displaystyle a_1 = d_1$$

$$\displaystyle a_2 = d_1 + d_2$$

$$\displaystyle a_3 = d_1 + d_2 + d_3$$

易发现规律：

$$\displaystyle sum = x * d_1 + (x - 1) d_2 +\cdots + d_x$$

$$\displaystyle = \sum_{i = 1} ^ {x} (x + 1 - i) d_ i$$

$$\displaystyle = (x + 1) * \sum_{i = 1} ^ {x} d_i - \sum_{i = 1} ^ {x} i* d_i$$

coding:

1
ll ans = (x + 1) * c1.query(x) - c2.query(x)

封装的板子如下：

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
template <class T>
class Fenwick {
    const int n;
    std::vector<T> a;
public:
    Fenwick(int n) : n(n), a(n) { }
    void add(int x, T v) {
        assert(0 <= x < n);
        x ++;
        while (x <= n) {
            a[x - 1] += v;
            x += x & (-x);
        }
    }
    T sum(int x) {
        assert(0 <= x < n);
        T ans = 0;
        while (x > 0) {
            ans += a[x - 1];
            x -= x & (-x);
        }
        return ans;
    }
    T rangeSum(int l, int r) {
        assert(0 <= l <= r < n);
        return sum(r) - sum(l);
    }
};
单点修改：
1
2
void f.add(int x,T v)
a[x] += p;

复杂度：O(logN)

区间查询(Sum)：
1
T f.sum(int x)

查询 [0,x) 的区间和

时间复杂度：O(logN)

区间查询(rangeSum)：
1
T f.rangeSum(int l, int r)

查询 [l,r) 的区间元素和

线段树

建树+查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 201000;
struct node {
	int minv;
} seg[N * 4];

void update(int id) {
    seg[id].minv = std::min(seg[id * 2].minv, seg[id * 2 + 1].minv);
}

void build(int id,int l,int r){
    if (l == r){
        seg[id].minv = a[l];
    } else {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        update(id);
    }
}
//build(1, 1, n);

单点修改

1
2
3
4
5
6
7
8
9
10
11
12
//节点为id,对应区间为[l,r]，修改a[pos] -> val
void change(int id, int l, int r, int pos, int val) {
    if(l == r){
        seg[id].minv = val;
    } else {
        int mid = (l + r) / 2;
        if(pos <= mid) change(id * 2, l, mid, pos, val);
        else change(id * 2 + 1, mid + 1, r, pos, val);
        update(id);
    }
}
//change(1, 1, n, x, d);

查询最小值

1
2
3
4
5
6
7
8
9
10
int query(int id, int l, int r, int ql, int qr) {
    if(l == ql && r == qr) return seg[id].minv;
    int mid = l + r >> 1;
    if(qr <= mid) return query(id * 2, l, mid, ql, qr);
    else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    else {
        return std::min(query(id * 2, l, mid, ql, mid), query(id * 2 + 1, mid + 1, r, mid + 1, qr));
    }
}
//query(1, 1, n, l, r);

懒标记