【算法】Tarjan求割点

填坑美滋滋。 割点是什么 如果一个点A是割点,那么在原图删去A点后原图联通块数会增加。 Tarjan 先只考虑联通图。 算法主体是dfs,依赖于一个叫“时间戳”的定义。 时间戳就是说执行这一次dfs是第几次。 emmm可以用这个东西卡时间骗分 对于每个点u,定义两个数组pre[u...

密码保护:【坑】dalao

C++ #define DREP(i, s, e) for(register int i = s; i >= e ;i--) #define REP(i, s, e) for(register int i = s; i <= e ;i++) #define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__) #...

【题解】SCOI2008 奖励关

传送门 题目大意 系统会随机给出k个食物,食物的种类共有n种。 吃每种食物之前必须先吃某些食物,一种食物吃完后会有一个收益val[i]。 求期望最大收益。 思路 题面中n\le 15这个条件似曾相识,考虑状压dp。 设dp[i][j]表示当前吃到了第i个食物,状压后已经吃了的食...

【题解】NOIP2007 矩阵取数游戏

自己开的坑,跪着也要填完。 题目大意 有一个n\times m的矩阵,每次可以取出每行的首项或末项。 一个数k的收益是k\times 2 ^ i,其中i表示k这个数在第i次被选出。 求最大总收益。 思路 简单的dp。 发现每一行互不影响,分开做。 设dp[i][j]表示选择区间[i,j]所获得...

密码保护:【题解】ZJOI2007 最大半连通子图

传送门 讲课听来的,exciting! 题目大意 一个有向图G=(V,E)称为半连通的满足:图中任意两点u v存在一条u到v的有向路径或者从v到u的有向路径。 给定一个有向图G,请求出G的最大半连通子图拥有的节点数K,以及不同的最大半连通子图的数目C。由于C可能比较大,仅要求输...

【题解】HNOI2010 弹飞绵羊

传送门 题目大意 有n个装置,编号从0到n-1,每个装置有一个弹力系数k[i],表示在这个位置的绵羊会被弹到第i+k[i]个装置,若不存在第i + k[i]个装置,则绵羊被弹飞。 给出m次操作,每次可能修改一个装置的弹力系数或询问绵羊从某个装置开始被弹几次会被弹飞。 分块 ...

【算法】分块

分块复杂度正确,怎么能叫骗分? ——Dr.Brave Stone Fake定义 分块就是把一个序列分成几个小块,同时对小块和单个元素进行操作。 这对于一些区间操作来说,常常有意想不到的好效果。 例子 打个比方,我们要区间加、区间查询和。 我们当然可以树状数组、线段树。 但...

【数据结构】左偏树

模板传送门 STL是个好东西,因为它集成了许多数据结构,比如priority_queue。 但是要合并时,priority_queue就GG了。 那么有两种解决方案。 使用pb_ds,但是由于其__gnu_pbds的下划线开头命名空间可能会出事。 手写。 左偏树 左偏树是一个堆,它有如下性质。 堆...

【题解】NOIP2013 货车运输

传送门 题目大意 给你一个无向图(不保证联通),你要在无向图中运货,限制每条边通过的货物不能超过每条边的边权。 每次给定起点和终点,问你每次一次性能运多少货? 思路 我们可以发现,有一些边权小的边我们其实不会走到。 所以我们可以简化这个图。 简化后的图...

【算法】倍增求lca(最近公共祖先)

Orz胡昊大爷。 先扯点闲谈 我以前写lca都是用tarjan写的。 虽说tarjan很好写,而且复杂度非常优秀。 但是他有一个致命的弱点:不能在线! 对于某些强制在线的题目,tarjan就GG了。 倍增原理 倍增是什么? 就是成倍増长。 树上倍增一个节点,就是求它向上跳2^k次后到...