更新于: | 阅读次数: | 评论数:
字数统计: 2k | 阅读时长 ≈ 9

Dinic算法

例题:CodeVS 1993 草地排水

题目描述 Description
在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。

农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。

根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

阅读全文 »

更新于: | 阅读次数: | 评论数:
字数统计: 838 | 阅读时长 ≈ 3

阶梯博弈

阐述

阶梯博弈也是博弈论中重要的一个分支，所谓阶梯博弈，其实指代的是一类只能从后向前逐层传递石子的游戏的模型，同样的，这类问题也可以转化成NIM取石子问题求解

题型

前五堆石子分别有2,1,3,1,4个石子，每个人只能把后面的任意多个石子向前移，不能移动者为负，现在问先手必胜还是必败？

阅读全文 »

更新于: | 阅读次数: | 评论数:
字数统计: 94 | 阅读时长 ≈ 1

安装venv

1
python3 install virtualenv

venv的使用

  • 在当前目录创建虚拟环境
1
python3 -m venv .
阅读全文 »

更新于: | 阅读次数: | 评论数:
字数统计: 1.2k | 阅读时长 ≈ 5

筛法求素数

基本步骤

说到求素数，其实在刚开始学C++的时候就已经见过诸如此类的问题，不过现在最常见的还是筛法求素数

谈及筛法求素数，其大致思路可分为如下五步：

  1. 把2到n的自然数放入a[2]到a[n]中(所放入的数与下标号相同) ;
  2. 在数组元素中以下标为序，按顺序找到未曾找过的最小素数minp和它的位置p(即下标号);
  3. 从p+1开始，把凡是能被minp整除的各元素值从a数组中划去(筛掉)，也就是把该元素标记为0;
    阅读全文 »

更新于: | 阅读次数: | 评论数:
字数统计: 1.2k | 阅读时长 ≈ 5

问题简介

错排问题，又称更列问题，是组合数学中的问题之一。对于它的研究最早可以追溯到十八世纪，当时他被数学家尼古拉·伯努利和欧拉研究，因此在历史上也被称为伯努利—欧拉的错装信封问题。这个问题有许多具体的版本，比如在写信时讲n封信装到n个不同的信封里，有多少种全部装错信封的情况？再比如n个人各写一张贺卡相互赠送，有多少种赠送方法？这些经典的题目都是典型的错排问题。

阅读全文 »