c0per 的博客

发牢骚和写点**文章的地方。

0%

NOI2019 退役记

NOI2019 是本蒟蒻的最后一次 NOI ,为了这次 NOI 提前停了将近一年的课,在外地培训了三个月。

虽然水平可能没什么太大的提高,幸而在考场上疯狂骗分,水了一块银牌。

比赛的时间安排比想象中紧张很多, Day2 的下午便开始和各个大学“签约”,第二天一大早就赶上了高铁,开始了漫漫回乡路。

一切都在眨眼间掠过,仿佛昨天还前天还挤在常州的小宾馆里训练,昨天才刚刚来到广州,感叹气候无比地湿热,今天便已坐在家中窗前。

直到学校开学的前一天,掏出电脑开始写退役博客时,才缓过神来:明天我就要去上课了,竞赛生涯已经结束了。

上下界网络流

每天边都有流量上界和下界的网络流题目。

无源汇

可行流

我们将每条边拆分成必须流的部分(红)和可选的部分(黑)。

为了保证红色的边必须满流,建立2个超级源点,汇点\(S,T\)。并建立如下的新图。

二分图进阶指南

前置知识:匈牙利算法,zkw费用流,Floyd传递闭包

基本概念

二分图:

指顶点可以分成两个互斥的独立集\(U\)\(V\)的无向图,也就是在任两个同在\(U\)\(V​\)的顶点间没有边。

阅读全文 »

线性基学习笔记

什么是线性基?

基在数学中指用于刻画向量空间的一组向量,该空间内的所有向量都可以通过基来表示。

oi中的线性基常在异或运算中出现。含义为可以表示\(n\)个数的异或运算结果的若干个数。

设存在\(n\)个数\(a_1,a_2,a_3...a_n\)。取出若干个数进行异或操作,最多有\(2^n\)种结果。

\(n​\)个数的线性基为\(k​\)个数\(b_1,b_2,b_3...b_k​\)。取出若干个数进行异或操作,其所得结果与前面相同。

\(k\)取最小值时,这\(k​\)个数被称为原数的线性基。

阅读全文 »

EK费用流,zkw费用流入门

什么是费用流?

在普通的网络流中,每一条边拥有相应的费用,即没有一单位的流量,就会产生一单位的费用。

在满足最大流的前提下,满足总费用最小,即\(\sum_{i \in E}f_i\)最大,\(\sum_{i \in E}f_i*c_i\)最小。

阅读全文 »

AC自动机详解

不是自动AC机

算法简介

啥是自动机?啥是AC自动机?

本蒟蒻对自动机并没有什么像样的理解,只知道AC自动机可以处理多个模式串在文本串中的匹配问题。

对于一般的匹配算法(KMP)只能一次处理单个模式串,而AC自动机可以做到快速的多模式串匹配。

前置技能:

阅读全文 »

为自建的网站增加https支持

使用acme.sh获取SSL证书

Let's Encrypt提供的SSL证书不仅免费,且支持泛域名,是十分便利的选择,唯一的缺点是证书只有60天的有效期。而acme.sh实现了acme协议,可以完成从申请到续签的一系列操作,我们使用acme.sh来管理证书。

安装acme.sh

1
curl  https://get.acme.sh | sh

acme.sh会被安装在~/.acme.sh/中,并创建cronjob,每天0点检查证书是否将过期并重新申请。

阅读全文 »