有且仅有一个源点 $s \in V$ ，有且仅有一个汇点 $t \in V$ ，且 $s\not = t$
有一个函数 $c: V \times V \to R^+$ ::success 每一条边对应容量 $c(u,v)$ ::
- 如果 $(u,v) \in E$ 且 $(v,u)\not\in E$ 则 $c(v,u) = 0$

$(u,v)$ 可称为弧

$c(u,v)$ 为弧的容量

可以类比水流，有很多只能单向流水的水管组成网络，水管有粗细 $c$

有一个有无限水流进入的源点 $s$ ，和无限水流出的汇点 $t$

2018-07-07发表2020-11-21更新OI / 学习笔记

动态规划-矩阵加速

¶ 矩阵乘法

\left\{ \begin{aligned} 2x + y = 3 \\ 3x + 2y = 9 \end{aligned} \right.

可表示成

\begin{bmatrix} 2 & 1 \\ 3 & 2 \end{bmatrix} \times \begin{bmatrix} x \\ y \end{bmatrix}= \begin{bmatrix} 2x+y \\ 3x+2y \end{bmatrix}

$A$ 是 $m\times n$ 矩阵， $B$ 是 $n\times p$ 矩阵。

2018-06-12发表2020-11-21更新OI / 题解

「NOIP 2008」传纸条

题目链接

为了方便，坐标先行后列。

设 $A = (1, 1),B = (m, n)$

不考虑不能传相同同学

从 A 到 B 再从 B 到 A $\sim$ 从 A 同时考虑两条路到 B

设 $i$ 为 A 到 B 线路 1 的行号， $j$ 为 A 到 B 线路 2 的行号， $k$ 为当前行列之和

对于线路1， $(i, k-i)$ 可从 $(i-1, k-i)$ 和 $(i, k-i-1)$ 推得

对于线路2， $(j, k-j)$ 可从 $(j-1, k-j)$ 和 $(j, k-j-1)$ 推得

故对于 $dp(i, j, k)$ 有四种情况。

\begin{aligned} dp(i, j, k) = a[i][k-i] + a[j][k -j] + \max\{ & dp(i, j, k-1), \\ & dp(i-1,j-1,k-1), \\ & dp(i-1,j,k-1), \\ & dp(i-1,j-1,k-1)\} \\ \end{aligned}

2017-11-04发表2020-11-21更新OI / 题解

奶牛玩杂技

非常棒的贪心题，我是完全没有想到解法。看了一波题解，证明如下：

若现在要处理两头牛 $a$ , $b$ 记 $w$ , $s$ 分别为 $w_a$ $s_a$ $w_b$ $s_b$

2017-10-29发表2020-11-21更新OI / 题解

「NOIP 2004」合唱队形

记忆化搜索

定义一个 solve(x, lim, dir)

x 表示处理完的层数，所有x == n是就return

lim 是限制条件

dir 表示方向，true为向上，false向下

当 dir == true 时，显然有以下情况

若 height[x+1] > lim
选 solve(x+1, height[x+1], true)
不选 solve(x+1, lim, true)
若 height[x+1] < lim
不选 solve(x+1, lim, true)
选，并改方向 solve(x+1, lim, false)
若 height[x+1] == lim
只能跳 solve(x+1, lim, false)

当 dir == false时，不能再换方向，显然有以下情况

若 height[x+1] > lim
不选 solve(x+1, lim, false)
若 height[x+1] < lim
选 solve(x+1, height[x+1], false)

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
int t[101], dp[101][231][2], n, ans=200;
int solve(int x, int max,bool dir){
    if (x == n){
        return 0;
    }
    if (dp[x][max][dir]!=-1) return dp[x][max][dir];
    int& ans = dp[x][max][dir];
    if (dir){
        if (t[x+1] < max) return ans = std::min(solve(x+1,max,true)+1,solve(x+1,t[x+1],false));
        if (t[x+1] > max) return ans = std::min(std::min(solve(x+1,t[x+1],true),solve(x+1,max,true)+1), solve(x+1,t[x+1],false));
        return ans = solve(x+1,max,true)+1;
    }else{
        if (t[x+1] < max) return ans = std::min(solve(x+1,t[x+1],false),solve(x+1,max,false)+1);
        if (t[x+1] >= max) return ans = solve(x+1,max,false)+1;
    }
}
int main(){
    std::memset(dp, -1, sizeof(dp));
    int i;
    cin >> n;
    for (i=1;i<=n;++i)
        cin >> t[i];
    cout << solve(0,0,true);
    return 0;
}

2017-10-22发表2020-11-21更新OI / 题解

「洛谷 P1603」斯诺登的密码

这题其实没有什么好说的，暴力打表，然后注意一下

若输出的是一位数需补零
若输出的是零不用补成 00

#include <bits/stdc++.h>
std::map<std::string, int> map;
int main(){
    using std::cin;
    using std::cout;
    using std::endl;
    std::string s;
    long long i, ans=0;
    map.insert(std::make_pair("one", 1));
    map.insert(std::make_pair("two", 4));
    map.insert(std::make_pair("three", 9));
    map.insert(std::make_pair("four", 16));
    map.insert(std::make_pair("five", 25));
    map.insert(std::make_pair("six", 36));
    map.insert(std::make_pair("seven", 49));
    map.insert(std::make_pair("eight", 64));
    map.insert(std::make_pair("nine", 81));
    map.insert(std::make_pair("ten", 0));
    map.insert(std::make_pair("eleven", 21));
    map.insert(std::make_pair("twelve", 44));
    map.insert(std::make_pair("thirteen", 69));
    map.insert(std::make_pair("fourteen", 96));
    map.insert(std::make_pair("fifteen", 25));
    map.insert(std::make_pair("sixteen", 56));
    map.insert(std::make_pair("seventeen", 89));
    map.insert(std::make_pair("eighteen", 89));
    map.insert(std::make_pair("nineteen", 61));
    map.insert(std::make_pair("twenty",	 0));
    map.insert(std::make_pair("a", 1));
    map.insert(std::make_pair("both", 4));
    map.insert(std::make_pair("third", 9));
    map.insert(std::make_pair("second", 4));
    map.insert(std::make_pair("first", 1));
    map.insert(std::make_pair("another", 1));

    for (i=0;i<6;i++){
        cin >> s;
        if (map.count(s) != 0)
            ans = ans*100 + map[s];
    }
    if (ans < 10 && ans != 0) cout << '0';
    cout << ans;
    return 0;
}

矩阵

行列式

¶ 定义

Edmonds-Karp 算法

¶ 原理

网络流基础

¶ 定义

¶ 网络

动态规划-矩阵加速

¶ 矩阵乘法

「NOIP 2008」传纸条

奶牛玩杂技

「NOIP 2004」合唱队形

「洛谷 P1603」斯诺登的密码

分类

标签