2-SAT 问题

2015-12-14
介绍 现有 n n n 个布尔变量 x i x_{i} x ​ i ​ ​ ,给出一些限制关系,比如 x1为真或者 x2 为假 、 x3 为真或者 x5 为真 等(注意这里的‘或’是指至少有一个条件成立),SAT 问题是要确定 n ......

网络流之 - 消圈定理(POJ 2175)

2015-12-05
摸爬滚打研究了好几个小时,终于搞清楚了消圈定理,其实并不复杂。。 消圈定理 所谓消圈定理,就是在某个流 f f f 中,如果其对应的残余网络没有负圈(剩余流量为 0 0 0 的边视为不存在),那它一定就是当前流量下的最小费用流。反之亦然。即「 f f f 是......

绝对众数问题

2015-12-03
绝对众数。在数列 p p p 中出现次数严格大于 ∣ p ∣ 2 \frac{\vert p \vert}{2} ​ 2 ​ ​ ∣ p ∣ ​ ​ 的数叫做绝对众数。 求绝对众数 快速排......

网络流之 - 匹配、边覆盖、独立集、顶点覆盖

2015-12-01
在图论中,有以下几个概念,它们之间的关系往往容易弄混淆,这里稍稍证明一下。 先放出概念 - 来自日本人的书。 概念 匹配 : 在 G G G 中两两没有公共端点的边集合 M ⊆ E M \subseteq E M ⊆ E 边覆盖:在 G G G ......

UVa 257 - Palinwords

2015-11-29
题目地址 描述 问一堆单词中,哪些是 palinword 并输出。 palinword 的定义为,包含两个不同的回文子串,并且要求回文子串不能互相包含。例如 aaa 和 aaaa 只算一个。 规模 单个单词长度 l < = 2 5 5 l <= 255 l < = 2 5 5 ......

NOIP 2015 Day 2 详细题解

2015-11-22
感觉网上的题解很不全,只有只言片语,零零散散的,于是自己写了一份。 如果题目有些遗忘了,最好回忆一下题目再看题解。有些题目的解很可能不是最优的,欢迎各路神犇留言。 跳石子 题目地址 描述 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N ......

NOIP 2015 Day 1 详细题解

2015-11-21
感觉网上的题解很不全,只有只言片语,零零散散的,于是自己写了一份。 如果题目有些遗忘了,最好回忆一下题目再看题解。有些题目的解很可能不是最优的,欢迎各路神犇留言。 神奇的幻方 题目地址 描述 幻方是一种很神奇的 N × N N \times N N × N 矩阵:它由数字 ......

KMP 算法详细解析

2015-11-14
虽然说网上 KMP 算法的解析实在是太多太多,可我还是忍不住要写一篇,因为我不想用那些看似逼格满满,却将简单事情搞得超级复杂的式子来说明。 下面,请带着轻松的心情来看这篇文章。 字符串匹配算法 字符串匹配是计算机的进行的非常频繁的算法。简单的说,有一个字符串 I have a dream. 。我想知道的事情是,里面是否包含另一个字符串 dream ? 因为执行的非常频繁,所以算......

欧几里德算法与扩展欧几里德算法

2015-11-03
欧几里德算法非常简洁,明了,通俗易懂。 m ( m > 0 ) m(m > 0) m ( m > 0 ) 整除 n n n 记作 m ∣ n m \vert n m ∣ n ,其定义为存在一个整数 k ......

弹性碰撞

2015-10-25
最近做了一些弹性碰撞的题目,然而大多数的书或者博文都没有详细的分析,做的迷迷糊糊的。费尽心思搞懂之后,决定分享一下心得,其实并没有多难。 定义 弹性碰撞是指两个刚体(忽略大小)在同一直线上运动时,相撞没有能量损耗,交换各自的速度同时掉头运动。 基本思想 处理这种问题,首先要明白基本的两点: 引理一:忽略个体的差异,那么两个刚体相撞掉头可以看作保持原样运动擦身而过。 ......