Dawn-K's Blog

「CodeNote」 CF1249E(思维+dp)

CF1249E By Elevator or Stairs? 题意给你一个n层的楼房,上楼有两种方式,一种是楼梯,一种是电梯.给出数组a[i]表示i到i+1层走楼梯所需要的时间,b[i]表示走电梯的时间,但是走电梯的情况下,进电梯和出电梯所需要的额外等待的时间是c. 如果使用楼梯从x层到y层需要 $\sum_{i=min(x,y)max(x,y)−1}^{max(x,y)...

Posted by Dawn-K's Blog on October 24, 2019

「CodeNote」 CF1249D1(思维+set+线段覆盖)

CF1249D1 题目链接题意给出一个x轴(可以假想x轴的范围是[1,2e5]),然后给出n,k. 接下来给出n个线段的l,r.添加到x轴上. 要求删除一些线段,使得在[1,2e5]范围内,任何一个点上覆盖的线段数量<=k. 第一行输出删除的条数, 第二行删除的每一条的编号(任意顺序). $1<=k,n,l_i,r_i<=2e5$ 思路这个题一开始...

Posted by Dawn-K's Blog on October 24, 2019

「CodeNote」 HDU1045(二分图匹配+行列缩点建图)

Fire Net Problem Description Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall. ...

Posted by Dawn-K's Blog on October 23, 2019

「CodeNote」网络流入门

网络流入门参考资料-洛谷题解介绍网络流网络流:所有弧上流量的集合f={f(u,v)},称为该容量网络的一个网络流. 网络流图:带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flow network)：仅有一个入度为0的顶点s，称s为源点仅有一个出度为0的顶点t，称t为汇点每条边的权值都为非负数，称为该边的容量，记作c(i,j)。弧的流...

Posted by Dawn-K's Blog on October 22, 2019

「CodeNote」 JAVA高精度浮点数

JAVA高精度浮点数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 // import com.sun.corba.se.impl.resolver.SplitL...

Posted by Dawn-K's Blog on October 22, 2019

「CodeNote」 HDU1281(二分图匹配+行列建图)

棋盘游戏题目链接题意小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。所以现在Gardon想让小希来解决一个更难的问题，在保证尽量多的“车”的前提下，棋盘里有些格子是可以避...

Posted by Dawn-K's Blog on October 22, 2019

「CodeNote」二分图匹配

二分图匹配崔添翼参考资料参考资料2 介绍二分图二分图是一种图论的景点模型.二分图由两个点集U,V组成.点集内部不存在边,点集之间存在边. 匹配给定一个二分图G,在G的一个子图M的点集E中,任何两个边不依附于同一个顶点,则称M是一个匹配. 特别地,如果无法通过增加未匹配的边来进一步增大匹配的边数,则称M为极大匹配. 极大匹配不唯一,他们中边...

Posted by Dawn-K's Blog on October 7, 2019

「CodeNote」 tarjan求LCA

tarjan求LCA 介绍第三种求LCA的方法,离线的. 但是实现时如果用STL,就还不如在线的算法快(已在洛谷实验过). 算法算法是这样的,首先建图,然后将查询用邻接表的方式存下. 然后从根节点进行dfs,然后每访问到一个节点,就标记.在访问了一个节点u的过程中,将它的子节点都dfs一下.然后用并查集将u,v合并(u作为父亲) 然后处理完节点u的所有子节点之后,开始进行处...

Posted by Dawn-K's Blog on October 5, 2019

「CodeNote」倍增求LCA

倍增求LCA 参考资料介绍 LCA的求法已经在之前的笔记中记载过,一共有三种. ST表.预处理时空复杂度都是O(nlogn),单次询问O(1).在线倍增法.预处理时空复杂度O(nlogn),单次询问O(logn).在线 tarjan.复杂度O(n+q).离线倍增倍增是一种对暴力的优化方式. 我们用p[i][j]表示i号节点的第$2^j$ 层祖先(j=0时...

Posted by Dawn-K's Blog on October 2, 2019

「CodeNote」双连通分量

双连通分量参考资料参考资料2 [TOC] 介绍若一个无向连通图不存在割点，则称它为“点双连通图”。若一个无向连通图不存在割边，则称它为“边双连通图”。无向图的极大点双连通子图称为“点双连通分量”，简记为“v-DCC”。无向连通图的极大边双连通子图被称为“边双连通分量”，简记为“e-DCC”。二者统称为“双连通分量”，简记为“DCC”。树的割顶 (割顶和割点没区...

Posted by Dawn-K's Blog on October 1, 2019

Dawn-K's Blog

「CodeNote」 CF1249E(思维+dp)

「CodeNote」 CF1249D1(思维+set+线段覆盖)

「CodeNote」 HDU1045(二分图匹配+行列缩点建图)

「CodeNote」网络流入门

「CodeNote」 JAVA高精度浮点数

「CodeNote」 HDU1281(二分图匹配+行列建图)

「CodeNote」二分图匹配

「CodeNote」 tarjan求LCA

「CodeNote」倍增求LCA

「CodeNote」双连通分量

FEATURED TAGS

ABOUT ME

FRIENDS

「CodeNote」 CF1249E(思维+dp)

「CodeNote」 CF1249D1(思维+set+线段覆盖)

「CodeNote」 HDU1045(二分图匹配+行列缩点建图)

「CodeNote」 网络流入门

「CodeNote」 JAVA高精度浮点数

「CodeNote」 HDU1281(二分图匹配+行列建图)

「CodeNote」 二分图匹配

「CodeNote」 tarjan求LCA

「CodeNote」 倍增求LCA

「CodeNote」 双连通分量

FEATURED TAGS

ABOUT ME

FRIENDS

「CodeNote」网络流入门

「CodeNote」二分图匹配

「CodeNote」倍增求LCA

「CodeNote」双连通分量