网络流

有一部分复制的这篇 博客

最大流=最小割

1. 没开 longlong， 没有1ll

2. 数组开小

3. 数组开太大，没注意空间

4. 多测不清空

5. 注意模数不一定是 $1e9+7$

6. 数组越界。数组各维度空间开反

7. 数学和 $dp$ 先把式子写好再写代码

8. 注意变量名不要写错

9. 注意 $stl$ 容器的大小是 $ull$ 类型的.

[JSOI2009]球队收益（紫）

(https://www.luogu.com.cn/problem/P4307)

标签

网络流，差分

A

标签

位运算 + $FWT$

方法

1. 找出满足要求的最大值和最小值，考虑从最小值逐渐向最大值调整，或从最大值逐渐向最小值调整。

2. 找出一种特殊情况下的方案，在考虑把其它情况变成这种特殊情况。或者把其它情况分成多个这种特殊情况。

D 小P走迷宫

标签

$dp$​ + $lgv$​ 引理 + 计数

link

难度

思维难度 : 四星

代码难度 : 一星

标签

$dp$ + 矩阵乘法 + 组合意义 + 计数

题解

考虑组合意义，就是一个有 $n$ 个格子，$n + 1$ 个间隔，每个间隔可以放隔板，把格子分成一些部分。每个格子都可以放 $1-2$ 个球，红球或蓝球，最后要求每个部分都有且仅有一个红球和一个蓝球。其中有一些间隔不能放隔板。求方案数。

对于一种放隔板的方案，放球的方案数显然是 $\prod_{i=1}^{k}a_i^2$ ，不同的放隔板的方案显然和放正方形的方案一一对应。

所有放隔板和放球的总方案数就是原题所有合法方案的贡献之和。

那么考虑新问题如何计数。如果不是关键点的话,可以推出转移 $A$​：

$f[i][j] 表示dp到第 i 个格子,当前部分有 j 个球\\ f[i][0] = f[i-1][0] + f[i-1][2] (放隔板或不放隔板)\\ f[i][1] = 2f[i-1][0] + f[i-1][1] + 2f[i-1][2] (放一个球，放另一个球，放隔板后放一个球)\\ f[i][2] = f[i-1][0] + f[i-1][1] + 2f[i-1][2] (放两个球，放另一个球，放隔板后放两个球或什么都不放)\\$

可以直接矩阵快速幂.

是关键点的话容易推出另一种转移 $B$.

如果当前 $dp$ 到的位置是关键点，乘上转移矩阵 $B$​​​ ，否则乘上转移矩阵 $A$ 。

因为关键点的个数 $\leq 10^5$ ， 所以关键点之间的部分可以矩阵快速幂优化.

Code:

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

#include <iostream>
#include <vector>
#define int long long

using namespace std;

const int M = 2e5 + 10, mod = 1e9 + 7;
struct Marix {
  int date[3][3];

  Marix() {}

  Marix (int v) {
    for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) date[i][j] = 0;
    for (int i = 0; i < 3; ++i) date[i][i] = v;
  }

  int * operator [] (int i) {
    return date[i];
  }
  
  Marix operator * (const Marix b) {
    Marix c(0);
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        for (int k = 0; k < 3; ++k) {
          (c.date[i][j] += date[i][k] * b.date[k][j] % mod) %= mod;
        }
      }
    }
    return c;
  }
};

Marix qpow(Marix a, int b) {
  Marix res(1);
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cout.tie(NULL);
  cin.tie(NULL);
  Marix a, b, ans(1);
  a[0][0] = 1, a[0][1] = 2, a[0][2] = 1;
  a[1][0] = 0, a[1][1] = 1, a[1][2] = 1;
  a[2][0] = 1, a[2][1] = 2, a[2][2] = 2;
  b[0][0] = 1, b[0][1] = 2, b[0][2] = 1;
  b[1][0] = 0, b[1][1] = 1, b[1][2] = 1;
  b[2][0] = 0, b[2][1] = 0, b[2][2] = 1;
  int n, m;
  vector<int> mark;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x;
    cin >> x;
    mark.push_back(x);
  }
  int last = -1;
  for (auto it : mark) {
    int po = it - last - 1;
    last = it;
    ans = ans * qpow(a, po) * b;
  }
  ans = ans * qpow(a, n - last - 1);
  cout << ans[0][2] << endl;
  return 0;
}

总结

对于一些比较难计数的计数题, 可以考虑它的组合意义，一般都会转化为放球问题, 这时候就可以用比较简单的 $dp$ , 或熟悉的计数套路解决.

难度

思维难度 : 四星

代码难度：一星半

标签

计数 + 组合意义 + $dp$

link

难度

思维难度 : 三星
代码难度 ：二星

标签

$dp$ + $离散化$ + 计数

2021.8.6

[APIO2016]划艇

题目 博客
当 $dp$ 中涉及较大的值域时，可以考虑离散化后进行 $dp$ ，在 $dp$​ 时要注意很多细节。如要分别考虑之前状态和当前状态在同一区间和不同区间的情况。