RainAir
My OI Blog
RainAir


文章归档

「二分图模板」距离序列

题目描述 已知序列 $S={0,1,\cdots ,n-1}$,序列里有 $n$ 个数,从 $0$ 到 $n-1$。定义两个数 $x,y$ 的距离 $D(x,y) = min{|x-y|,N-|x-y|}$. 定义序列 S 的一个排列 T ,那么这两个序列的距离序列 $Q(S,T) = {D(S_0,T_0),D(S_1,T_1),\cdots,D(…

   258   2018-11-27 去围观

「BZOJ5028」小Z的加油店

题目描述 题目链接 小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子,每个瓶子有一个容量vi。每次别人来加油,他会让 别人选连续一段的瓶子。他可以用这些瓶子装汽油,但他只有三种操作: 1. 把一个瓶子完全加满; 2. 把一个瓶子完全倒空; 3. 把一个瓶子里…

   329   2018-11-24 去围观

Dinic 学习笔记

Dinic 是一种网络最大流的算法。 引入 网络流的本质是线性规划。 定义:有向图 $(V,E)$ 存在源点 $S \in V$ 和汇点 $T \in V,S \neq T$,每条边都有一个容量 $c$。 对于任意一个时刻,设 $flow(u,v)$ 表示实际流量,则整个图 $G$ 的流网络满足如下性质: 1. 容量限…

   373   2018-11-22 去围观

AGC027C – ABland Yard

题目描述 题目链接 给出一个 $N$ 个点、 $M$ 条边的无向图(节点编号 $1~N$ )。每个节点有一个值 A 或 B,你可以从任意一个节点出发,经过一些节点后(可以重复经过),你将经过的节点的值顺次写出来,就可以得到一个只包含 A 或 B 的字符串。求对于只包含 A 或 B 的…

   200   2018-11-22 去围观

「NOI2010」航空管制

题目描述 题目链接 有 $n$ 个航班依次起飞,一个时刻只能有一个飞机起飞,并且有 $m$ 个限制: 1. 第一种限制,第 $i$ 个飞机必须在 $c_i$ 的时刻前起飞。 2. 第二种限制,第 $i$ 个飞机必须在第 $j$ 个飞机之前起飞。 询问: 1. 一个可行的起飞方案。 2. 每个飞机最早…

   269   2018-11-21 去围观

HDU 5215 Cycle

题目链接 题目描述 给定一张无向图,判断是否存在奇环和偶环。 $n \leq 100000,m \leq 300000$ 题解 这是一个二合一的题目。 首先我们考虑如何判断奇环,注意到一个性质:如果一个图有奇环,那么这个图不能被二分图染色。 那么判断奇环只需要二分图染色一遍就可以…

   238   2018-11-21 去围观

HDU 5306 Gorgeous Sequence

题目链接 题目描述 (本人喜欢用 Vjudge 所以就放那里的链接啦。 给定一个序列,要求实现区间求最大值,区间求和,区间对一个数取min。 解题报告 开始挖十一集训的坟了...... 这一题是吉司机线段树模板题的简化版本。 大家都会维护最大值和和,怎么实现那个取min…

   256   2018-11-18 去围观

NOIP 2018 SD游记

咕了一周之后来写一片游记...... 先照例 Orz 吊打我的 Logey Day0 考前坚信不玩炉石传说,为自己奶了一口。 感觉考在正睿前刷了 $50$ 套模拟赛应该没问题吧? 坐在车上一边骂着**司机不走高速,一边低头颓着手机然后下车的时候头好晕,手机也没电了。 抽到了外校,又…

   753   2018-11-18 去围观

「NOIP2017」宝藏

题目链接 Luogu P3959 这一题有两种做法:状压dp和模拟退火 解题思路 看到这一道题目的时候,我的第一反应就是:裸的Prim啊! 但仔细思考了一下,发现事情没有那么简单: 长度和层数都对后面的结果有影响,所以不能贪心的求Prim,贪心会导致局部最优…

   319   2018-11-08 去围观

「NOIP2016」天天爱跑步

题目链接 NOIP 史上最毒瘤的一个题目......花了 2h 总算肝出来了。 解题报告 暴力测试点 大力枚举时间然后统计答案就可以了…….简单的模拟题目。 期望得分 $25$ 分。 链情况 考虑链情况的每一个人只能向左或向右走,也就是 $s \leq t$ 向右,否则向左。我们考…

   403   2018-11-08 去围观
文章归档